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?
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?
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.
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: