I have the following algorithm:
class CycleData : List<IntPoint>{
public IntPoint startPoint;
public Boolean ended=false;
public CycleData(IntPoint startpoint) { startPoint = startpoint; base.Add(startpoint); }
}
class GeoDataGraphPoint
{
private IntPoint point;
private List<GeoDataGraphPoint> connected = new List<GeoDataGraphPoint>();
private int generation=-9999;
public void AddConnection(GeoDataGraphPoint c)
{
connected.Add(c);
c.connected.Add(this);
}
public GeoDataGraphPoint(IntPoint point)
{
this.point = point;
}
public List<CycleData> GetCycles(int gen)
{
if (generation != -9999)
{
var r = new CycleData(point);
return new List<CycleData> { r };
}
generation = gen;
List<CycleData> res = new List<CycleData>();
foreach (GeoDataGraphPoint p in connected)
{
if (p.generation != gen-1)
{
res.AddRange(p.GetCycles(gen + 1));
}
}
foreach (CycleData list in res)
{
if (list.ended == false)
{
list.Add(point);
if (list.startPoint == this.point)
{
list.ended = false;
}
}
}
gen = -9999;
return res;
}
}
Now in principle this should return every cycle in the graph (for polygon detection). However it seems to fail to return anything in some occasions, I suspect that there is some kind of memory problem as removing parts of the graph sometimes causes new cycles to be found.
Here is a part of the input where it fails:
connection:(2282,3) to (2282,-192)
connection:(2282,3) to (2085,3)
connection:(2282,-192) to (2282,3)
connection:(2282,-192) to (2466,-192)
connection:(2466,-192) to (2282,-192)
connection:(2466,-192) to (2466,581)
connection:(2466,581) to (2466,-192)
connection:(2466,581) to (1494,581)
connection:(1494,581) to (2466,581)
connection:(1494,581) to (1494,397)
connection:(1494,397) to (1494,581)
connection:(1494,397) to (2282,397)
connection:(2282,397) to (1494,397)
connection:(2282,397) to (2282,187)
connection:(2282,187) to (2282,397)
connection:(2282,187) to (2085,187)
connection:(2085,187) to (2282,187)
connection:(2085,187) to (2085,3)
connection:(2085,3) to (2085,187)
connection:(2085,3) to (2282,3)
connection:(2085,3) to (2085,187)
connection:(2085,3) to (2282,3)
connection:(2085,187) to (2282,187)
connection:(2085,187) to (2085,3)
connection:(2282,187) to (2282,397)
connection:(2282,187) to (2085,187)
connection:(2282,397) to (1494,397)
The above code is for two triangles arranged to form a square (in coordinates) where both sides touch one another so like this:
Where I can the function as following:
class GeoDataGraph : Dictionary<IntPoint, GeoDataGraphPoint>
{
public void resetGens()
{
foreach(var v in base.Values)
{
v.generation = -9999;
}
}
public static Island GetHolesInIsland(Island input)
{
GeoDataGraph graph = new GeoDataGraph();
for (int i = 0; i < input.area.Count-1; i = i + 2)
{
var p1 = new IntPoint(input.area[i].X, input.area[i].Y);
var p2 = new IntPoint(input.area[i + 1].X, input.area[i + 1].Y);
if (!graph.ContainsKey(p1)) graph.Add(p1, new GeoDataGraphPoint(p1));
if (!graph.ContainsKey(p2)) graph.Add(p2, new GeoDataGraphPoint(p2));
graph[p1].AddConnection(graph[p2]);
}
IntPoint min = new IntPoint(int.MaxValue, int.MaxValue);
List<IntPoint> minCycle = null;
List<List<IntPoint>> cycles = new List<List<IntPoint>>();
while (graph.Count != 0)
{
var first = graph.First();
var NewCycles = first.Value.GetCycles(1);
graph.resetGens();
if (NewCycles.Count == 0)
{
graph.Remove(first.Key);
Console.WriteLine("point" + first.Key + "is uncycled");
}
cycles.AddRange(NewCycles);
foreach (var cycle in NewCycles)
{
foreach (var cycleNode in cycle)
{
graph.Remove(cycleNode);
if (min.X > cycleNode.X || min.Y > cycleNode.Y)
{
minCycle = cycle;
min = cycleNode;
}
}
}
}
cycles.Remove(minCycle);
if (minCycle == null) { minCycle = new List<IntPoint>();
foreach(IntPoint a in input.area) {
Console.Write(a);
} }
input.holes = cycles;
input.area = minCycle;
return input;
}
}
}
where Island contains.area contains a list of points ordered by connected pairs.
The basic algorithm is simple: take a node recursively visit every node connected to it until you detect a cycle, then return that node and append any node on the way out until you find the start of the cycle again. Once you have found every node connected to the start node remove the cycles (they since we checked every node connected to the cycle we shouldn't be deleting the once we already did) and start again on the next node, if a node contains no cycles remove it. I suspect something might be going wrong at this step but am unsure. Any idea what I'm doing wrong that causes a weird interdependence that causes seemingly unrelated polygons to go wrong?
