使用MATLAB查找点中的所有多边形

Question

我在飞机上有一组点,我想找到所有凸多边形而不包括它们内部的一个点.

例如,我想找到所有三角形,所有四个大小的多边形,所有四个五个大小的多边形,依此类推,直到可以找到它们而不包括它们内部的一个点.

在图像中,行a对应于大小为3的凸多边形.虽然第1列和第2列显示了我想要的正确示例,但第3列显示了一个三角形,其中包含两个点,我不想要它.

行b和c示出了尺寸为4和5的多边形的示例.

b3示出了非凸多边形的示例

我想知道MATLAB中是否有函数或任何其他语言,或者有人知道可以做到的算法.

除了点之外,算法可以接收要搜索的多边形的大小,它将返回所有可能正确的多边形,如果不包含该大小的任何多边形,则返回空.

我很感激帮助.

Answer 1

步骤 1：对点执行 Delaunay 三角测量。

第2步：

• 对于大小为 3 的多边形：所得三角形就是结果。
• 对于大小为 4 的多边形：选取任意一对共享两个角的三角形
• 对于大小为 5 的多边形：选择任何大小为 4 的多边形并将其与正好共享两个角的三角形配对