120
правок
Изменения
Нет описания правки
Например, если у нас появилось ложное пересечение (рисунок 1) мы можем получить отрицательное "расстояние" до прямой, если ожидаем, что все точки лежат с одной стороны относительное неё. Ещё, из-за недостаточной точности, может быть нарушена замкнутость контура (рисунок 2), что приведёт, например, к неправильной заливки области в графическом редакторе.
===Свойства===
Пусть нам дано множество отрезков <tex>A</tex>, тогда полученный после выравнивания планарный граф <tex>A^*</tex> должен обладать следующими свойствами:
# '''Фиксированная точность координат:''' все координаты <tex>A^*</tex> должны лежать в узлах некоторой ε решётки.
# '''Геометрическое подобие:''' <tex>A^*</tex> должен полностью лежать в области, полученной [[Сумма Минковского (определение, вычисление)|суммой Минковского]] <tex>A</tex> и квадрата со стороной ε.
# '''Топологическое подобие:''' Существует непрерывное преобразование <tex>A</tex> в <tex>A^*</tex>.
==Алгоритм==
