Snap rounding — различия между версиями
Alex z (обсуждение | вклад) |
Alex z (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
==Введение== | ==Введение== | ||
| + | {|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''' (фиксирование выравнивания) {{---}} это алгоритм, который восстанавливает топологию множества отрезков, координаты которого заданны с некоторой ε погрешностью. | '''Snap rounding''' (фиксирование выравнивания) {{---}} это алгоритм, который восстанавливает топологию множества отрезков, координаты которого заданны с некоторой ε погрешностью. | ||
| − | + | ===Мотивация=== | |
| − | + | Пусть у нас есть множество отрезков, чьи координаты были получены с некоторой абсолютной погрешностью. В такой структуре может быть нарушена топология, а это может повлиять на работу других алгоритмов над этой структурой. | |
| + | |||
| + | Например, если у нас появилось ложное пересечение (рисунок 1) мы можем получить отрицательное "расстояние" до прямой, если ожидаем, что все точки лежат с одной стороны относительное неё. Ещё, из-за недостаточной точности, может быть нарушена замкнутость контура (рисунок 2), что приведёт, например, к неправильной заливки области в графическом редакторе. | ||
| + | |||
| − | |||
| − | |||
==Алгоритм== | ==Алгоритм== | ||
Версия 00:24, 1 августа 2014
Эта статья находится в разработке!
Содержание
Введение
Snap rounding (фиксирование выравнивания) — это алгоритм, который восстанавливает топологию множества отрезков, координаты которого заданны с некоторой ε погрешностью.
Мотивация
Пусть у нас есть множество отрезков, чьи координаты были получены с некоторой абсолютной погрешностью. В такой структуре может быть нарушена топология, а это может повлиять на работу других алгоритмов над этой структурой.
Например, если у нас появилось ложное пересечение (рисунок 1) мы можем получить отрицательное "расстояние" до прямой, если ожидаем, что все точки лежат с одной стороны относительное неё. Ещё, из-за недостаточной точности, может быть нарушена замкнутость контура (рисунок 2), что приведёт, например, к неправильной заливки области в графическом редакторе.
Алгоритм
Упрощение выравнивания
Замечания
Ссылки
- CGAL - 2D Snap Rounding
- Iterated snap rounding with bounded drift
- Efficient Snap Rounding with Integer Arithmetic
- An Intersection-Sensitive Algorithm for Snap Rounding
