[geos-devel] [GEOS] #702: OverlayOp takes mover 20 minutes when a polygon with over a million holes is involved

[GEOS]

#702: OverlayOp takes mover 20 minutes when a polygon with over a million holes
is involved
------------------------+---------------------------------------------------
 Reporter:  strk        |       Owner:  geos-devel@…              
     Type:  defect      |      Status:  new                       
 Priority:  major       |   Milestone:  3.4.3                     
Component:  Default     |     Version:  3.4.2                     
 Severity:  Unassigned  |    Keywords:                            
------------------------+---------------------------------------------------
 I've been looking at a huge polygon having over a million small holes and
 a large extent, and saw ST_Intersection between it and a rectangle take
 around 26 minutes.

 Implementing a quick short-circuit based on analyzing each hole in turn
 for it being in-or-out of the rectangle can take the time down to 5
 seconds.

 As of the new rectangle intersection optimization code (#699) I've seen
 the same intersection take around 1 second.

 This ticket is to find out if there's anything that could be optimized in
 GeometryGraph building with these kind of inputs.

-- 
Ticket URL: <http://trac.osgeo.org/geos/ticket/702>
GEOS <http://geos.refractions.net/>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).