Если у вас есть информация о подключении (например, у вас есть многоугольники, а не только точки), не так уж и сложно сделать достойную работу по сокращению многоугольников.
То, что я делал в прошлом, состояло из двух шагов.
Любая вершина, окруженная полигонами, все из которых являются копланарными, может быть удалена. Я сделал это путем «скольжения» вершины к соседней вершине, чтобы этот сосед получил все соседи тестовой вершины и все треугольники, которые становятся вырожденными (например, любые треугольники, общие для двух вершин).
Любая вершина, имеющая два ребра, выходящих друг против друга, где многоугольники с обеих сторон либо полностью отсутствуют, либо копланарны, также может быть аналогично свернута в соседнюю вершину, но, очевидно, только одну, которая находится вдоль одной из параллельные ребра.
примечание
Два многоугольника копланарны, если они имеют хотя бы одну общую точку и имеют одинаковую нормаль. Поскольку полигоны-кандидаты всегда присоединяются к вершине-кандидату, вам просто нужно сравнить нормали полигонов. Нормаль можно вычислить, взяв перекрестное произведение двух ребер многоугольника.