четверг, 14 июля 2011 г.

Нахождение точки пересечения двух отрезков

Рассмотрим алгоритм нахождения точки пересечения двух векторов. Для этого нам понадобится параметрическое уравнение отрезка.
Пусть имеется некоторый отрезок P0P1, уравнение данного отрезка будет иметь вид:
где Р0 и Р1 – начальная и конечная точки отрезка;
u = P1-P0 – вектор, показывающий направление и длину отрезка;
s – координата точки на отрезке (или прямой, содержащей данный отрезок).
При  0 <= s <= 1 мы имеем множество точек, лежащих между точками Р0 и Р1, в противном случае (s < 0 или s > 1) – мы получим все точки, лежащие на прямой, содержащей данный отрезок, но за его границами («левее» и «правее»).
Рассмотрим теперь 2 отрезка, заданных параметрическими уравнениями:
Данные отрезки будут параллельны, если
где c – некоторое число.
Вспомним теперь понятие перпендикулярного скалярного произведения – модификации скалярного произведения, в котором первый вектор заменен его левой нормалью. Важным свойством данного произведения будет его равенство нулю в случае параллельности перемножаемых векторов (вытекает из свойств обычного скалярного произведения векторов), т.е.:
Это все была необходимая вводная информация. Перейдем теперь непосредственно к нахождению точки I пересечения отрезков P(s) и Q(t).
Иллюстрация к нахождению точки пересечения двух отрезков

Проведем вектор w, соединяющий начала отрезков P(s) и Q(t) (т.е. через точки P0 и Q0):

Условием пересечения отрезков P(s) и Q(t) будет перпендикулярность векторов P(s1)-Q0 и левой нормали вектора v  (см. рисунок), т.е. равенство их скалярного произведения нулю:
где
Тогда, подставив в выражение скалярного произведения векторов данные координаты векторов, получим:

Раскрыв скобки и перегруппировав, получим:

отсюда
Выражение в числителе полученной дроби – есть перпендикулярное скалярное произведение векторов v  и w, а выражение в знаменателе – перпендикулярное скалярное произведение векторов v  и u, взятое со знаком «минус». Тогда:
Аналогично найдем значение параметра t1 для отрезка Q(t):
 Таким образом, мы нашли значения параметров s1 и t1. Координаты самой точки пересечения можно найти, подставив значения одного из параметров в соответствующее уравнение отрезка. Например:
 Но полученная таким образом точка может лежать как в границах заданных отрезков, так и за их пределами, и нам необходимо определить лежит ли данная точка в границах отрезков, или нет. Для этого нужно, чтобы выполнялись следующие условия:
 Вот и вся теория необходимая нам для данной операции. Данную статью Вы можете скачать в формате pdf здесь (более читабельна).
Краткое описание алгоритма было взято отсюда. Я его только перевел и подробно расписал.

Комментариев нет:

Отправить комментарий