Opened 2 years ago
Closed 2 years 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 , 2 years ago
comment:2 by , 2 years 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 , 2 years 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 , 2 years 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.