[geos-devel] Current project status

[Martin Davis]

So my take on the statistics below is that GEOS is now somewhat faster than JTS (at least, JTS before the self-intersection check speedup).  So we may be at the point of diminishing returns for increasing performance using the current algorithms.

The changes to incorporate the self-intersection check speedup are relatively minor - I think we should incorporate them now. I will send the code to Yury to port.

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


> -----Original Message-----
> From: Yury A. Bychkov [mailto:ybychkov at direct.ca]
> Sent: Sunday, November 24, 2002 2:59 AM
> To: geos-devel at geos.refractions.net
> Subject: [geos-devel] Current project status
> 
> 
> 1. RobustLineIntersector has been updated.
> 2. MonotoneChainIndexer::getChainStartIndices was a biggest 
> single contributor
> to Coordinate() calls (~20% of total calls). I've replaced instances
> CoordinateList with references to gauge performance increase 
> (See results
> below).
> 3. Currently I am redoing the CoordinateList (and calls to 
> its methods) with
> respect to the suggestions on the list.
> 
> Here are the performance results (P4-2.53):
> No modifications:
>  # overlapping MCs: 406
>  # segment intersection tests: 226
>  n Pts: 1000  Executed in     30 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 278
>  n Pts: 2000  Executed in     50 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 248
>  n Pts: 4000  Executed in    100 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 250
>  n Pts: 8000  Executed in    150 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 272
>  n Pts: 16000  Executed in    391 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 264
>  n Pts: 32000  Executed in    751 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 236
>  n Pts: 64000  Executed in   1513 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 264
>  n Pts: 128000  Executed in   3395 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 238
>  n Pts: 256000  Executed in   7120 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 232
>  n Pts: 512000  Executed in  12788 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 232
>  n Pts: 1024000  Executed in  25296 ms.
> 
> New RobustLineIntersector:
>  # overlapping MCs: 406
>  # segment intersection tests: 226
>  n Pts: 1000  Executed in     20 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 278
>  n Pts: 2000  Executed in     40 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 248
>  n Pts: 4000  Executed in     90 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 250
>  n Pts: 8000  Executed in    130 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 272
>  n Pts: 16000  Executed in    311 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 264
>  n Pts: 32000  Executed in    621 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 236
>  n Pts: 64000  Executed in   1252 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 264
>  n Pts: 128000  Executed in   2754 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 238
>  n Pts: 256000  Executed in   5688 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 232
>  n Pts: 512000  Executed in  10895 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 232
>  n Pts: 1024000  Executed in  22042 ms.
> 
> CoordinateList instances replaced with references in 
> MonotoneChainIndexer; some
> tweaking of CoordinateList:
>  # overlapping MCs: 406
>  # segment intersection tests: 226
>  n Pts: 1000  Executed in     20 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 278
>  n Pts: 2000  Executed in     30 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 248
>  n Pts: 4000  Executed in     70 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 250
>  n Pts: 8000  Executed in    120 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 272
>  n Pts: 16000  Executed in    270 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 264
>  n Pts: 32000  Executed in    500 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 236
>  n Pts: 64000  Executed in    991 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 264
>  n Pts: 128000  Executed in   2023 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 238
>  n Pts: 256000  Executed in   4276 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 232
>  n Pts: 512000  Executed in   7861 ms.
>  # overlapping MCs: 406
>  # segment intersection tests: 232
>  n Pts: 1024000  Executed in  15993 ms.
> 
> 
> Yury
> 
> 
> 
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel
>