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

[Martin Davis]

Ok, after refreshing my brain about the JTS algorithms I can now shed some light on the mystery of why there are so many calls to RobustDeterminant::signOfDet2x2 and SegmentIntersector SegmentIntersector::addIntersections.

Both of these have to do with the constraints that the very general OGC spatial model places on the developer.  The OGC SFS allows any orientation for the rings of a polygon.  It also allows the holes in a polygon to touch the polygon shell at points which are not nodes.  Because of this, the first step during the processing of relate(Geom, Geom) is to analyze each argument geometry to determine (a) what orientation its rings are, and (b) whether its rings self-intersect at points.  To do this, a lot of processing needs to be carried out!  

In particular: 
- isCCW is called on each ring - which calls signOfDet2x2 n times (for each pair of consecutive line segments)
- computeSelfNodes is called on each arg geometry - which calls addIntersections a whole bunch of times (n^2 times if you have a dumb algorithm, or in JTS on average a linear number of times due to the indexing.)

SO...  ain't no way out of this one, unless you can convince OGC to change their model.  Which they ain't gonna do, since they (rightly) want it to be general enough for all users.

The only way around these expensive tests is to cache the orientation and intersection information for each Geometry.  This makes sense if you have a storage format in which you can maintain this cached information.  There's tricky design issues here too - for instance, the number of self-intersections may be as many as O(n)!  Some people prefer the Geometry format to be as small as possible - others want it to be fast.  Can't do both...  

Attached is a listing from JTS which shows counts for intersection tests for the self-node tests and the relate tests.  As you can see, the self-node tests dwarf the relate tests.

Probably the real message here is that JTS has lived quite happily doing this all the time.  If GEOS is slower than JTS we have to look elsewhere for the cause.

===========================================
n Pts: 1000
computeSelfNodes: SegmentIntersector # tests = 4054
computeSelfNodes: SegmentIntersector # tests = 4054
computeIM: # segment intersection tests: 234
   Executed in 9473 ms
n Pts: 2000
computeSelfNodes: SegmentIntersector # tests = 8242
computeSelfNodes: SegmentIntersector # tests = 8242
computeIM: # segment intersection tests: 286
   Executed in 80 ms
n Pts: 4000
computeSelfNodes: SegmentIntersector # tests = 16626
computeSelfNodes: SegmentIntersector # tests = 16626
computeIM: # segment intersection tests: 257
   Executed in 140 ms
n Pts: 8000
computeSelfNodes: SegmentIntersector # tests = 33346
computeSelfNodes: SegmentIntersector # tests = 33346
computeIM: # segment intersection tests: 261
   Executed in 301 ms
n Pts: 16000
computeSelfNodes: SegmentIntersector # tests = 66866
computeSelfNodes: SegmentIntersector # tests = 66866
computeIM: # segment intersection tests: 273
   Executed in 500 ms
n Pts: 32000 computeSelfNodes: SegmentIntersector # tests = 133890
computeSelfNodes: SegmentIntersector # tests = 133890
computeIM: # segment intersection tests: 256
   Executed in 881 ms
n Pts: 64000 computeSelfNodes: SegmentIntersector # tests = 267906
computeSelfNodes: SegmentIntersector # tests = 267906
computeIM: # segment intersection tests: 240
   Executed in 1713 ms
n Pts: 128000
computeSelfNodes: SegmentIntersector # tests = 535914
computeSelfNodes: SegmentIntersector # tests = 535914
computeIM: # segment intersection tests: 268
   Executed in 3395 ms
n Pts: 256000
computeSelfNodes: SegmentIntersector # tests = 1071946
computeSelfNodes: SegmentIntersector # tests = 1071946
computeIM: # segment intersection tests: 240
   Executed in 6588 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