Как проверить, пересекает ли сегмент линии прямоугольник?

Одним очень простым вариантом было бы использовать стандартный алгоритм для проверки пересечения двух сегментов линии, чтобы проверить, пересекаются ли сегменты линии между четырьмя линейными сегментами, составляющими углы поля. Вычислительно очень эффективно проверять, пересекаются ли два сегмента линии, поэтому я ожидаю, что это может работать очень быстро.

Надеюсь это поможет!

Чтобы понять, как получить формулу для проверки того, пересекает ли сегмент линии прямоугольник, важно помнить свойства векторного точечного продукта .

Представляем сегмент линии как единичный вектор и расстояние между начальной точкой сегмента линии и началом. Вот некоторый код C #, чтобы вычислить это из переменных 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 вершин (углы прямоугольника) с вектором направления отрезка линии. Если все 4 имеют значения одного и того же знака, то все вершины лежат на одной стороне линии (а не на отрезке линии, а на бесконечной линии), и поэтому линия не пересекает прямоугольник. Этот подход является только жизнеспособным для обнаружения двумерных пересечений. Это можно использовать для фильтрации через большинство из них быстро (с использованием только умножений и дополнений). Вам придется выполнять дополнительные проверки для сегментов линии, а не строк.