1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Введение==
{|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''' (фиксирование выравнивания) {{---}} это алгоритм, который восстанавливает топологию множества отрезков, координаты которого заданны с некоторой <tex>\varepsilon</tex> погрешностью.
===Мотивация===
Пусть у нас есть множество отрезков, чьи координаты были получены с некоторой абсолютной погрешностью. В такой структуре может быть нарушена топология, а это может повлиять на работу других алгоритмов над этой структурой.
Например, если у нас появилось ложное пересечение (рисунок 1) мы можем получить отрицательное "расстояние" до прямой, если ожидаем, что все точки лежат с одной стороны относительное неё. Ещё, из-за недостаточной точности, может быть нарушена замкнутость контура (рисунок 2), что приведёт, например, к неправильной заливки области в графическом редакторе.
===Свойства===
Пусть нам дано множество отрезков <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>.#Разобьём каждый пересекающий пучок на три части:#Обновим статус. ==Упрощение привязкивыравнивания==
==Замечания==
==Ссылки==
* [http://doc.cgal.org/latest/Snap_rounding_2/index.html CGAL - 2D Snap Rounding]
* [http://www.sciencedirect.com/science/article/pii/S0925772107000922 Iterated snap rounding with bounded drift]
* [http://cccg.ca/proceedings/2007/07a1full.pdf Efficient Snap Rounding with Integer Arithmetic]
* [http://www.cs.tau.ac.il/~danha/papers/issr.pdf An Intersection-Sensitive Algorithm for Snap Rounding]
==См. также==
* [[Алгоритм Бентли-Оттмана]]
* [[Упрощение полигональной цепи]]
* [[Представление чисел с плавающей точкой]]
