3622
правки
Изменения
→Невыпуклый полигон
Можно физически разделить исходное ребро на два, вставив новую точку <tex> S </tex>. Это решает проблему, так как никакое ребро не будет разделено дважды, а определение концов разделяемого ребра выполняется просто. Вставка вершины для точки <tex> B </tex> в <tex> \mathrm{LAV} </tex> тоже происходит относительно просто, потому что мы знаем точно, с каким ребром эта вершина связана. Но такой подход требует отдельно рассматривать вершины типа <tex> S </tex>, чтобы не добавить их случайно в <tex> \mathrm{straight}\ \mathrm{skeleton}</tex>.
===== Второй способ (используемый в авторском решении) =====
Идея заключается в том, чтобы хранить только вершины, которые реально будут в <tex> \mathrm{straight}\ \mathrm{skeleton}</tex> , а указатели на разделямое ребро хранятся во всех подполигонах, для которых это ребро является общим. Это приводит к множественным попаданиям <tex> split\ event'</tex>ов на одно ребро. Для примера, два полигона на рисунке выше разделяют общую ссылку на ребро <tex> e_i </tex>. Во время процесса обработки вершины <tex> B </tex> многоугольник <tex> XMVNY </tex> разбивается на две части <tex> XMB </tex> и <tex> BNY </tex>, а вершина <tex> V </tex> помечается как обработанная. Всё это нужно для того, чтобы правильно связать <tex> B </tex> с вершинами <tex> X </tex> и <tex> Y </tex>, а не с <tex> Z </tex> и <tex> Y </tex>. Во время обхода <tex> \mathrm{SLAV} </tex> выбирается правильная часть ребра <tex> e_i </tex> (в данном случае она определяется вершинами <tex> X </tex> и <tex> Y </tex>). Определяется следующим образом: вершина <tex> B </tex> лежит справа от биссектрисы посещённой вершины <tex> Y </tex> и слева от биссектрисы предка посещённой вершины <tex> X </tex>.
==== Алгоритм для невыпуклых полигонов ====
