6

我在平面上有一组点，我想找到所有凸多边形而不包括其中的一个点。

例如，我想找到所有三角形、所有四个大小的多边形、所有四个五个大小的多边形等等，直到可以找到它们而不在其中包含一个点。

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

b和c行显示大小为 4 和 5 的多边形的示例。

b3显示了一个非凸多边形的示例

在此处输入图像描述

我想知道 MATLAB 或任何其他语言中是否有函数，或者是否有人知道可以做到这一点的算法。

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

我很感激帮助。

4

2 回答 2

2

第 1 步：对点执行 Delaunay 三角剖分。

第2步：

  • 对于大小为 3 的多边形：生成的三角形是结果。
  • 对于大小为 4 的多边形：选择任何一对共享两个角的三角形
  • 对于大小为 5 的多边形：选择任何大小为 4 的多边形，并将其与正好共享两个角的三角形配对
于 2014-02-18T08:12:23.633 回答
0

如果可行，您可以尝试简单的解决方案：-

  1. 为 k 边多边形选择 k 个点
  2. 对其应用凸包算法
  3. 如果凸包大小等于 k，则点集形成所需的 k 边多边形。

时间复杂度：- O(2^N*N*logN)

于 2014-02-18T09:23:34.837 回答