フロントエンドのグラフィックスは、クロスがあるパスを決定する方法

ビジュアライゼーション・アプリケーションでは、経路が交差しているかどうかを判断する必要がよくあります。経路が交差しているかどうかによって、多角形が単純多角形であるかどうかを判断したり、交通経路が交差点を持っているかどうかを判断したりすることができます。

この問題は、実際には本質的に2つの線分が交差するかどうかを判断することです。パスは、線分で構成されているため、限り、隣接する線分に加えて判断するように、他の線分が2つに交差することはできません、JSコードは次のとおりです：

function isPathIntersection(points) {
 const len = points.length;
 for(let i = 0; i < len - 1; i++) {
 const point = points[i];
 const nextPoint = points[i + 1];
 for(let j = 0; j < len - 1; j++) {
 const p1 = points[j],
 p2 = points[j + 1];
 if(p1 !== point && p2 !== point && p1 !== nextPoint && p2 !== nextPoint
 && isCross(p1, p2, point, nextPoint) && isCross(point, nextPoint, p1, p2)) {
 return true;
 }
 }
 }
 return false;
}

上記のコードは、実際には、2つのループを使って各線分のパスを走査し、2つの線分が交差しているかどうかを判定するもので、判定ロジックはisCross関数に実装されています。

では、isCross関数はどのように実装すればいいのでしょうか？分析してみましょう。

下図のように、ベクトルがベクトルの位置する直線と交差する場合、ベクトルとベクトルはベクトルの反対側にあり、C X B と C X A の符号が反対であること、つまりこの左図を満たすはずです。逆に、ベクトルがベクトルの位置する直線と交差しない場合、ベクトルとベクトルは同じ側にある、すなわち、C X B と C X A は同じ符号を持ちます。

そこで、この原則に基づき、isCross関数は次のように実装することができます：

function isCross(p1, p2, p3, p4) {
 const v1 = subtract([], p4, p3);
 const v2 = subtract([], p1, p3);
 const v3 = subtract([], p2, p3);
 const z1 = cross(v1, v2);
 const z2 = cross(v1, v3);
 return z1 * z2 <= 0;
}

subtractはベクトルの減算、crossはベクトルのクロス積。

では、なぜisPathIntersectionでisCrossを2回判定しなければならないのでしょうか？

isCross(p1, p2, point, nextPoint) && isCross(point, nextPoint, p1, p2)

直線A（p1, p2）と直線B（p3, p4）の交点は、AがBのある直線の両側にあることと、BがAのある直線の両側にあることの両方を満たさなければならないからです。

たとえば上のグラフの場合、isCross(p1, p2, p3, p4)は真ですが、isCross(p3, p4, p1, p2)は偽で、2つの線分は交差しません。

つまり、これで全機能を実現することができ、全コードは以下のように複雑ではありません：

import {subtract, cross} from '../common/lib/math/functions/Vec2Func.js';
function isCross(p1, p2, p3, p4) {
 const v1 = subtract([], p4, p3);
 const v2 = subtract([], p1, p3);
 const v3 = subtract([], p2, p3);
 const z1 = cross(v1, v2);
 const z2 = cross(v1, v3);
 return z1 * z2 <= 0;
}
function isPathIntersection(points) {
 const len = points.length;
 for(let i = 0; i < len - 1; i++) {
 const point = points[i];
 const nextPoint = points[i + 1];
 for(let j = 0; j < len - 1; j++) {
 const p1 = points[j],
 p2 = points[j + 1];
 if(p1 !== point && p2 !== point && p1 !== nextPoint && p2 !== nextPoint
 && isCross(p1, p2, point, nextPoint) && isCross(point, nextPoint, p1, p2)) {
 return true;
 }
 }
 }
 return false;
}
function draw(context, points) {
 context.clearRect(0, 0, context.canvas.width, context.canvas.height);
 const d = `M${points.join('L')}`;
 const color = isPathIntersection(points) ? 'red' : 'blue';
 context.strokeStyle = color;
 const path = new Path2D(d);
 context.stroke(path);
}
const canvas = document.querySelector('canvas');
const ctx = canvas.getContext('2d');
ctx.lineWidth = 5;
ctx.lineJoin = 'round';
ctx.lineCap = 'round';
const points = [];
canvas.addEventListener('click', (evt) => {
 const {x, y} = evt;
 const {x: x0, y: y0} = evt.target.getBoundingClientRect();
 points.push([x - x0, y - y0]);
 draw(ctx, points);
});
canvas.addEventListener('dblclick', (evt) => {
 points.length = 0;
 draw(ctx, points);
});

最終的な結果は以下の通り：

オンラインデモのアドレス