Предикат "левый поворот" — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 21: Строка 21:
 
== Ссылки ==
 
== Ссылки ==
  
 +
* [http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%B4%D0%B8%D0%BA%D0%B0%D1%82 wikipedia.ru - Предикат]
 
* [http://e-maxx.ru/algo/segments_intersection_checking e-maxx.ru/algo - Проверка двух отрезков на пересечение]
 
* [http://e-maxx.ru/algo/segments_intersection_checking e-maxx.ru/algo - Проверка двух отрезков на пересечение]
* [http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%B4%D0%B8%D0%BA%D0%B0%D1%82 wikipedia.ru - Предикат]
 

Версия 01:23, 5 октября 2011

Эта статья находится в разработке!

Допустим нам дана задача: Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется проверить, пересекаются они на плоскости или нет. Для упрощения определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке"). Для начала разберемся, что за зверь такой - Предикат.

Определение:
Предикат (лат. praedicatum — заявленное, упомянутое, сказанное) — любое математическое высказывание, в котором есть, по меньшей мере, одна переменная

Примеры

- Например, обозначим предикатом EQ(x, y) отношение равенства («x = y»), где x и y принадлежат множеству вещественных чисел. В этом случае предикат EQ будет принимать истинное значение для всех равных x и y.

- Более житейским примером может служить предикат ПРОЖИВАЕТ(x, y, z) для отношения «x проживает в городе y на улице z» или ЛЮБИТ(x, y) для «x любит y», где множество M — это множество всех людей.


Итак, у нас есть задача, с чего начнем её решать? Одно из решений - определить, лежат ли точки концов отрезков по разные стороны от другого отрезка. Вот тут нам и поможет предикат. Два из трех аргументов это точки концов одного отрезка, а последний - один из концов другого отрезка.

Определение:
Left_Turn(a, b, c) = true, если (b - a)*(c - a) > 0


Единственное, на что следует обратить внимание — граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай надо рассмотреть отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют "проверкой на bounding box").

Ссылки