3622
правки
Изменения
м
→Частный случай множественных split event'ов на одном ребре
Чтобы решить эту проблему, следует хранить <tex>split\ event</tex> как <tex>3</tex> вершины {{---}} невыпуклая вершина и две вершины противолежащего ребра. Дополнительно нужно хранить [[Хеш-таблица | ассоциативный массив]] из пары вершин в ребро для этих вершин. Тогда в момент разделения ребра <tex>ZY</tex> необходимо удалить это ребро из ассоциативного массива и поместить туда два новых ребра <tex>ZX</tex> и <tex>XY</tex>, которые будут ссылаться на исходное ребро <tex> e_i </tex>.
Но в очереди могло быть событие по трём вершинам исходного ребра, однако а после разделения этого ребра уже нет (например, такое может произойти, если с ребром одновременно сталкивается несколько невыпуклых вершин, лежащих на параллельной этому ребру прямой). Посмотрев в ассоциативный массив, можно обнаружить, что такой пары вершин нет. Хотя Однако нам нужно всё же получить по ребру требуемую пару вершин. Для этого можно хранить ещё один ассоциативный массив из пар в рёбра, только из него уже не удалять старые пары. Тогда станет возможным получение по паре вершин ребра, а потом по ребру можно будет получить все актуальные пары вершин, соответствующих этому ребру, и добавить <tex>split\ event</tex> с нужной парой вершин.
==== Алгоритм для невыпуклых полигонов ====
