algorithm - 轮廓绘图算法

Question

这个任务是我妻子交给我的，所以这是重中之重:-)

我有一个点集合(实际上是北距和东距，但这并不重要)。我想获取这些点并创建一组代表轮廓的矢量，这样我就可以在 Google 地球上绘制。

所以，像这样:

  #                       #
           #             #       #
#             #    #
      #   #

            #

会给出:

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

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

该算法只需运行几次，因此如果每次运行需要一个小时和几千兆的 RAM，这不是问题。

Answer 1

候选多边形的制定

看起来您正在寻找这样的多边形

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

这根据您的点集定义了一组可行的候选多边形。

凸包？

一个目标函数可以是“在这些多边形中，选择顶点数最少的那个”。那将是您的点集的凸包。其他答案解决了这种方法，所以我不会再多说什么了。

更多...

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

一种方法可能是从找到凸包开始，然后将边缘“拉入”到内部顶点，在这些位置额外顶点的成本被总面积较小的好处所抵消。

例如，这个:

通过拉动顶部的边缘会变成这样:

第二个多边形可能更“自然”地适合点集，即使它不是点集的凸包。