Алгоритм плоской развертки: Как упорядочить отрезки после точки пересечения

Question

Я пытаюсь реализовать в коде C++ алгоритм плоской развертки для пересечений сегментов, основанный на этой книге: http://www.cs.uu.nl/geobook/. Они предлагают реализовать структуру состояния развертки плоскости с использованием сбалансированного бинарного дерева поиска.

Я использую структуру std::set для реализации структуры состояния, но у меня возникают проблемы с переупорядочением сегментов, которые содержат точку "p", а их верхняя конечная точка - это точка "p". Они имеют одинаковую координатную точку, что означает, что я не могу вставить их в std::set, потому что он не допускает повторяющихся значений... Я попытался вставить их с их нижней конечной точкой, но тогда они потеряют порядок, в котором они пересекаются линией разметки чуть ниже "р".

Псевдокод, который есть в книге, говорит следующее:

6. Вставьте сегменты в U(p) ∪C(p) в Дао. Порядок сегментов в Дао должен соответствовать порядку, в котором они пересекаются линией развертки чуть ниже p. Если есть горизонтальный сегмент, он идет последним среди всех сегментов, содержащих p.
7. (∗ Удаление и повторная вставка сегментов C (p) меняет их порядок. ∗)

Я не знаю, как они собираются изменить свой порядок.. Когда я вставляю сегменты в структуру статуса, я сортирую их по их координате верхней конечной точки. Я не знаю, как поменять их порядок после пересечения.

Любая идея?

Обновление: книга находится здесь: https://books.google.com/books?id=C8zaAWuOIOcC но некоторые страницы не отображаются. Это на главе 2, страницы 24, 25 и 26. Надеюсь, что это помогает дать некоторый контекст

Лучший,

Answer 1

Предикат сортировки для std::set Используемая в качестве структуры данных состояния развертки плоскости должна работать следующим образом:

1. Он должен (динамически) вычислять координату пересечения данного сегмента с линией развертки для текущей позиции линии развертки.

2. В случае связывания (когда два сегмента пересекают линию развертки по одной и той же координате), необходимо также сравнить углы двух сегментов - это позволит выяснить порядок сегментов в статусе для будущих позиций линия развертки

Обратите внимание, что требование 1. выше означает, что объект предиката должен содержать ссылку на переменную положения линии развертки, чтобы он мог правильно сравнивать сегменты по мере продвижения линии развертки. Положение линии развертки не может быть сохранено в самом предикате, потому что тогда вы не сможете обновить его из своего алгоритма (std::set не предоставляет доступ к его предикату по ссылке).

РЕДАКТИРОВАТЬ

Обратите внимание, что ответственность за поддержание правильного порядка сегментов в наборе (т. Е. Обменивать их по мере необходимости) по-прежнему лежит на алгоритме - std::set с таким предикатом не будет автоматически переупорядочивать его элементы.

Answer 2

Когда используешь std::set появление двух или более элементов на общем значении y не должно быть проблемой, если вы используете подходящий компаратор для std::set, Я бы предложил, кроме значения y, сравнить и отсортировать по уклону. (Пример компаратора для std::set)

Я бы предложил не использовать для этого std::set, а что-то вроде std::vector. Использование std:: vector позволяет вам поменять (std::swap) ссылки на определенные сегменты линии, а также вставить / удалить за O(log n) время, если сегмент строки начинается / заканчивается, где n - количество сегментов линии. Идея состоит в том, что вы сами сохраняете правильный порядок статуса на протяжении всего цикла линии, меняя сегменты линии, которые соответствуют пересечению, только очередь событий является приоритетной. (Удалено из-за комментария @Sneftel, спасибо за понимание.)

Относительно вашего общего подхода к алгоритму стреловидности: статус (sweep line status) действительно представляет порядок отрезков линии в определенное (текущее) время в вашей строчке. Для статуса линии развертки, в моем понимании, следует использовать сбалансированное двоичное дерево (как упомянуто @Sneftel). Затем вы можете самостоятельно поддерживать правильный порядок статуса в течение всего цикла, меняя сегменты линии, которые соответствуют пересечению, только event queue должна быть какая-то очередь с приоритетами.

Answer 3

Напишите функцию сравнения, чтобы основная сортировка была по y, а младшая по x. Затем вы можете вставить сегменты с дублирующимися значениями y, если х отличается. (Если у вас есть два одинаковых сегмента, вам все равно нужно обращаться с ними специально для тестирования пересечений).