Opened 22 months ago
Closed 19 months ago
#1122 closed enhancement (fixed)
BuildArea is slow when there are many holes
Reported by: | strk | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | 3.9.3 |
Component: | Default | Version: | 3.9.0 |
Severity: | Unassigned | Keywords: | |
Cc: | rouault |
Description
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 , 22 months ago
comment:2 by , 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 , 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 , 19 months ago
Milestone: | 3.9.2 → 3.9.3 |
---|
As noted in the code, this line is going to be very slow, since it uses topological
equals
: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.