轮廓绘制算法

Question

我的妻子给了我这个任务，所以这是最重要的事情 :-)

我有一组点（实际上是北坐标和东坐标，但并不重要）。我想把这些点转换成代表轮廓的向量集，以便在Google Earth上绘制。

因此，类似于：

  #                       #
           #             #       #
#             #    #
      #   #

            #

会给予：

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

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

算法只需要运行几次，所以如果每次运行需要花费一小时和大量RAM也不是问题。

- Neil

---

好问题。你可能会从http://programmers.stackexchange.com或http://math.stackexchange.com获得更好的回答。 - Fogmeister

为什么选用那种形状？为什么不画出这些点的凸包？ - Chowlett

@Chowlett 就把那个作为答案吧；我正要提到用这些点可以制作几种“坚固”的形状。 - user1207456

你可以尝试查找凸包算法，链接为http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2 - sasha sami

Answer 1

候选多边形的制定

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

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

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

凸包？

一个目标函数可以是“在这些多边形中选择顶点数量最少的一个”。那就是你的点集的凸包。其他答案涉及该方法，所以我不再赘述。

更多内容...

但这不是你唯一可以选择的目标函数。例如，你可以选择在顶点数量、总面积和顶点角度不太锐利之间权衡。我不知道任何现有的命名算法解决这个问题，但这绝对是一个有趣的问题。

一种方法可能是首先找到凸包，然后在成本超过拥有更少的总面积的好处的内部顶点处“拉进”边缘。

例如，这个：

通过拉伸顶部的边缘，会变成这样：

尽管它不是点集的凸包，但这个第二个多边形可能更符合该点集。

- Timothy Shields

---

对于一个二维点集，你所描述的“凹”壳可以通过alpha形状找到。 - Cyril

Answer 2

您可能正在寻找点的凸包；有多种算法可以找到它。请参考Convex Hull Algorithms了解更多信息。

- Chowlett