Detecting whether a line (with several points) is by itself, or connected to another line

Question

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.

Answer 1

A standard (,continuous) geometrical approach does not seem to be applicable here. From your picture, the roads are too intrincate (and thus very difficult or impossible to be replaced by just one line (or a bunch of them)) and the situation to be modelled (being part of the network) too imprecisely-defined, to rely on simplifications.

The only accurate-enough approach I can come up with for this problem is checking whether the given roads have common points with the main network or not.

Main ideas:

1. Storing all the points defining the main network; that is, all the points of each road forming part of it. This collection will be constantly updated with each new road decided to be part of the network (as explained in the point below).
2. Analysing each road by checking all their defining points and confirming whether they are part of the main network or not (eventually, by accounting for some "tolerance error"). A secondary collection will be started here where all the roads connected to the road being analysed will be included (once the analysed road is considered connected, all these secondary roads will automatically be considered connected too and vice versa).

Logically, this is an in-the-worst-scenario-possible approach; the more information you have, the more simplifications would be applicable and the less brute-force the calculations might become. But if your input data looks like the one in the picture, I wouldn't be too optimistic on this front.