我有一组 2D点。他们是 X，在一个标准的笛卡尔网格系统y坐标（在这种情况下， UTM区）。我需要找到那个点集$ P $孔pferably有一定能力来设置，发现这些小孔的算法的灵敏度。通常，这些点集非常密集，但有些可以少得多密集。

I have a set of 2d points. They are X,Y coordinates on a standard Cartesian grid system(in this case a UTM zone). I need to find the holes in that point set preferably with some ability to set the sensitivity of the algorithm that finds these holes. Typically these point sets are very dense but some can be much less dense.

它们是什么，如果有帮助的任何，是在该字段中的土壤已被采样的各种性能，人们在农业显然发现有用点。有时，这些点样品中有巨大的岩石或沼泽​​的地方或完整的小湖泊和池塘。

What they are, if it helps any, are points at which the soil in the field has been sampled for various properties that people in agriculture apparently find useful. Sometimes in these point samples there are giant rocks or swampy places or full on little lakes and ponds.

从点集，他们希望我找的凹多边形，大约定义了这些漏洞。

From the point set they want me to find the concave polygon that roughly defines these holes.

我已经写，发现外凹边界多边形，并允许他们设置灵敏度如何粗糙或平滑多边形是由算法所形成的算法。运行后，他们想找到漏洞并给他们一个凹多边形的孔，我想在某些情况下可能是凸的，但是这将是边缘情况不是普遍现象。

I already wrote the algorithm that finds the exterior concave boundary polygon and allows them to set sensitivity for how rough or smooth the polygon is that is formed by the algorithm. After that runs they would like to find holes and have those holes given to them as a concave polygon which I guess in some cases might be convex but that will be the edge case not the norm.

现在的问题是，我曾经听说过关于这个问题的是那些做了由天文学家谁想要发现空了的大口袋在太空中，我从来没有能够找到他们的论文之一，所示的实际算法的唯一报纸在他们作为以外的任何一个粗略的概念描述。

The problem is the only papers I have ever heard of on this subject are ones done by astronomers who want to find big pockets of emptiness out in space and I have never been able to find one of their papers with an actual algorithm shown in them as anything other than a rough conceptual description.

我曾尝试谷歌和各种学术文章搜索等，但我还没有发现多少是有用的，到目前为止。这使我怀疑也许有对这类问题的一个名字，我不知道它，所以我正在寻找错误的事情或东西？

I have tried Google and various scholarly paper searches etc. but I haven’t found much that is useful so far. Which makes me wonder if maybe there is a name for this kind of problem and I don’t know it so I am searching for the wrong thing or something?

所以之后，长篇大论的解释，我的问题是：有谁知道我应该寻找找到这个$ P $论文pferably具有明确的算法或是否有人知道一种算法，将做到这一点，他们可以点我也是？

So after that long winded explanation, my question is: Does anyone know what I should be searching for to find papers on this preferably with well defined algorithms or does somebody know an algorithm that will do this that they can point me to?

任何事情来帮助我解决这个问题将是非常有益的，并大大AP preciated，甚至只是正确的搜索短语，将打开了潜在的算法或论文。

Anything to help me solve this problem would be very useful and greatly appreciated, even just correct search phrases that will turn up the potential algorithms or papers.

这将实施将是语言的例子来自数学包什么 MATLAB或ASM，C，C ++，Python和Java或MathCAD的等将C＃，但没事的，只要这个例子没有在它的一些调用，去像 FindTheHole 等。其中， FindTheHole 未被定义，或者是专有的实现软件如的MathCAD 等的例子有很多的。

The language this will be implemented in will be C# but examples in anything from Mathematica packages to MATLAB or ASM, C, C++, Python, Java or MathCAD etc. would be fine so long as the example doesn’t have some calls in it that go to things like FindTheHole etc. Where FindTheHole isn’t defined or is proprietary to the implementing software e.g. MathCAD examples typically have a lot of that.

下面是两个例子的实际点集，一是密集和一个稀疏的地区他们，我需要找到：

Below are two examples of actual point sets, one dense and one sparse and the areas in them I would need to find:

推荐答案

Delauney三角可以帮助。它的属性，没有输入点是在三角任何外接圆的三角形内。正因为如此，孔边界点会被覆盖的孔变大/变宽的三角形连接。在你的情况下，三角测量将会有很多类似规模的三角形，而尺寸较大的一些三角形覆盖孔。大概它足以滤除较大的，并连接他们找到一个孔。

Delauney triangulation can help. It has property that no input point is inside the circumcircle of any triangle in triangulation. Because of that, hole boundary points will be connected by larger/wider triangles covering that hole. In your cases triangulation will have lot of triangles of similar size, and some triangles of larger size that cover holes. Probably it is enough to filter larger ones and connect them to find a hole.