Возьмем луч, выходящий из произвольной точки А, и рассмотрим, к чему может привести прохождение луча через вершину многоугольника. Основные возможные случаи изображены на рис. 8.5.

В случае а, когда ребра, выходящие из соответствующей вершины, лежат по одну сторону от луча, четность количества пересечений не меняется.

в

б V

Рис. 8.5

8. Основные алгоритмы вычислительной геометрии Случай в, когда выходящие из вершины ребра лежат по разные стороны от луча, четность количества пересечений изменяется.

К случаям б и г такой подход непосредственно неприменим. Несколько изменим его, заметив, что в случаях а и б вершины, лежащие на луче, являются экстремальными значениями в тройке вершин соответствующих отрезков. В других же случаях экстремума нет.

Исходя из этого, можно построить следующий алгоритм"opengl3_138.html">⇐ Предыдущая| |Следующая ⇒