大纲绘图算法

Question

我的妻子给了我这个任务,所以这是头等大事:-)

我有一系列积分(实际上是Northings和Eastings,但这并不重要).我想取这些点并创建一组代表轮廓的矢量,这样我就可以在Google地球上绘图.

所以,像:

  #                       #
           #             #       #
#             #    #
      #   #

            #

会给:

  #-----------------------#--
 /                            \ --#
#                  #------------/
 \-----#         /
         \     /
            #

我想出的一个可能的解决方案是计算每个点之间的向量,并丢弃与另一个向量重叠的每个向量.我还没有实现这个(不太确定如何),但我想知道是否还有其他方法.

该算法只需要运行几次,所以如果每次运行需要一个小时,那么RAM就不是问题.

Answer 1

候选多边形的制定

看起来你正在寻找一个多边形

• 它的所有顶点都在你的点集中
• 它包含点集中的每个点

这定义了一组与点集相关的可行候选多边形.

凸壳？

一个目标函数可以是"在这些多边形中,选择具有最小顶点数的那个".这将是你的点集的凸包.其他答案解决了这种方法,所以我不会再说什么了.

还有更多......

但这不是您可以选择的唯一目标函数.例如,您可以在具有较少顶点,具有较小总面积和在顶点处具有较不尖锐的角度之间进行权衡.我不知道该问题的任何现有命名算法,但它绝对是一个有趣的算法.

一种方法可能是通过寻找凸包开始,然后"拉"边缘的位置内部顶点,其中额外的顶点的费用是由具有较少总面积的好处抵消.

例如,这个:

通过沿着顶部拉边缘将成为这个:

这个第二个多边形可能是一个更"自然"的点集,即使它不是点集的凸包.