1632
правки
Изменения
м
'''{|align="right" |-valign="top" |[[Файл:Snap rounding''' (фиксирование выравнивания) a11.png|мини|160px|Рисунок 1а {{---}} это алгоритм, который восстанавливает топологию множества Ложное пересечение отрезков, координаты которого заданны с некоторой ε погрешностью.]] |[[Файл:Snap rounding a2.png|мини|160px|Рисунок 1б {{---}} Устранение пересечения созданием новой точки.]] |-valign="top" |[[Файл:Snap rounding b1.png|мини|160px|Рисунок 2а {{---}} Нарушение целостности контура.]] |[[Файл:Snap rounding b2.png|мини|160px|Рисунок 2б {{---}} Замыкание контура объединением общих точек.]] |}
[[Файл:'''Snap rounding a11''' (фиксирование выравнивания) {{---}} это алгоритм, который восстанавливает топологию множества отрезков, координаты которого заданны с некоторой <tex>\varepsilon</tex> погрешностью.png]][[Файл:Snap rounding a2.png]]
rollbackEdits.php mass rollback
==Введение==
===Мотивация===Пусть у нас есть множество отрезков, чьи координаты были получены с некоторой абсолютной погрешностью. В такой структуре может быть нарушена топология, а это может повлиять на работу других алгоритмов над этой структурой. Например, если у нас появилось ложное пересечение (рисунок 1) мы можем получить отрицательное "расстояние" до прямой, если ожидаем, что все точки лежат с одной стороны относительное неё. Ещё, из-за недостаточной точности, может быть нарушена замкнутость контура (рисунок 2), что приведёт, например, к неправильной заливки области в графическом редакторе. ===Свойства===Пусть нам дано множество отрезков <tex>A</tex>, тогда полученный после выравнивания планарный граф <tex>A^*</tex> должен обладать следующими свойствами: # '''Фиксированная точность координат:''' все координаты <tex>A^*</tex> должны лежать в узлах некоторой решётки с шагом <tex>2 \varepsilon</tex>.# '''Геометрическое подобие:''' <tex>A^*</tex> должен полностью лежать в области, полученной [[Файл:Snap rounding b1.pngСумма Минковского (определение, вычисление)|суммой Минковского]]<tex>A</tex> и квадрата со стороной <tex>2 \varepsilon</tex>.[[Файл# '''Топологическое подобие:Snap rounding b2''' Существует непрерывное преобразование <tex>A</tex> в <tex>A^*</tex>.png]]
==Алгоритм==
{{Определение
|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>.
#Разобьём каждый пересекающий пучок на три части:
#Обновим статус.
==Упрощение выравнивания==
