At work I encountered the use of gaiaUnaryUnion function to merge (union) polygons, and I wondered how it is
actually implemented, my guess was it must have built some kind of tree structure out of all the input polygons.
Let’s dive in to some code in GEOS:
So indeed, it uses a R-Tree to collect spatially neighboring polygons together and forms a tree! After the tree is built,
it is flattened out into a list (itemTree; needs to be verified), which is then thrown to unionTree() to do the real
Now let’s have a look of how unionTree is realized:
In conclusion, the implementation walks the tree in a depth-first fashion and merges geometries along the way
with a divide-and-conquer operation - binaryUnion(). So this is it! Conceptually it’s quite simple, isn’t it?!
to flatten a tree structure efficiently.
In a follow-up to this post, you might want to figure out how actually a R-Tree is implemented and how