Opened 7 years ago

Closed 4 years ago

Last modified 4 years ago

#728 closed defect (fixed)

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

Reported by: rouault Owned by: geos-devel@…
Priority: major Milestone: 3.5.1
Component: Default Version: 3.4.2
Severity: Unassigned Keywords:
Cc: dbaston

Description

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.

Change History (13)

comment:2 by rouault, 7 years ago

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

comment:3 by rsbivand, 7 years ago

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

comment:5 by dbaston, 7 years ago

Cc: dbaston added

comment:6 by strk, 7 years ago

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

comment:8 by strk, 6 years ago

Milestone: 3.4.33.6.1

Ticket retargeted after milestone deleted

comment:9 by strk, 5 years ago

Milestone: 3.6.13.6.2

Ticket retargeted after milestone closed

comment:10 by strk, 5 years ago

Milestone: 3.6.23.6.3

Ticket retargeted after milestone closed

comment:11 by robe, 4 years ago

Milestone: 3.6.33.8.0

comment:12 by dbaston, 4 years ago

Resolution: fixed
Status: newclosed

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

comment:13 by robe, 4 years ago

Milestone: 3.8.03.5.1
Note: See TracTickets for help on using tickets.