3622
правки
Изменения
→Алгоритм с изпользованием SLAV
==== Нахождение координат точки B ====
[[Файл:skeleton_b_point_coord.png|500px]]
В простейшем случае точка <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>.
'''Замечание:''' простой тест на пересечение биссектрисы вершины <tex> V </tex> и целой линии, содержащей ребро, отсекает случаи тех рёбер, которые лежат ''позади'' вершины <tex> V </tex>.
Координаты возможной точки кандидата <tex> B_i </tex> вычисляются следующим образом: это точка пересечения биссектрисы вершины <tex> V </tex> и биссектрисы угла, который образуется в точке пересечения прямой, содержащей одно из рёбер, инцидентных <tex> V </tex>, и прямой, содержащей противолежащее ребро <tex> e_i </tex>. Итоговая точка пересечения <tex> B </tex> выбирается как ближайшая среди всех найденных точек <tex> B_i </tex>.
'''Частный случай:''' в этом месте также должна быть проверка на то, что противолежащее ребро не будет параллельно ни одному ребру вершины <tex> V </tex>. Тогда рёбра могут накладываться друг на друга. {{TODO | t = И что делать?(}}
==== Работа с LAV в момент возникновения split event'a ====
