3622
правки
Изменения
м
→Алгоритм для выпуклых полигонов
'''Шаг 2.''' Следующие действия выполняются в цикле, пока приоритетная очередь не пуста:
:<tex>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди.
:<tex>(b)</tex> Если вершины <tex> V_a </tex> и <tex> V_b </tex>, соответствующие данной точке пересечения , помечены как обработанные, то переходим к следующей итерации цикла шага 2. Это означает, что ребро между данными вершинами полностью стянулось (обработанные вершины и стянутые рёбра помечены крестом на рисунке ниже). Эту проверку необходимо делать из-за того, что мы могли поместить обработанные вершины в момент получения новых <tex>event'</tex>ов.
:<tex>(c)</tex> Если осталось всего три вершины <tex> V_a, V_b, V_c </tex>, то добавим в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> рёбра <tex> IV_a, IV_b, IV_c </tex>. В случае выпуклого многоугольника в этом месте можно завершить алгоритм. Но в общем случае нужно будет перейти к началу цикла снова.
:<tex>(d)</tex> Добавим в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> рёбра <tex> IV_a, IV_b </tex>.
