Opened 12 years ago

Closed 12 years ago

Last modified 12 years ago

#545 closed enhancement (fixed)

Slow Polygonize operation with big polygon

Reported by: strk Owned by: geos-devel@…
Priority: major Milestone: 3.3.4
Component: Default Version: 3.3.3
Severity: Unassigned Keywords:
Cc:

Description

The attached XML test contains the hexwkb of a multipolygon composed by 9930 polygons and giving Polygonizer an hard time (30 seconds of operations).

gprof finds about half the time being spent in ::operation::polygonize::EdgeRing::isInList which is called by ::operation::polygonize::EdgeRing::findEdgeRingContaining and indeed the code seems to be optimizable (compute the bounding box of each ring rather than scanning it over and over again)

Change History (4)

comment:1 by strk, 12 years ago

Attachment didn't work, it's 1.6 MB... It's temporarily available here: ​http://strk.keybit.net/tmp/SlowPolygonize.hexwkb.bz2

comment:2 by strk, 12 years ago

There seems to be a bug in ptNotInList too ! I wonder how to trigger it, but ptNotInList seems to be returning a point _in_ the list rather than a point _not_ in the list!

comment:3 by strk, 12 years ago

Resolution: → fixed
Status: new → closed

r3628 in 3.3 branch and r3629 in trunk speeds this up to run in 4 seconds rather than 30 (~8x).

I've filed #545 for the possible bug spotted during profiling this.

in reply to:  3 comment:4 by Mike Taves, 12 years ago

Replying to strk:

I've filed #545 for the possible bug spotted during profiling this.

Correction: see #546

Note: See TracTickets for help on using tickets.