NetTopologySuite/NetTopologySuite — pull request #14 by airbreather (2014-10-24 11:37:04+00:00)
Title: CascadedPolygonUnion Performance Improvement

JTS's version of CascadedPolygonUnion puts everything into an STRTree with a maximum node capacity of 4, and then unions up each node separately. That way, each step of the cascaded union handles unioning together up to 4 polygons at a time, all of which are "close" to one another.

As of de89f7c, NTS now puts all the polygons into one big list and unions each half of the list recursively, using STRTree only as a means of sorting the list. This often causes the earlier rounds to remove fewer vertices than JTS would, leaving later rounds to have to deal with more complex polygons than otherwise.

On my machine, this change makes unioning tl_2014_06_tract.zip from ftp://ftp2.census.gov/geo/tiger/TIGER2014/TRACT/ go from 358.6 seconds to 331.9 seconds. Admittedly not as dramatic as I'd hoped, but still a noticeable improvement, and it's more like the way that JTS does it.