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

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


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

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

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

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

PS:
ржунимагу :D

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

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

Alex Lexcuk, спасибо.

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

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

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).

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

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

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

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

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

RaVeN-Nikma

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

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

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