r - 从给定顶点查找非自相交多边形的边

Question

我在二维中有一个非自相交多边形的顶点，其中 x 坐标是居中经度，y 坐标是居中纬度。我想找到多边形的边。

我可以绘制顶点并查看哪些顶点相邻并查看边。但我的问题是如何获得这些优势。

比如我在考虑样本数据:

> data1
    vertices       lon      lat
       5         1.133179 1.027886
       4         1.094459 1.013952
       2         1.055672 1.000000
       1         1.000000 1.028578
       3         1.038712 1.042541
       6         1.116241 1.070438

点的样本图是

我想要一个这样的数组

>edges 
      ind1 ind2
[1,]    5    6
[2,]    1    3
[3,]    3    6
[4,]    1    2
[5,]    2    4
[6,]    4    5

我对这种多边形的形状很感兴趣(具有最小面积)

我通过使用 R 包 alphahull 的函数 ashape 得到了这个数组。但是在这个函数中，欧几里得距离用于计算点之间的距离，这不适用于我的情况(因为我考虑的是 (lon, lat) 上的数据，我们可以使用 distHaversine 包中的距离函数 地理圈)。如果多边形具有大量顶点且形状复杂，则此函数会给出不令人满意的结果。这个多边形可能是凸的，也可能不是。

现在我只想构建一个算法来找到具有最小面积的非相交多边形的边。

在这方面的任何帮助将不胜感激。

Answer 1

寻找所有可能的多边形的算法:

• 生成凸包。请注意，任何不相交的多边形都必须按顺序遍历其凸包。
• 从凸包上的任意点开始生成从该点到每个内部点以及到凸包上的下一个相邻点的路径列表
• 递归地将每条路径扩展到每个剩余的内部点以及凸包上的第一个自由点
• 对于添加到路径的每个段，如果路径自相交则拒绝该路径

我不打算发布代码，但这里有 8 个点的随机集合的所有 67 种可能的多边形。正如人们可以想象的那样，结果集随着点数的增加而迅速膨胀(例如 n=12 -> ~10000 个多边形..)

这里是具有最小和最大周长的多边形。