Я ищу способ триангуляции и заполнения внутренней части контура непростого (возможно, самопересекающегося) многоугольника.В Интернете я нашел несколько очень хороших алгоритмов для триангуляции простых кривых или нахождения выпуклой оболочки набора точек, но мне нужно найти контур списка точек, на который я не могу полагаться, что он является кривой Джордана (без пробивки отверстий длякаждое самопересечение, как, скажем, mapbox / earcut, делает)
Я пробовал порт python для среза 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])
Ожидается один большой многоугольник без отверстий. Получен многоугольник с двумя треугольными отверстиями, где самопересечения