#python #algorithm #math #computational-geometry
#питон #алгоритм #математика #вычислительная геометрия
Вопрос:
Я ищу способ триангуляции и заполнения внутренней части контура непростого (возможно, самопересекающегося) многоугольника. Я нашел несколько очень хороших алгоритмов онлайн для триангуляции простых кривых или нахождения выпуклой оболочки набора точек, но мне нужно найти контур списка точек, на который я не могу полагаться, что это кривая Джордана (без пробивания отверстий для каждого самопересечения, например, mapbox / earcut, делает)
Я попробовал использовать python-порт earcut от mapbox (https://github.com/joshuaskelly/earcut-python ) что здорово, но пробивает отверстия для самопересечений, которые я не мог попробовать scipy.spacial , так как он вообще не поддерживает непростые кривые.
Я провожу свои исследования на Python и планирую в конечном итоге перенести его на JavaScript, но пока я не зависим от языка, и подойдет любой алгоритм.
import earcut
from shapely.ops import cascaded_union
from shapely.geometry import Polygon
points = [[(0,0), (100,0), (100,50), (200,100), (0,100), (20,20), (80,20), (80,80), (20,80)],[]]
data = earcut.flatten(points)
flattrangles = earcut.earcut(data['vertices'])
alltriangles = [[points[0][j] for j in tr] for tr in triangles.T.tolist()]
cascaded_union([Polygon(tr) for tr in alltriangles])
Ожидаемый один большой многоугольник без отверстий
Есть многоугольник с двумя треугольными отверстиями, где самопересечения
Комментарии:
1. Было бы очень полезно, если бы вы могли опубликовать эскиз того, каким вы хотите получить результат, в сравнении с тем, что было бы нежелательным результатом. Я могу придумать только один однозначный способ заполнения самопересекающегося многоугольника, и он включает отверстия на самопересечениях, которые, как вы упоминаете, не являются тем, что вы хотите сделать…
2. @vlsd, я думаю, он имеет в виду это: en.wikipedia.org/wiki/Nonzero-rule
3. @MattTimmermans ненулевое значение — это то, о чем я думал (пока о четном / нечетном, спасибо!), Но даже тогда есть возможность «дыр», как показывает отличный визуальный пример в Википедии.
4. Если ваша цель действительно заполнить, нет необходимости в триангуляции. Вы можете использовать прямое заполнение полигонов с помощью правила четности или ненулевого значения.
5. @YvesDaoust: моя цель действительно в конечном итоге заполнить многоугольник, но я хочу выполнить триангуляцию для векторизации и рендеринга через opengl. Я могу написать алгоритм, который растрирует с использованием строки сканирования, но на самом деле предпочел бы хорошо протестированную библиотеку, которая делает это за меня, что касается отверстий, теперь я убежден, благодаря комментариям выше, что мне нужно переформулировать вопрос и искать ненулевую триангуляцию правил, и действительно не могу использоватьограничение «без отверстий», которое явно не определено. Я скоро отредактирую этот пост