[geos-devel] [GEOS] #982: Postgis ST_ConcaveHull Runtime GEOS Problem?

[GEOS]

#982: Postgis ST_ConcaveHull Runtime GEOS Problem?
------------------------+---------------------------
 Reporter:  tsw         |       Owner:  geos-devel@…
     Type:  defect      |      Status:  reopened
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.7.0
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Now that I've looked at the data in this test case, I can see that this
 dataset is absolutely a worst-case scenario for union.  The reason is that
 there are so many intersections between the lines, it is going to produce
 on the order of O(n^2) node points.  This means the noding process has to
 run in slow O(n^2) time.  Also, memory usage is going to be very large.

 So this is an example of where using Union within the Concave Hull
 algorithm is not a good idea.

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