Snap rounding

Материал из Викиконспекты
Перейти к: навигация, поиск
НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

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

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.
Эта статья находится в разработке!

Введение

Рисунок 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. Обновим статус.

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

Замечания

Ссылки

См. также