tl; dr：平面を使用します。数学については以下で説明します。下部にキャンバスの例があります。
すべてのセルが軸に沿った境界ボックスであるとすると、平面方程式を使用して、線とエッジの交点を見つけることができます。
飛行機
ボックスは、4つの幾何学的平面のセットと考えることができます。各平面には、平面の「正面」である方向を示す法線または長さ1のベクトルがあります。セルの側面を構成する平面の法線は次のようになります。
top = {x: 0, y: -1};
bottom = {x: 0, y: 1};
left = {x: -1, y: 0};
right = {x: 1, y: 0};
平面上の点が与えられると、平面には次の方程式があります。
distance = (normal.x * point.x) + (normal.y * point.y)
この方程式を使用して、平面の距離を計算できます。この場合、ボックスの左上隅（たとえば、xが10、yが100）が上面にあることがわかっているので、次のことができます。
distance = (0 * 10) + (-1 * 100)
distance = -100
平面に対するポイントのチェック
距離が決まったら、方程式を再利用して、平面に対して任意の点がどこにあるかを確認できます。ランダムな点p（xは-50、yは90）の場合、次のことができます。
result = (normal.x * p.x) + (normal.y * p.y) - distance
result = (0 * -50) + (-1 * 90) - (-100)
result = 0 + (-90) - (-100)
result = -90 + 100
result = 10
考えられる結果は2つあります。
if (result >= 0) {
// point is in front of the plane, or coplanar.
// zero means it is coplanar, but we don't need to distinguish.
} else {
// point is behind the plane
}
平面に対して線をチェックする
次の方法で、からaへの線の両方の端点を確認できます。b
result1 = (normal.x * a.x) + (normal.y * a.y) - distance
result2 = (normal.x * b.x) + (normal.y * b.y) - distance
4つの可能な結果があります：
if (result1 >= 0 && result2 >= 0) {
// the line is completely in front of the plane
} else if (result1 < 0 && result2 < 0) {
// the line is completely behind the plane
} else if (result1 >= 0 && result2 < 0) {
// a is in front, but b is behind, line is entering the plane
} else if (result1 < 0 && result2 >= 0) {
// a is behind, but b is in front, line is exiting the plane
}
線が平面と交差するとき、交点を見つけたいと思います。ベクトル用語で線を考えるのに役立ちます：
a + t * (b - a)
の場合t == 0、あなたは行の先頭にあり、行t == 1の終わりです。このコンテキストでは、交点を次のように計算できます。
time = result1 / (result1 - result2)
そして交点は次のとおりです。
hit.x = a.x + (b.x - a.x) * time
hit.y = a.y + (b.y - a.y) * time
ボックスに対して行をチェックする
その数学で、あなたはあなたの箱との交線を理解することができます。各平面に対してラインの端点をテストし、時間の最小値と最大値を見つける必要があります。
ボックスは凸多角形であるため、このチェックの初期段階があります。線がボックス内のいずれかの平面の前に完全にある場合、ボックスと交差することはできません。残りの飛行機のチェックをスキップできます。
JavaScriptでは、結果は次のようになります。
/**
* Find the points where a line intersects a box.
*
* @param a Start point for the line.
* @param b End point for the line.
* @param tl Top left of the box.
* @param br Bottom right of the box.
* @return Object {nearTime, farTime, nearHit, farHit}, or false.
*/
function intersectLineBox(a, b, tl, br) {
var nearestTime = -Infinity;
var furthestTime = Infinity;
var planes = [
{nx: 0, ny: -1, dist: -tl.y}, // top
{nx: 0, ny: 1, dist: br.y}, // bottom
{nx: -1, ny: 0, dist: -tl.x}, // left
{nx: 1, ny: 0, dist: br.x} // right
];
for (var i = 0; i < 4; ++i) {
var plane = planes[i];
var nearDist = (plane.nx * a.x + plane.ny * a.y) - plane.dist;
var farDist = (plane.nx * b.x + plane.ny * b.y) - plane.dist;
if (nearDist >= 0 && farDist >= 0) {
// both are in front of the plane, line doesn't hit box
return false;
} else if (nearDist < 0 && farDist < 0) {
// both are behind the plane
continue;
} else {
var time = nearDist / (nearDist - farDist);
if (nearDist >= farDist) {
// entering the plane
if (time > nearestTime) {
nearestTime = time;
}
} else {
// exiting the plane
if (time < furthestTime) {
furthestTime = time;
}
}
}
}
if (furthestTime < nearestTime) {
return false;
}
return {
nearTime: nearestTime,
farTime: furthestTime,
nearHit: {
x: a.x + (b.x - a.x) * nearestTime,
y: a.y + (b.y - a.y) * nearestTime
},
farHit: {
x: a.x + (b.x - a.x) * furthestTime,
y: a.y + (b.y - a.y) * furthestTime
}
};
}
それでも遅すぎる場合は、世界を大きな長方形に分割し、それらの長方形に線を割り当てることによって、ブロードフェーズカリングを行うこともできます。ラインとセルが同じ長方形にない場合、それらは衝突しません。
このキャンバスの例をアップロードしました。