Как можно рассчитать точку пересечения прямой с квадратом

[RaVeN-Nikma]

Собственно, есть квадрат 100 на 100 px, внутри него есть случайная точка, за пределами квадрата есть еще одна точка, между этими двумя точками проводится отрезок. Необходимо узнать по какой стороне (ABCD), и в какой точке прямая пересекает квадрат.


Задачу решил, но решение не нравится. Интересно узнать какие варианты кому придут в голову.

[in4core]

Нарисуйте для себя xy координатную ось, где центр квадрата точка нулевая точка, и все вопросы должны отпасть мне кажется

[RaVeN-Nikma]

И как это поможет найти нужные данные (точку и сторону) Могли бы Вы продолжить мысль

[i.o.]

Необходимо узнать по какой стороне (ABCD), и в какой точке прямая пересекает квадрат.

Через пересечение четырех отрезков с заданным.

PS:

Нарисуйте для себя xy

ржунимагу

[Котяра]

Если есть координаты точек, то очевидно, что какие то xy уже существуют в условиях задачи.

[Alex Lexcuk]

Может поможет пересечение прямых?
http://www.murmadillo.tut.su/html/li...Intersect.html

[RaVeN-Nikma]

Alex Lexcuk, спасибо.

Делал тоже на основе пересечение отрезков, но этот пример красивее, чем то что я навоял.

[semenyakinVS]

Можно записать уравнение прямой параметрически и решить относительно переменной, которое изменяется. Т.е:

X(t) = begX + (endX - begX) * t; (1)
Y(t) = begY + (endY - begY) * t; (2)

Если подставить значение координаты стороны квадрата (если стороны квадрата ориентированы по осям) По одному из уравнений можно найти t (выбираем то, в котором координата начала и конца не равны). Например, для стороны В вашего квадрата:

maxX = begX + (endX - begX) * t; => t = (maxX - begX) / (endX - begX)

, где maxX - координата Х обеих точек стороны В.

После того, как находим t, получаем координаты точки, подставив t в формулы (1,2).

Отдельно надо будет исследовать параллельность (векторное произведение) со стороной и факт попадания в сторону (пересечение может произойти за стороной).

А вообще, если одна из точек внутри квадрата, может быть ещё более красивое и быстрое решение.

[-De-]

Про пересечение отрезков, рекомендую: http://users.livejournal.com/_winnie/152327.html
С++ код, но должен быть понятен. out_intersection - точка пересечения, если что.
Наглый спойлер: описано, почему не стоит параметризовать!

[semenyakinVS]

Сообщение от -De-

Про пересечение отрезков, рекомендую: http://users.livejournal.com/_winnie/152327.html
С++ код, но должен быть понятен. out_intersection - точка пересечения, если что.
Наглый спойлер: описано, почему не стоит параметризовать!

Интересная статья. Метод с перпендикуляром красивый.

Одно плохо - автор на умножения в функции не скупился. 16 штук (вместе с делением) - это много. А именно они в основном хавают ресурсы при поиске пересечений.

RaVeN-Nikma

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

На втором шаге можно глянуть выше или ниже угловая точка (между найденными двумя сторонами) отрезка и найти точно сторону, с которой будем искать пересечение (через векторное произведение). Дальше искать пересечение с конкретной стороной по выбранному вами алгоритму.

Это всё катит, ясное дело, только для ориентированного по осям квадрата.