Snap rounding

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

Введение

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

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

См. также

• Алгоритм Бентли-Оттмана
• Упрощение полигональной цепи
• Представление чисел с плавающей точкой