пересечение линии и квадрата

Question

У меня есть квадрат в 2d пространстве (ширина = высота).Квадрат в настоящее время определяется двумя точками: BottomLeft (X1, Y1) и TopRight (X2, Y2).

Квадрат выровнен по оси, поэтому найти два других угла так же просто, как (X1, Y2)) и (X2, Y1).

У меня также есть две точки - одна всегда внутри квадрата, а другая определенно снаружи.Они не обязательно находятся в центре площади - они могут быть где угодно.Я тоже знаю их координаты.

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

Метод грубой силы - попытаться вычислитьпересечения для каждой стороны квадрата и проверьте, существует ли он.Его можно оптимизировать, рассчитав, где относительно квадрата находится вторая точка, и отбросив две линии (например, если координаты X и Y увеличиваются, нет необходимости проверять нижнюю и левую стороны квадрата).

Мне интересно, есть ли лучшее / более быстрое решение моей проблемы?Я буду писать на Java

Answer 1

Пусть внутренняя точка (x0, y0), внешняя точка (ox, oy)

Представляет линию в параметрической форме

vx = ox - x0
vy = oy - y0

//equations:
x = x0 + vx * t
y = y0 + vy * t

Теперь найдите потенциальные положения границ в зависимости от направления:

if vx > 0 then
   ex = x2
else
   ex = x1

if vy > 0 then
    ey = y2
else
   ey = y1

Проверьте дополнительные случаи горизонтального / вертикального направления линии:

 if vx = 0 then
      return cx = x0,  cy = ey

 if vy = 0 then
      return cx = ex, cy = y0

В общем случае найдите параметры пересечений с горизонтальным и вертикальнымлинии края

 tx = (ex - x0) / vx
 ty = (ey - y0) / vy

и получить пересечение для меньшего значения параметра

 if tx <= ty then //meet vertical edge first
     return cx = ex, cy = y0 + tx * vy
 else
    return  cx = x0 + ty * vx,  cy = ey

Answer 2

Эффективное решение:

Я предполагаю, что вы знаете, какая точка находится внутри квадрата (также может быть прямоугольником).

Вычтите координаты этой точки извсе остальные точки (вторая конечная точка и четыре угла).Рассмотрим подразделение плоскости на девять областей, образованных путем расширения сторон квадрата.Требуется четыре знаковых теста, чтобы узнать, в какой из восьми внешних областей находится другая точка.

Тогда, если эта точка находится в «боковой» области, вы неявно знаете, какая сторона пересекается.Если точка лежит в «угловой» области, вы должны выбрать между двумя сторонами, и это делается путем проверки того, с какой стороны отрезка прямой расположен угол.Для этого требуется вычисление области треугольника со знаком (два умножения и одно вычитание).

Когда вы знаете, какая из сторон пересекается, легко найти точку пересечения, используя пропорцию.Это занимает одно деление.

Наконец, вы переводите обратно в исходное положение внутренней точки.Общая стоимость составляет

• четыре вычитания,

• четыре знака испытаний,

• в случаеугловых областей, два умножения и одно вычитание,

• одно деление,

• два сложения

плюс немного клейкой логики.

Этот абсолютный минимум не гарантируется, но он должен быть близок к.