Snap rounding — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 6 промежуточных версий 2 участников)
Строка 2: Строка 2:
  
 
==Введение==
 
==Введение==
'''Snap rounding''' (фиксирование выравнивания) {{---}} это алгоритм, который восстанавливает топологию множества отрезков, координаты которого заданны с некоторой ε погрешностью.
+
{|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://doc.cgal.org/latest/Snap_rounding_2/index.html CGAL - 2D Snap Rounding]
Строка 12: Строка 60:
 
* [http://cccg.ca/proceedings/2007/07a1full.pdf Efficient Snap Rounding with Integer Arithmetic]
 
* [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]
 
* [http://www.cs.tau.ac.il/~danha/papers/issr.pdf An Intersection-Sensitive Algorithm for Snap Rounding]
 +
 +
==См. также==
 +
* [[Алгоритм Бентли-Оттмана]]
 +
* [[Упрощение полигональной цепи]]
 +
* [[Представление чисел с плавающей точкой]]

Текущая версия на 19:19, 4 сентября 2022

Эта статья находится в разработке!

Введение

Рисунок 1а — Ложное пересечение отрезков.
Рисунок 1б — Устранение пересечения созданием новой точки.
Рисунок 2а — Нарушение целостности контура.
Рисунок 2б — Замыкание контура объединением общих точек.

Snap rounding (фиксирование выравнивания) — это алгоритм, который восстанавливает топологию множества отрезков, координаты которого заданны с некоторой [math]\varepsilon[/math] погрешностью.

Мотивация

Пусть у нас есть множество отрезков, чьи координаты были получены с некоторой абсолютной погрешностью. В такой структуре может быть нарушена топология, а это может повлиять на работу других алгоритмов над этой структурой.

Например, если у нас появилось ложное пересечение (рисунок 1) мы можем получить отрицательное "расстояние" до прямой, если ожидаем, что все точки лежат с одной стороны относительное неё. Ещё, из-за недостаточной точности, может быть нарушена замкнутость контура (рисунок 2), что приведёт, например, к неправильной заливки области в графическом редакторе.

Свойства

Пусть нам дано множество отрезков [math]A[/math], тогда полученный после выравнивания планарный граф [math]A^*[/math] должен обладать следующими свойствами:

  1. Фиксированная точность координат: все координаты [math]A^*[/math] должны лежать в узлах некоторой решётки с шагом [math]2 \varepsilon[/math].
  2. Геометрическое подобие: [math]A^*[/math] должен полностью лежать в области, полученной суммой Минковского [math]A[/math] и квадрата со стороной [math]2 \varepsilon[/math].
  3. Топологическое подобие: Существует непрерывное преобразование [math]A[/math] в [math]A^*[/math].

Алгоритм

Определение:
Активная ячейка — ячейка решётки, относительно которой идёт выравнивание, в которую попал конец отрезка или точка пересечения отрезков из [math]A[/math].


Определение:
Пучок [math]b_h[/math] — подмножество отрезков [math]A[/math], у которых меньший в лексикографическом порядке конец лежит в ячейке [math]h[/math].


Определение:
[math]u(b)[/math] — отрезок лежащий выше всех в пучке [math]b[/math].
[math]l(b)[/math] — отрезок лежащий ниже всех в пучке [math]b[/math].


В целом алгоритм выравнивания похож на алгоритм Бентли-Оттмана, только мы будем манипулировать пучками вместо отрезков.

Инициализируем приоритетную очередь [math]Q[/math] для хранения активных ячеек в лексикографическом порядке. Также инициализируем статус [math]T[/math] для хранения пучков, которые в данный момент пересекает заметающая прямая. Для каждого конца отрезка из [math]A[/math] добавим в [math]Q[/math] соответствующую активную ячейку.

Далее будем доставать из [math]Q[/math] активные ячейки и для каждой ячейки [math]h[/math] выполнять следующие операции:

  1. Найдём все пучки в статусе [math]T[/math], которые пересекают ячейку [math]h[/math].
  2. Разобьём каждый пересекающий пучок на три части:
  3. Обновим статус.

Упрощение выравнивания

Замечания

Ссылки

См. также