Opened 5 years ago

Closed 7 weeks ago

#702 closed defect (worksforme)

OverlayOp takes over 20 minutes on polygon with over 1M holes

Reported by: strk Owned by: geos-devel@…
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 Changed 5 years ago by strk

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.

comment:2 Changed 5 years ago by strk

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:3 Changed 3 years ago by strk

Milestone: 3.4.33.6.1

Ticket retargeted after milestone deleted

comment:4 Changed 3 years ago by strk

Milestone: 3.6.13.6.2

Ticket retargeted after milestone closed

comment:5 Changed 2 years ago by strk

Milestone: 3.6.23.6.3

Ticket retargeted after milestone closed

comment:6 Changed 15 months ago by robe

Milestone: 3.6.33.8.0

comment:7 Changed 3 months ago by dbaston

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 Changed 8 weeks ago by pramsey

Summary: OverlayOp takes mover 20 minutes when a polygon with over a million holes is involvedOverlayOp takes over 20 minutes on polygon with over 1M holes

comment:9 Changed 7 weeks ago by pramsey

Resolution: worksforme
Status: newclosed

Lacking repro inputs I'm closing for how.

Note: See TracTickets for help on using tickets.