轮廓图绘制算法 [英] Outline plotting algorithm

问题描述

我的妻子已经把我的任务交给了我，所以这是当务之急:-)

I've been given this task by my wife, so it's top priority :-)

我收集了一些要点(实际上是Northings& Eastings，但这并不重要).我想把握这些要点，并创建一组代表轮廓的矢量，以便在Google地球上绘图.

I have a collection of points (actually Northings & Eastings, but it doesn't really matter). I want to take those points and create a set of vectors that represent the outline, so I can plot on Google earth.

所以，像这样:

  #                       #
           #             #       #
#             #    #
      #   #

            #

会给出:

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

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

A possible solution I came up with, is to compute vectors between every point, and discard every vector that is overlapped by another vector. I haven't implemented this yet (not really sure how), but I wondered if there are other ways.

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

The algorithm only has to run a couple of times, so if it takes an hour per run and gigs of RAM it's not an issue.

推荐答案

候选多边形的形成

似乎您正在寻找的多边形如此

Formulation of candidate polygons

It seems like what you're looking for a polygon such that

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

这相对于您的点集定义了一组可行的候选多边形.

This defines a feasible set of candidate polygons with respect to your point set.

一个目标函数可以是在这些多边形中，选择顶点数量最少的多边形".那就是您的点集的凸包.其他答案解决了该方法，因此我不再赘述.

One objective function could be "Among these polygons, choose the one with the minimum number of vertices." That would be the convex hull of your point set. Other answers address that approach, so I won't say anything more about it.

但这不是您可以选择的唯一目标函数.例如，您可以在较少的顶点，较小的总面积和较小的顶点锐角之间进行权衡.我不知道有什么现有的命名算法可以解决这个问题，但这绝对是一个有趣的算法.

But that is not the only objective function you could choose. For example, you could instead have a trade-off between having fewer vertices, having less total area, and having less-sharp angles at vertices. I don't know of any existing named algorithms for that problem, but it's definitely an interesting one.

一种方法可能是先找到凸包，然后将边缘拉入"内部顶点的位置，在该位置中，额外顶点的成本因总面积较小的好处而被抵消.

One approach could be to start by finding the convex hull, then "pull in" edges to interior vertices in the locations where the cost of the extra vertex is outweighed by the benefit of having less total area.

例如，此:

通过沿顶部拉入边缘将成为这种情况:

Would become this, by pulling in the edge along the top:

第二个多边形对于点集可能更自然"，即使它不是不是点集的凸包.

This second polygon might be a more "natural" fit for the point set, even though it is not the convex hull of the point set.

这篇关于轮廓图绘制算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！