Изменения

Наличие невыпуклой вершины может привести (а может и не привести) к разделению внутренней области. Невыпуклая вершина может участвовать в обычном <tex> edge\ event'</tex>е (точка <tex> A </tex> на рисунке выше). В таком случае <tex> edgeEdge\ event'</tex>ы в случае невыпуклогого многоугольника обрабатываются так же, как и в алгоритме с выпуклым многоугольником.

В простейшем случае точка <tex> B </tex> появляется, когда "волновой фронт" распространения движения рёбер от невыпуклой вершины натыкается на встречный фронт противолежащего ребра. В такой момент возникает <tex> split\ event</tex>. Поэтому точка <tex> B </tex> может быть изначально охарактеризована, как точка, находящаяся на одном расстоянии от противолежащего ребра и прямых, содержащих рёбра невыпуклой вершины. Задача состоит в том, чтобы найти это самое противолежащее ребро (случай <tex> a) </tex> на рисунке выше). Но как показывает случай <tex> b) </tex>, простой тест на пересечение ребра и биссектрисы невыпуклой вершины (то есть невыпуклая вершина как бы врезается в противолежащее ребро) не может быть использован (в этом случае луч биссектрисы пересекает сразу два ребра, непонятно, с каким из них произойдёт <tex> split\ event</tex>). Поэтому необходимо проверять, что точка <tex> B </tex> лежит в "бесконечном" треугольнике, ограниченном противолежащим ребром и биссектрисами <tex> b_i </tex> и <tex> b_{i+1} </tex>, идущими из вершин, инцидентных противолежащему ребру <tex> e_i </tex>.