[geos-devel] Why many calls to signOfDet2x2 and addIntersections

Martin Davis mbdavis at VividSolutions.com
Wed Nov 20 18:57:46 EST 2002


Just for grins, I disabled the self-intersection check and reran the SineStarX2 test.  Times are below - they are up to 10 times faster!

I've been thinking a bit about this annoying requirement to test for self-intersections before performing any functions.  Strictly speaking, this is only required for linestrings (which can self-intersect) and *between* different rings of polygons - but not between a ring and itself (OGC rings can't self-intersect).  Currently JTS just checks *everything* for self-intersections.  Since many cases involve only polygons without holes, being a bit smarter about what gets checked could produce a substantial performance improvement.

I'll spend some time thinking about how to change JTS to implement this.. It's not totally trivial, but might not be too bad.

===============================
n Pts: 1000
   Executed in 1352 ms
n Pts: 2000
   Executed in 20 ms
n Pts: 4000
   Executed in 10 ms
n Pts: 8000
   Executed in 30 ms
n Pts: 16000
   Executed in 50 ms
n Pts: 32000
   Executed in 100 ms
n Pts: 64000
   Executed in 100 ms
n Pts: 128000
   Executed in 221 ms
n Pts: 256000
   Executed in 411 ms

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




More information about the geos-devel mailing list