[geos-devel] JTS performance improvement for large polygons

[Martin Davis]

I've come up with a fairly easy update for JTS which eliminates the unecessary tests for ring self-intersection during spatial functions.  This will be shipped in the new version of JTS (although of course I can make it available for inclusion in GEOS at any time).

Note that this produces large gains for situations such as SineStar^2 for 255,000 points (a gain of 10x in performance).  However, the gains are less noticeable for small polygons (1000 points or less).  It also only matters if you actually have to test for intersections - if the polygons do not interact because their bounding boxes don't overlap, you of course don't see any improvement.

I've tested the new code in some practical situations involving testing many polygons for overlap, and it actually didn't make any difference. 

However, it's definitely good to tighten up the algorithm for the times it really is needed.

Martin Davis, Senior Technical Specialist
Vivid Solutions Inc.
Suite #1A-2328 Government Street   Victoria, B.C.   V8T 5G5
Phone: (250) 385 6040    Fax: (250) 385 6046
EMail: mbdavis at vividsolutions.com  Web: www.vividsolutions.com