Найти все полигоны в точках, используя MATLAB

Question

У меня есть набор точек на плоскости, и я хочу найти все выпуклые многоугольники, не включая точки внутри них.

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

На изображении строка a соответствует выпуклым многоугольникам размера 3. В то время как столбцы 1 и 2 показывают правильные примеры того, что я хочу, в столбце 3 показан треугольник, включающий в себя две точки, чего я не хочу.

Строки b и c показывают примеры полигонов размера 4 и 5.

b3 показывает пример невыпуклого многоугольника

Интересно, есть ли функция в MATLAB или любом другом языке или кто-то знает об алгоритме, который может это сделать?

Алгоритм может получать, кроме точек, размер полигонов для поиска, он будет возвращать все возможные правильные полигоны или пустые, если не содержит полигонов такого размера.

Я ценю помощь.

Answer 1

Шаг 1: Выполните триангуляцию Делоне-Точки.

Шаг 2:

• Для полигонов размером 3: получаются треугольники.
• Для полигонов размера 4: выберите любую пару треугольников, которые имеют два угла
• Для многоугольников размера 5: выберите любой многоугольник размера 4 и соедините его с треугольником, который разделяет ровно два угла

Answer 2

Вы можете попробовать наивное решение, если это возможно:-

1. выберите k точек для k стороннего многоугольника
2. применить к нему выпуклый корпус алогрита
3. если размер выпуклой оболочки равен k, то множество точек образуют искомый многогранник k.

Сложность времени:- O(2^N*N*logN)