Трапецеидальная декомпозиция многоугольника в C++

Question

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

Я нашел нечто подобное, реализованное в Python здесь:https://deparkes.co.uk/2015/02/05/trapezoidal-decomposition-polygons-python/.

Есть ли способ сделать это на C++?

Учитывая список точек (x, y) (std::vector), затем верните список трапеций (точек).

Answer 1

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

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

1. Преобразуйте все ребра в направленные ребра (у них должно быть направление, чтобы вы могли правильно обрабатывать отверстия)
2. Отсортируйте ребра по увеличению минимальной координаты x (вы также можете сделать это по y, но если предположить, что x увеличивается слева направо на вашей диаграмме, это правильный выбор для вашего случая). Для ребер с одинаковой минимальной координатой x используйте координату y, чтобы упорядочить их. Например, на диаграмме, которую вы показали, похоже, что они отсортированы сверху вниз. Увеличение или уменьшение y зависит от вашей системы координат.
3. Установите линию сканирования на первую вершину и введите ребра, которые касаются линии сканирования.
4. Продвиньте линию сканирования к следующей вершине. Обычно полезно сохранить значение предыдущей строки развертки доступным.
5. Выпускайте любые трапеции. Все излучаемые трапеции будут находиться между предыдущей строкой сканирования и текущей. И вершины будут там, где текущая или предыдущая линия сканирования пересекаются с краем.
6. Удалите все края, которые теперь находятся слева от линии сканирования. (Например, на диаграмме, когда линия сканирования находится в вершине 2, вы должны удалить ребро из 0-2)
7. Слияние любых новых ребер.
8. Пока остаются края, перейдите к шагу 4.

Здесь я опускаю некоторые неудобные детали. Вам может понадобиться "сетка" выходных трапеций в зависимости от вашего приложения, и вы должны быть очень осторожны с частями вычислений с плавающей запятой.

Если вы можете найти код, выполняющий растеризацию полигонов, его часто можно адаптировать для этого. В этом случае вы изменяете код для вычисления пересечений ребер в каждой координате x или y только в вершинах. Еще одно место, где можно поискать, — это пакеты EDA с открытым исходным кодом. Этот алгоритм необходим для подготовки данных о дизайне чипа для подготовки маски, но, поскольку вы использовали термин «трещина», возможно, вы уже это знали ;-)