从给定顶点求非自交多边形的边

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包ashape的函数alphahull获得了这个数组。但是在这个函数中，欧几里得距离被用来求点之间的距离，这在我的情况下是不适用的(因为我在考虑关于(lon，lat)的数据，所以我们可以在包distHaversine中使用geosphere距离函数)。当多边形具有多个顶点且形状复杂时，该函数给出了不满意的结果。这个多边形可能是凸的，也可能不是凸的。

现在我要做的就是建立一个算法，用最小面积来寻找非相交多边形的边。

如能在这方面提供任何帮助，我们将不胜感激。

Answer 1

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

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

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

​

​

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

​

​

Answer 2

1. 将点从lon,lat转换为笛卡尔x,y或x,y,z

- use spherical or ellipsoidal surface
- if the size is small enough you can project (x,y,z) to local surface plane to avoid 3D computing
- you can also use `lon,lat` as `x,y` but make sure there is no zero crossing (if is then offset that axis by some value until it isn't)

​

1. 现在有很多可能的策略

- you did not provide any rule for the shape
- so I assume 'minimal' **perimeter/size/area** and generic **concave** polygon
- you can not go directly to edge lines before you know where is inside and where is outside
- I would do this task like this: [find polygon](https://stackoverflow.com/a/22295680/2521214) based on [find holes](https://stackoverflow.com/q/21816562/2521214) in 2D point set

​

1. 修改1

- as you already have all the edge points (at least that is my impression)
- so you can make flag for each point from the above algorithm
- that will tell you where is inside or outside of polygon
- for example take 8 directions (N,NE,E,...) and encode which way is filled and which empty
- then on each edge start in the middle of empty direction
- and find 2 closest lines to it (in angular terms) that are not intersecting any previous line
- and if more available use the smallest ones
- ​

​

- gray means inside polygon
- make list of all such possible lines (2 per point)
- then search for connected loops
- beware this modification is not 100% error prone (I do not think that is for concave polygon even possible)

​

1. 修改2

- use complete polygon from bullet 2
- and try to match its edge points to your input edge points
- then use the edge lines as in original polygon but with your new points
- if some points are skipped then find closest edge line to it and divide it by this point
- this should be more safe and accurate then bullet 3.

​

简单方法

• 如果上面的内容对你来说太过分了

1. create list of all possible lines
2. sort them by size ascending
3. remove all 'long' lines that are intersecting any 'short' line  
    - what is short or long depends on you
    - for example first third of lines can be the short ones and the last third the long ones
    - or make average size and what is `< 0.6*avg_size` or `> 1.2*avg_size` ...
    - or if you have N points then first 2N lines are short the rest is long (2 lines per point)
    - test all and select the best option for you  ...

​

1. try to find joined lines  
    - find only lines that are connected once (no more then 2 lines per point)
    - remove them from list into the final solution list
    - after this you will have list of possible lines and list of found lines

​

1. remove all lines from possible lines that intersect any line in found lines  
    - this should remove any non relevant lines

​

1. try to find connections again  
    - take first possible line if found connection move it to the solution list
    - and go to bullet 5.
    - if none found continue with next line ...
    - stop if none line left or none connection found.

​

​