#1122 closed enhancement (fixed)

BuildArea is slow when there are many holes

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


See https://trac.osgeo.org/postgis/ticket/4966

This merge request seems to make things much faster (x17): https://gitlab.com/geos/libgeos/-/merge_requests/3

Even, comments ?

Change History (7)

comment:1 by mdavis, 22 months ago

As noted in the code, this line is going to be very slow, since it uses topological equals:

   if( f2er->equals(hole) ) 

I am dubious about the correctness of checking only a single point to decide if the rings are equal (as suggested in the GitLab merge request 3.)

This can be improved by using a custom ring equality comparison function. The rings are equal iff they contain the same points, possibly rotated. So the function can first compare the envelopes, and then find the lowest point in each ring, and then walk the rings comparing their points.

comment:2 by strk, 22 months ago

Indeed a single point doesn't help, looks like rings are not even returning necessarely with the *same* starting point. I think I remember having seen a function comparing possibly rotated points, but dunno where (in GEOS, I mean). Would rather not re-implement if it's already available. Do you recall any such thing Martin ?

comment:3 by strk, 22 months ago

I've ended up reimplementing it, could you check the merge request again please ? https://gitlab.com/geos/libgeos/-/merge_requests/3

comment:4 by pramsey, 19 months ago


comment:5 by Sandro Santilli <strk@…>, 19 months ago

In 2a8d882/git:

Use custom rings comparator in BuildArea

References #1122 in main branch (3.11.0dev)

comment:6 by Sandro Santilli <strk@…>, 19 months ago

In da8ebd0/git:

Use custom rings comparator in BuildArea

References #1122 in 3.10 branch (3.10.2dev)

comment:7 by Sandro Santilli <strk@…>, 19 months ago

Resolution: fixed
Status: newclosed

In 4a91381/git:

Use custom rings comparator in BuildArea

Closes #1122 in 3.9 branch (3.9.3dev)

Note: See TracTickets for help on using tickets.