Slow C# algorithm needs enhancement when dealing with hundreds of objects (doesn't scale)

Question

We have code that reads in a DXF/DWG file (drawing file) and then our own geometry library that converts everything into point, line, arcs, circles, and etc. objects. Then we have a Shape object which will hold one or many entities. Shapes can also contain other shapes as children and those shapes can have children.

We have basic checks that do the typical checks like if an entity touches another entity or intersects it and are generally perform well so we haven't included that code here.

In the software when we load a drawing file we do the following:

1. Read in the file, consume the entities into objects
2. Up convert each entity into a shape object, circles are 1:1, lines and everything else get marked as 'Irregular' shape objects
3. Build an array of shapes / merge shapes by checking which entities 'touch' each other, so anything touching gets grouped into a single shape
   • simple checks like are first/last points the same
   • intersections
   • standard checks pulled out of geometry text books and other geometry libraries
4. Once we have a list of shapes we do parent/child analysis (right now it only goes one level deep) so instead of ending up with let's say a dozen shapes from a hundred entities we know some are shapes inside of a shape, so we may only have one true 'shape' in the drawing while other shapes are nested underneath it as children or we could have multiple shapes in a drawing that are not within each other

Overall it performed pretty good but once we added more complex drawings into the mix we realized some authors don't do single polylines but may have dozens or hundreds of lines in a drawing and then you could also have dozens or hundreds of circles showing cuts/holes in it. Then on top of that the average number of drawings the code deals with could be 10-30 files. So now we are seeing an average use case and the code not scaling to handle it and the step #2 is more of a brute force algorithm and can take 4+ seconds to run when there's hundreds of entities in a file. The algorithm / code mainly just looks at all entities and tries to identify which ones are touching which ones. I'm looking for ideas to improve the algorithm. I am trying to write more geometry focused code vs cad code, the cad code that reads the file is separate and just builds geometry to work with, then we go into geometry and do generic geometry work that isn't cad based but universal like hull analysis, total distances, want to also integrate with other open source libraries and leverage stronger analysis techniques on the drawing data and eventually even do image recognition which translates into geometry then back into cad by keeping libraries de-coupled.

It loops over all the entities checking if an entity touches (checking first/last points, intersection algorithms, standard geometry checks that are pretty quick), if so it adds it to the shape and keeps going then restarts all over again creating new shapes or adding to existing ones until it's passed over all the entities and all of the shapes made. And when creating shapes and looking at new entities, it loops all over the entities in the shape checking if they touch again so that's why it doesn't scale well and it's not the best piece of code.

Ignoring the 'touching' checks and all Invalidate does is update internals like length calculations and things like that, the issue is below.

Any suggestions on how to improve this algorithm for speed and efficiency when dealing with hundreds of entities?

        //we can end up with disjointed shapes, this scan keeps passing until we have no
        //more merges to try and perform every time we find a match we restart
        int idx = 0;
        uint kickout = 0;
        bool no_more = false; bool restart = false;

        //nothing at all?
        if (shapes.Count() <= 0)
            return shapes;

        do
        {
            int i = -1;
            Shape s1 = shapes[idx];
            if (s1.Entities.Count() > 0)
            {
                for (i = idx + 1; i < shapes.Count(); i++)
                {
                    Shape s2 = shapes[i];
                    if (s2.Entities.Count() > 0)
                    {
                        foreach (Entity e in s2.Entities)
                        {
                            if (s1.Touches(e))
                            {
                                //as a group, they all touch each other so they must
                                //all connect. Invalidate later (for speed)
                                s1.Add(s2);

                                s2.Clear(); //empty
                                shapes.Remove(s2); //empty from collection

                                restart = true;
                                break;
                            }
                        }
                    }
                }
            }

            //check next shape
            if (i == shapes.Count() || i == -1)
            {
                idx++;
                //idx %= shapes.Count(); //b/c we are manipulating contents
            }

            if (idx == shapes.Count() && !restart)
            {
                no_more = true;
            }
            if (idx == shapes.Count() && restart)
            {
                //re-pass, we have to keep going in case we missed a
                //joining segment/point
                idx = 0; restart = false;
            }

            //something went wrong here, don't freeze but we need to capture this
            kickout++;
            if (kickout + 1 == uint.MaxValue) //pretty high limit for checking
            {
                Debug.WriteLine("CRITICAL ERROR, OVERFLOW DETECTED IN SHAPE ANALYSIS!");
                throw new OverflowException("CRITICAL ERROR, OVERFLOW DETECTED IN SHAPE ANALYSIS!");
            }

        } while (!no_more);

Answer 1

First of all consider using Benchmark.NET for benchmarking your code. It could help you improve your performance and point out directly which parts are slow. It's very hard for us to point out one "slowest" place in your code, because we don't see all parts that could have influence. And even if you paste it here we can easily misjudge it. We're humans after all. That's why such library was created - to be sure.

But I have few "why" for code you pasted:

1. Why you keep checking if there is anything in 's2.Entities'? Loop is doing it for you.

2. Why Entities.Count() shapes.Count() are methods? It implies that those object implements IEnumerable, so when they're invoked IEnumerable actually iterates through all of elements and counts them, could be potential improvement. [REFERENCE]

3. What is the implementation of 'Touches' methods? It's one of the most crucial parts of the code because it's invoked many times. Even if you wrote that it's standard pulled out from the books and "generally perform well" doesn't mean that it performs well in this case.
4. Why are you clearing s2? Does it clear collection of entities? It could cause huge GC pressure. Benchmark.NET will help you discover that.
5. Why are you removing s2 from collection? Is it because it's merged into s1, so it's treated as one shape now, right? Remember that remove complexity could be O(n) (for List collection for example), because it has to 'find' correct shape to remove and while one shape can contain many other shapes it could case huge complexity during comparing one to another. You can easily return new List of shapes that are already merged.

6. Basically this code looks like you're trying to minimize shapes count by merging those that are 'touching eachother'. By 'touching eachother' I mean shapes that has, at least, one entity that touches our shape. If I'm not mistaken we can write it like this:

   public List<Shape> MergeShapes(Shape[] shapes)
   {
       var mergedShapes = new List<Shape>(shapes.Length); // my assumption also preallocating size of list to minimize resizing
       var alreadyMergedShapesIndices = new HashSet<int>();
   
       for (int i = 0; i < shapes.Length; i++) // you applied indexing on shapes variable that's why I assumed it's an array
       {
           if (alreadyMergedShapesIndices.Contains(i)) // my assumption after seeing shapes.Remove(s2) we don't want to merge into shape that was already processed.
           {
               continue;
           }
   
           var shapeToMergeInto = shapes[i];
   
           for (int j = i + 1; j < shapes.Length - 1; j++)
           {
               var shapeToVerify = shapes[j];
   
               if (shapeToVerify.Entities.Any(e => shapeToMergeInto.Touches(e)))
               {
                   shapeToMergeInto.Add(shapeToVerify);
                   alreadyMergedShapesIndices.Add(j);
               }
   
               j++;
           }
   
           mergedShapes.Add(shapeToMergeInto);
       }
   
       return mergedShapes;
   }
   

Please don't consider code in my answer as the fastest possible solution for your problem. It's just my attempt to make it more readable and to be sure that I understood algorithm correctly. The only way to make any performance improvements is to benchmark your code, because you and your team understood how domain is represented, what collections are used.