BuildArea is slow when there are many holes

[strk]

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 ?

[mdavis]

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.

[strk]

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 ?

[strk]

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

[Sandro Santilli <strk@…>]

In 2a8d882/git:

Use custom rings comparator in BuildArea

References #1122 in main branch (3.11.0dev)

[Sandro Santilli <strk@…>]

In da8ebd0/git:

Use custom rings comparator in BuildArea

References #1122 in 3.10 branch (3.10.2dev)

[Sandro Santilli <strk@…>]

In 4a91381/git:

Use custom rings comparator in BuildArea

Closes #1122 in 3.9 branch (3.9.3dev)