1632
правки
Изменения
м
rollbackEdits.php mass rollback
|}
'''Snap rounding''' (фиксирование выравнивания) {{---}} это алгоритм, который восстанавливает топологию множества отрезков, координаты которого заданны с некоторой ε <tex>\varepsilon</tex> погрешностью.
===Мотивация===
Пусть нам дано множество отрезков <tex>A</tex>, тогда полученный после выравнивания планарный граф <tex>A^*</tex> должен обладать следующими свойствами:
# '''Фиксированная точность координат:''' все координаты <tex>A^*</tex> должны лежать в узлах некоторой ε решёткис шагом <tex>2 \varepsilon</tex>.# '''Геометрическое подобие:''' <tex>A^*</tex> должен полностью лежать в области, полученной [[Сумма Минковского (определение, вычисление)|суммой Минковского]] <tex>A</tex> и квадрата со стороной ε<tex>2 \varepsilon</tex>.
# '''Топологическое подобие:''' Существует непрерывное преобразование <tex>A</tex> в <tex>A^*</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>.
#Разобьём каждый пересекающий пучок на три части:
#Обновим статус.
==Упрощение выравнивания==
