Iterating through entities multiple times and performance

[Anonymous]

I have a situation where I need to check a DBText position vs other entities (check if DBText is clashing) then move the text position if required then do the same iteration check again. The way I check for text clash is similar to this article which involves exploding entities in memory sometimes.

Doing this in a drawing that has xrefs, Block references and other objects is very time consuming. And I typically have to do this for like 2000+ DBTexts.

So my question is, "what is the best way or ways to speed up the process?". I was thinking of iterating first time only and storing most results. But i'm not sure if this will speed things up or not.

Thanks in advance for your help

[ActivistInvestor · Accepted solution]

My guess is that spatial indexing is most-likely the best approach to solving your problem.

A quadtree can be used to spatially-index the bounding boxes of entities so that other entities that intersect with it can be found quickly. Most CAD software use quadtrees or its 3D analog, octrees, to search for objects when you select one by picking a point.

You can implement the quadtree in such a way that it can reference nested entities as well, although you will need to use something like a FullSubentityPath, or store the non-database resident entities produced by Explode() themselves in quadtree nodes in order to reference them.

Searching the internet for C# implementations might bear some fruit.

[dgorsman]

There's some similarity in processing points for Delaunay triangulation; sort based on execution method prior to evaluation so when they will logically generate a known result they can be skipped in all future loops.  Whatever method is chosen consider this: adding an additional item to consider results in an exponential increase in processing time, so removing items has the inverse effect, so reduce the number of items being cross-checked as soon as possible.

Don't forget about hybrid systems either: humans can be better at drawing layout than computers.  Let the computer do some of the heavy lifting with repetitive tasks but consider letting the user find the optimum locations.  While a completely automated system may be faster, the drawings can be rather ugly and end up needing manual clean-up anyways.

You might also want to delve into genetic algorithms.  It's a little daunting at first but well-constructed ones perform well where you have large numbers of objects of indeterminate nature.  They also perform better when a "good enough" solution is more acceptable than a potentially exhaustive search for multiple equally viable solutions (or no ideal solution is possible).  Due to the nature of how it works the results are usually not repeatable (run it on the same problem several times and you'll end up with several variations on the same solution but with few exact matches) but with very large sets that's not a primary concern.