algorithm - 轮廓绘图算法

Question

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

我有一组点（实际上是 Northings 和 Eastings，但这并不重要）。我想获取这些点并创建一组代表轮廓的向量，这样我就可以在 Google 地球上绘图。

所以，像：

  #                       #
           #             #       #
#             #    #
      #   #

            #

会给：

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

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

该算法只需要运行几次，因此如果每次运行需要一个小时并且需要大量 RAM，这不是问题。

Answer 1

候选多边形的制定

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

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

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

凸壳？

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

还有什么...

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

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

例如，这个：

会变成这样，通过沿顶部拉动边缘：

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

Answer 2

您可能正在寻找点的凸包；有多种算法可以找到它。