[geos-devel] [GEOS] #1122: BuildArea is slow when there are many holes

[GEOS]

#1122: BuildArea is slow when there are many holes
-------------------------+---------------------------
 Reporter:  strk         |       Owner:  geos-devel@…
     Type:  enhancement  |      Status:  new
 Priority:  major        |   Milestone:  3.9.2
Component:  Default      |     Version:  3.9.0
 Severity:  Unassigned   |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by mdavis):

 As noted in the code,
 [https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/operation/polygonize/BuildArea.cpp#L109
 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
 [https://gitlab.com/geos/libgeos/-/merge_requests/3 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.

-- 
Ticket URL: <https://trac.osgeo.org/geos/ticket/1122#comment:1>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).