A Faster Way to Match Geometry in Grasshopper

Tree search beats normal search

Last week I showed you the problem I had.

Using Grasshopper to check 5,000 elements against 5,000 elements takes a long time. Even for Grasshopper.

My solution as I’ve hinted, is to use a data structure known as an RTree to speed this search up.

Let me show you how this actually works.

What is an RTree ?

The core idea behind an RTree is quite simple.

Instead of measuring the distance from every point to every other point, Grasshopper first builds a spatial index of the points. That index divides space into a hierarchy of locations.

When you query for the closest point, it rules out entire regions instantly and only does the precise distance calculation on the small set of candidates that are actually nearby.

The result turns a four hour search operation into seconds.

Instead of checking every point, an RTree allows the computer to eliminate hundreds of points immediately. This is the reason it drastically speeds up the operation.

Okay, so theoretically, this makes sense but how do we set this up ?

P.S. if you’re a paid member of CodedShapes, you have access to some real examples of how I have used these components.

Setting it up in Grasshopper

The plugin doing all the work here is LunchBox.

In it, it gives you a few components that creates an RTree and does the RTree searching.

All you have to do is feed in a list of search points to build the RTree.

Then use the RTree Closest Point component to search for the points within the RTree.

It's that simple. It doesn't seem like much with few points, but you'll notice the difference, the more points you feed in.

At 5000 points, an RTree search took 11ms while the regular closest point took 1.1s. That’s a 10x improvement with not much change to the script.

When I first saw this, it blew my mind.

Using an RTree to pair members

Okay, but what if you have curves and not points? Like my problem, I had 5,000 curves, not 5,000 points.

Well, if you have curves and want to make use of the speed of an RTree search, all you have to do is to find a point that best represents your curve.

This means, you can use the mid-point (or if you’re good with data structures, a list of points) that represent your curve. In my case, because things were mostly orthogonal using the mid-point was good enough.

Instead of a curve to curve search. It became a midpoint to midpoint search. And using RTrees made this operation very quick.

Using an RTree to find points within a distance

You can also use RTrees to find the closest points for a given distance. Especially if you know that you’ll have many results to whatever it is you’re searching.