tl; др: Используйте самолеты, математика объяснена ниже. Внизу есть пример холста.
Учитывая, что все ваши ячейки являются ограничивающими прямоугольниками, вы можете использовать уравнение плоскости, чтобы найти пересечение вашей линии с ребрами.
Planes
Вы можете представить свою коробку как набор из четырех геометрических плоскостей . Каждая плоскость имеет нормаль или вектор длиной один, указывающий, какое направление является «фронтом» плоскости. Нормали для плоскостей, составляющих стороны вашей клетки, будут:
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
Возможны два результата:
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
Возможны четыре результата:
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
}
};
}
Если это все еще слишком медленно, вы также можете сделать широкофазный отбор, разделив мир на большие риты и назначив линии этим ритам. Если ваша линия и ячейка не совпадают, они не сталкиваются.
Я загрузил пример холста этого .