Блог

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

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

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

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

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

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

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

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

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