在2d点集找到漏洞？

Question

在2d点集找到漏洞？我有一套2d points。它们X,Y coordinates位于标准的笛卡尔网格系统上（在本例中为a UTM zone）。我需要在该点集中找到孔，最好能够设置找到这些孔的算法的灵敏度。通常这些点集非常密集，但有些可能密度低得多。它们是什么，如果它有帮助的话，那就是田地里的土壤被采样的点，农业人们显然发现它们有用。有时在这些点样品中有巨大的岩石或沼泽地或满是小湖泊和池塘。从点集中，他们希望我找到粗略定义这些孔的凹多边形。我已经编写了找到外部凹面边界多边形的算法，并允许它们设置由算法形成的多边形粗糙或平滑的灵敏度。在那之后，他们想找到洞并将那些洞作为凹多边形给予它们，我猜在某些情况下可能是凸的，但这将是边缘情况而不是常态。问题是我听过的关于这个问题的唯一论文是那些希望在太空中找到大空虚的天文学家完成的论文，我从来没有能够找到他们的一篇论文，其实际算法如下所示除了粗略的概念描述之外的任何东西我已经尝试了谷歌和各种学术论文搜索等，但到目前为止我还没有找到很多有用的东西。这让我想知道是否有这个问题的名字，我不知道所以我在寻找错误的东西或什么？所以经过那个冗长的解释，我的问题是：有没有人知道我应该寻找什么，最好用定义明确的算法找到这方面的论文，或者有人知道一个他们可以指向我的算法吗？任何帮助我解决这个问题的东西都会非常有用并且非常感激，即使只是正确的搜索短语，也会发现潜在的算法或论文。这将实现的语言将是C＃，但是从Mathematica软件包到其他任何东西的例子MATLAB or ASM, C, C++, Python, Java or MathCAD都可以，只要示例中没有一些调用类似于FindTheHole等等的东西。在哪里FindTheHole没有定义或者是对于实现软件而言是专有的，例如，MathCAD示例通常具有很多。

Answer 1

Delauney三角测量可以提供帮助。它具有在三角测量中任何三角形的外接圆内没有输入点的特性。因此，孔边界点将通过覆盖该孔的较大/较宽的三角形连接。在你的情况下，三角测量将有许多相似大小的三角形，以及一些覆盖孔的较大尺寸的三角形。可能它足以过滤较大的并连接它们以找到一个洞。

Answer 2

使用Delaunay三角测量法找到Gabriel图可能会更好。然后，您对Gabriel图进行角度排序，并进行圆形行走以生成凸多边形列表。然后，您可以按区域对这些多边形进行排序。你会对面积最大的那些感兴趣。

修改角度排序图表也可以更有效，您可以按照从A到B的路径，然后顺时针或逆时针（从角度排序）查看下一步。字典的词典可能是有用的，其定义类似于“图[A] [B] =（顺时针，逆时针）”。使用字典词典方法的示例算法（python）。

pre_graph = gabriel_graph(point)graph = {}for a in pre_graph:
    graph[a] = {}
    angle_sorted = sort(pre_graph[a], key=calc_angle_from(a))
    for i,b in enumerate(angle_sorted):
        clockwise = angle_sorted[(i - 1) % len(angle_sorted)]
        counterclockwise = angle_sorted[(i + 1) % len(angle_sorted)]
        graph[a][b] = (clockwise, counterclockwise)polygons = []for A in points:
    for B in graph[A]:
        for direction in [0,1]:
            polygon = [A]
            next_point = B:
            while next != A:
                polygon.append(next)
                next_point = graph[A][B][direction]
            if polygon[0] == min(polygon): # This should avoid duplicates
                polygons.add(polygon)

结合Ante的建议也可能有用。