Getting to Know Your Neighbors – Quickly
Visio’s SpatialNeighbors property is useful for finding shapes that are nearby other shapes or that overlap other shapes. It can be used to programmatically answer the question “What did I drop my shape on top of?”.
Unfortunately, the SpatialNeighbors property can be extremely slow under certain circumstances. In real world scenarios, searching might take anywhere from a second to over a minute. That’s unacceptable for developers who need to make frequent calls to the method. Two factors can significantly alter the performance of the method.
First, searching group shapes is much slower than searching non-group shapes. This has to do with the way that SpatialNeighbors defines containment. Shape A is contained within Group Shape B if A is contained within the union of all the sub-shapes of B. Thus a lot of work is done to calculate that union before any relationship determination is made. It may not be possible to eliminate groups, but it is always helpful to performance to minimize the number of sub-shapes as much as possible. Also make sure to avoid nested groups. Opt instead for of a single group shape with many sub-shapes. Reducing the number of groups or shapes within groups can double or triple the performance of SpatialNeighbors.
That’s a decent improvement, but the second factor is even more important for performance. With each call to SpatialNeighbors, the developer must specify the Relation types they wish to detect. The four relation types are ContainedIn, Contain, Overlap and Touching. Any combination of types can be searched for. The problem is that Visio checks for each of these relationships individually and must redo all the analysis work described above every time. This leads to astronomic execution times.
The workaround here is to not specify the relation type at all. When passing in 0 for the Relation parameter, Visio makes several internal optimizations because it no longer cares about the particular way in which two shapes are related. For developers who don’t care about the relation type, passing in 0 is a couple orders of magnitude faster (100x) than passing in all the types. For those that really do need to find the shapes matching a particular relationship, call SpatialNeighbors passing in 0 to get a collection of candidate shapes. Then iterate through the collection and use the SpatialRelation property to get the relationship. This technique uses the really fast searching code to weed out all the shapes that are completely unrelated. The expensive code to determine actual relationships is then used with a much smaller set of shapes.