I am writing code to detect whether a line (with multiple points, these lines have curves) is part of a road network. If there is a road with no way to get to it (basically isolated) I need to flag it.
See the below screenshot
While scanning through the road network, the isolated lines should be flagged.
My thoughts on a solution
UPDATE Jan 14th/2014:
Tt works! It is however WAY too slow. It takes 30 minutes to run!
I start by sorting from left to right. I then add the first item in the list to XYPoints "network" list/hashset. It checks every XYPoint of every line for a connection (same point), and then adds all its points to the "network" and remove it from the list of lines (since it's already been checked, no need to check it again).
If the polyline isn't connected to the main network, it will still be residing in my original list of all the roads at the end.
Okay, code snippet, I'll keep updating this as I make progress, feel free to add some thoughts:
while (true)
{
int numOflinesBeforeChecking = polylinez.Count;
for (int i = 0; i < polylinez.Count; i++)
{
//scan through each point of each polyline
foreach (XYPoints xyp in polylinez[i].XYpoints)
{
//bool foundAvertice = false;
if (listOfEndPoints.Contains(xyp))
{
//add them as endpoints
foreach (XYPoints verifiedXYs in polylinez[i].XYpoints)
{
listOfEndPoints.Add(verifiedXYs);
}
//add them to the network
for (var g = 0; g < (polylinez[i].XYpoints.Count - 1); g++)
{
mainHighwaylines.Add(new Line2D(polylinez[i].XYpoints[g], polylinez[i].XYpoints[g + 1]));
}
polylinez.RemoveAt(i);
break; //break out of scanning XYPoints of an individual line/road, hit this again!
} //end if
} //end foreach XYPoint loop
} //end for i loop
//clearly there are no more lines
if (numOflinesBeforeChecking == polylinez.Count)
{
break;
}
} //end infinite loop
//check for intersections here
//mainHighway Lines has been generated, now let's check them for intersections
while (true)
{
int numOflinesBeforeChecking = polylinez.Count;
for (var i = 0; i < polylinez.Count; i++)
{
//smallLines relates to each individual polyline, seperated into even smaller lines
List<Line2D> smallLines = new List<Line2D>();
for (var g = 0; g < (polylinez[i].XYpoints.Count - 1); g++)
{
smallLines.Add(new Line2D(polylinez[i].XYpoints[g], polylinez[i].XYpoints[g + 1]));
}
bool intersectionFound = false;
foreach (Line2D line in smallLines)
{
bool lineIntersection = false;
foreach (Line2D mainHighwayline in mainHighwaylines)
{
if (line.intersectsLine(mainHighwayline))
{
intersectionFound = true;
lineIntersection = true;
break;
}
}
if (lineIntersection)
{
break;
}
}
if (intersectionFound)
{
for (var g = 0; g < (polylinez[i].XYpoints.Count - 1); g++)
{
mainHighwaylines.Add(new Line2D(polylinez[i].XYpoints[g], polylinez[i].XYpoints[g + 1]));
}
polylinez.RemoveAt(i);
}
}
//clearly there are no more lines
if (numOflinesBeforeChecking == polylinez.Count)
{
break;
}
}
What I need
Improvements on how to make this faster! The second infinite loop takes most of the time.
The second infinite loop with a break checks to see if there's intersections (they might not have shared end points, they might just intersect). I keep it in an infinite loop in case there's new data added.
Making the second major loop (checking for intersection loop) infinite with an if statement makes it go from 6 minutes to 30. However it is necessary to catch certain false positives.