[geos-devel] New performance test with 2 large geometrys

[Martin Davis]

I tried a slight variation of the original SineStar test (call it SineStarSquared).  It compares two SineStars, each with the same number of points. One sineStar is offset from the other by 50 units in the y direction.    This means that the number of actual intersections is constant.  With the indexing implemented in JTS the expected performance is linear (and this is in fact what happens, I'm happy to say).  (Note that an implementation with poor or no indexing could have time of O(n^2), however.)

Here's the timings.  They're only 50% slower than the original SineStarBox test, which is pretty good.

n Pts: 1000   Executed in 2804 ms
 n Pts: 2000   Executed in 60 ms
 n Pts: 4000   Executed in 120 ms 
n Pts: 8000   Executed in 210 ms 
n Pts: 16000   Executed in 401 ms 
n Pts: 32000   Executed in 661 ms 
n Pts: 64000   Executed in 1421 ms 
n Pts: 128000   Executed in 2644 ms 
n Pts: 256000   Executed in 5307 ms

(Yury: to implement this simply replace the line
    Polygon box = GeometryTestFactory.createBox(fact,0,0,1,100.0);
with
    Polygon box = GeometryTestFactory.createSineStar(fact, 0.0, size/2, size, armLen, nArms, nPts); 
)

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