3622
правки
Изменения
→Алгоритм для невыпуклых полигонов
::* создадим две новые вершины <tex> V_1 </tex> и <tex> V_2 </tex> с одинаковыми координатами точки пересечения <tex> I </tex>,
::* найдём для каждой вершины <tex> V_1 </tex> и <tex> V_2 </tex> противолежащее ребро в своём подпалигоне,
::* разделим <tex> \mathrm{LAV}</tex> с вершиной <tex> V </tex> на две части (как показано на рисунке выше), вставим в части вершины <tex> V_1 </tex> и <tex> V_2 </tex>, а затем обе части добавим в <tex> \mathrm{SLAV}</tex>. Вершина <tex> V_1 </tex> будет следующей для предыдующего к <tex> V </tex> узлу узла в <tex> \mathrm{LAV}</tex> и предыдущей для конца противолежащего ребра. Аналогично для вершины <tex> V_2 </tex>. Этот шаг в действительно разбивает полигон на две части,
::* удалим из ассоциативного массива пару вершин ребра <tex> e_i </tex> и поместим две новых пары, в одной из которых будет вершина <tex> V_1 </tex> и конец ребра <tex> e_i </tex>, а в другом {{---}} начало <tex> e_i </tex> и вершина <tex> V_2 </tex>,
::* Добавим указатели вершинам <tex> V_1 </tex> и <tex> V_2 </tex> на соответствующие рёбра.
