GEOSDelaunayTriangulation() utterly slow on big point cloud (133 000 points)

[rouault]

GEOSDelaunayTriangulation() doesn't complete in a reasonable time (I stopped it after ~ 15 minutes) when run on the multipoint aggregating all the points of the attashed shapefile. On the contrary,QHull Delaunay triangulation completes in less than one second.

[rouault]

Link is ​http://even.rouault.free.fr/delaunay_input.shp.zip

[rsbivand]

There are 3 dimensions in the shapefile. Using two dimensions only, R deldir::deldir completes in 444 seconds on my laptop, but does this make sense, given that the points are in geographical coordinates? Does Qhull use GC distances - I don't think so, nor does GEOS - is this just a test case?

> bbox(out)
                min          max
coords.x1 145.77283   216.073340
coords.x2 -78.36998    -7.316789
coords.x3  -4.00000 10632.000000

[dbaston]

Possible explanation: ​https://github.com/postgis/postgis/pull/73#issuecomment-158551270

[strk]

Evan if you could re-test it would be great.

[strk]

The proposed branch to test: ​https://github.com/libgeos/libgeos/pull/55

[strk]

Ticket retargeted after milestone deleted

[strk]

Ticket retargeted after milestone closed

[strk]

Ticket retargeted after milestone closed

[dbaston]

I'm pretty confident this was resolved by the linked pull request.