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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры)
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
Допустим нам дана задача: Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется проверить, пересекаются они на плоскости или нет. Для упрощения определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке"). Для начала разберемся, что за зверь такой - Предикат.
+
Допустим нам дана задача: Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется проверить, пересекаются они на плоскости или нет. Для упрощения определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке").
{{Определение
 
|definition =
 
'''Предикат''' (лат. '''praedicatum''' — заявленное, упомянутое, сказанное)  — любое математическое высказывание, в котором есть, по меньшей мере, одна переменная
 
}}
 
== Примеры ==
 
 
 
- Например, обозначим предикатом EQ(x, y) отношение равенства («x = y»), где ''x'' и ''y'' принадлежат множеству вещественных чисел. В этом случае предикат EQ будет принимать истинное значение для всех равных x и y.
 
 
 
- Более житейским примером может служить предикат ПРОЖИВАЕТ(x, y, z) для отношения «x проживает в городе y на улице z» или ЛЮБИТ(x, y) для «x любит y».
 
 
 
  
 
Итак, у нас есть задача, с чего начнем её решать? Какие вообще могут быть расположения точек и самих отрезков относительно друг друга?
 
Итак, у нас есть задача, с чего начнем её решать? Какие вообще могут быть расположения точек и самих отрезков относительно друг друга?
Строка 32: Строка 22:
 
[[Файл:Bounting_box().png]]
 
[[Файл:Bounting_box().png]]
 
[[Файл:Bounting_box_.png]]
 
[[Файл:Bounting_box_.png]]
 
== Ссылки ==
 
 
* [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 - Проверка двух отрезков на пересечение]
 

Версия 04:58, 13 октября 2011

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

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

Итак, у нас есть задача, с чего начнем её решать? Какие вообще могут быть расположения точек и самих отрезков относительно друг друга?

Cross.png Two segments.png Touch.jpg

Одно из решений - определить, лежат ли точки концов отрезков по разные стороны от другого отрезка. Вот тут нам и поможет наш предикат, где два из трех аргументов (например a и b) это точки концов одного отрезка, а последний - один из концов другого отрезка.

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


Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Какую? Посмотрим внимательнее на наш предикат. Ошибка раскрывается тогда, когда угол между отрезками АВ и АС крайне мал.

Tiny angle.jpg

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

Bounting box().png Bounting box .png