Если у вас есть 2 точки, (x1, y1) и (x2, y2), которые представляют собой два противоположных угла прямоугольника и две другие точки (x3, y3) и (x4, y4), которые представляют собой 2 конечные точки сегмента линии, как вы можете проверить, пересекает ли отрезок линии прямоугольник?
(Сегмент линии - это только сегмент, содержащийся между данными конечными точками. Это не бесконечная длина, определяемая этими двумя точками.)
Одним очень простым вариантом было бы использовать стандартный алгоритм для проверки пересечения двух сегментов линии, чтобы проверить, пересекаются ли сегменты линий с любым из четырех сегментов линии, которые делают вверх по углам коробки. Это очень удобно, чтобы проверить, пересекаются ли два сегмента линии, поэтому я ожидаю, что это может произойти очень быстро.
Надеюсь, это поможет!
Чтобы понять, как получить формулу для проверки того, пересекает ли сегмент линии прямоугольник, важно помнить свойства vector dot product.
Представляем сегмент линии как единичный вектор и расстояние между начальной точкой линии и началом. Здесь некоторый код С# для вычисления того из переменных PointF a_ptStart и a_ptEnd, используя Vector:
Vector vecLine = new Vector(a_ptEnd.X - a_ptStart.X, a_ptEnd.Y - a_ptStart.Y);
double dLengthLine = vecLine.Length;
vecLine /= dLengthLine;
double dDistLine = Vector.Multiply(vecLine, new Vector(a_ptStart.X, a_ptStart.Y));
Вам также потребуется вычислить перпендикулярный вектор и его расстояние от начала координат для сегмента линии. Вращение единичного вектора на 90 °; легко.
Vector vecPerpLine = new Vector(-vecLine.Y, vecLine.X);
double dDistPerpLine = Vector.Multiply(vecPerpLine, new Vector(a_ptStart.X, a_ptStart.Y));
Предполагая, что четыре угла прямоугольника находятся в переменных Vector, называемых vecRect1, vecRect2, vecRect3 и vecRect4, вычислите расстояние между сегментом линии и всеми четырьмя углами целевого ограничивающего прямоугольника:
double dPerpLineDist1 = Vector.Multiply(vecPerpLine, vecRect1) - dDistPerpLine;
double dPerpLineDist2 = Vector.Multiply(vecPerpLine, vecRect2) - dDistPerpLine;
double dPerpLineDist3 = Vector.Multiply(vecPerpLine, vecRect3) - dDistPerpLine;
double dPerpLineDist4 = Vector.Multiply(vecPerpLine, vecRect4) - dDistPerpLine;
double dMinPerpLineDist = Math.Min(dPerpLineDist1, Math.Min(dPerpLineDist2,
Math.Min(dPerpLineDist3, dPerpLineDist4)));
double dMaxPerpLineDist = Math.Max(dPerpLineDist1, Math.Max(dPerpLineDist2,
Math.Max(dPerpLineDist3, dPerpLineDist4)));
Если все расстояния положительные или все расстояния отрицательные, то прямоугольник находится на одной стороне линии или другой, поэтому нет пересечения. (Предполагается, что прямоугольники с нулевой гранью не пересекаются с любым сегментом линии.)
if (dMinPerpLineDist <= 0.0 && dMaxPerpLineDist <= 0.0
|| dMinPerpLineDist >= 0.0 && dMaxPerpLineDist >= 0.0)
/* no intersection */;
Затем проецируйте все четыре угла целевого ограничивающего прямоугольника на сегмент линии. Это дает нам расстояние между началом линии и проекцией прямоугольника на эту линию.
double dDistLine1 = Vector.Multiply(vecLine, vecRect1) - dDistLine;
double dDistLine2 = Vector.Multiply(vecLine, vecRect2) - dDistLine;
double dDistLine3 = Vector.Multiply(vecLine, vecRect3) - dDistLine;
double dDistLine4 = Vector.Multiply(vecLine, vecRect4) - dDistLine;
double dMinLineDist = Math.Min(dDistLine1, Math.Min(dDistLine2,
Math.Min(dDistLine3, dDistLine4)));
double dMaxLineDist = Math.Max(dDistLine1, Math.Max(dDistLine2,
Math.Max(dDistLine3, dDistLine4)));
Если точки прямоугольника не попадают в длину сегмента линии, то нет пересечения.
if (dMaxLineDist <= 0.0 || dMinLineDist >= dLengthLine)
/* no intersection */;
Я считаю, что это достаточно.
Получите точечный продукт всех четырех вершин (углов прямоугольника) с вектором направления отрезка линии. Если все 4 имеют значения одного и того же знака, то все вершины лежат на одной стороне линии (а не на отрезке линии, а на бесконечной линии), и поэтому линия не пересекает прямоугольник. Этот подход является только жизнеспособным для обнаружения двумерных пересечений. Это можно использовать для фильтрации через большинство из них быстро (с использованием только умножений и дополнений). Вам нужно будет сделать дополнительные проверки для сегментов линии вместо строк.