Opened 10 years ago
Closed 5 years ago
#702 closed defect (worksforme)
OverlayOp takes over 20 minutes on polygon with over 1M holes
| Reported by: | strk | Owned by: | |
|---|---|---|---|
| Priority: | major | Milestone: | 3.8.0 |
| Component: | Default | Version: | 3.4.2 |
| Severity: | Unassigned | Keywords: | |
| Cc: |
Description
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.
Change History (9)
comment:1 by , 10 years ago
comment:2 by , 10 years ago
NOTE: the test I was running could have been also affected by a PostGIS issue: http://trac.osgeo.org/postgis/ticket/2933#comment:8
comment:6 by , 6 years ago
| Milestone: | 3.6.3 → 3.8.0 |
|---|
comment:7 by , 5 years ago
strk, do you still have these inputs after 5 years, and do you want to see if there is an improvement following this: https://github.com/libgeos/geos/pull/141 ?
comment:8 by , 5 years ago
| Summary: | OverlayOp takes mover 20 minutes when a polygon with over a million holes is involved → OverlayOp takes over 20 minutes on polygon with over 1M holes |
|---|
comment:9 by , 5 years ago
| Resolution: | → worksforme |
|---|---|
| Status: | new → closed |
Lacking repro inputs I'm closing for how.
I was thinking that a generic speedup for "intersection" could be to restrict topology building to the extent resulting from the intersection of bounding boxes of the source geometries.