120
правок
Изменения
м
Нет описания правки
|}
'''Snap rounding''' (фиксирование выравнивания) {{---}} это алгоритм, который восстанавливает топологию множества отрезков, координаты которого заданны с некоторой ε <tex>\varepsilon</tex> погрешностью.
===Мотивация===
==Алгоритм==
{{Определение
|definition=
'''Активная ячейка''' {{---}} ячейка решётки, относительно которой идёт выравнивание, в которую попал конец отрезка или точка пересечения отрезков из <tex>A</tex>.
}}
{{Определение
|definition=
'''Пучок''' <tex>b_h</tex> {{---}} подмножество отрезков <tex>A</tex>, у которых меньший в лексикографическом порядке конец лежит в ячейке <tex>h</tex>.
}}
{{Определение
|definition=
<tex>u(b)</tex> {{---}} отрезок лежащий выше всех в пучке <tex>b</tex>.<br/><tex>l(b)</tex> {{---}} отрезок лежащий ниже всех в пучке <tex>b</tex>.
}}
В целом алгоритм выравнивания похож на [[Алгоритм Бентли-Оттмана|алгоритм Бентли-Оттмана]], только мы будем манипулировать пучками вместо отрезков.
Инициализируем приоритетную очередь <tex>Q</tex> для хранения активных ячеек в лексикографическом порядке. Также инициализируем статус <tex>T</tex> для хранения пучков, которые в данный момент пересекает заметающая прямая. Для каждого конца отрезка из <tex>A</tex> добавим в <tex>Q</tex> соответствующую активную ячейку.
Далее будем доставать из <tex>Q</tex> активные ячейки и для каждой ячейки <tex>h</tex> выполнять следующие операции:
#Найдём все пучки в статусе <tex>T</tex>, которые пересекают ячейку <tex>h</tex>.
#Разобьём каждый пересекающий пучок на три части:
#Обновим статус.
==Упрощение выравнивания==
