Opened 4 years ago
Closed 19 months ago
#1030 closed enhancement (fixed)
Retain order of inputs in GEOSVoronoiDiagram
Reported by: | dbaston | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | 3.11.0 |
Component: | Default | Version: | main |
Severity: | Unassigned | Keywords: | |
Cc: |
Description
Some discussion at https://github.com/r-spatial/sf/issues/1371
One idea from the linked thread is to return cells in the order of the input points only for the case where no points are duplicated, and to not worry about it otherwise.
I'd propose to implement this behavior for GEOSVoronoiDiagram and, if there is a substantial performance penalty, then to expose it as a separate GEOSOrderedVoronoiDiagram instead.
Change History (8)
comment:1 by , 4 years ago
comment:2 by , 4 years ago
We could track the creation order of the QuadEdges, though. Haven't tried it but seems possible. Even absolute worst solution in GEOS (PIP) has to be more efficient than each client library implementing this on their own.
comment:3 by , 4 years ago
No need for PIP. Generated Voronoi polygons (in JTS at least) have their site coordinate attached as userData. Code here.
comment:4 by , 4 years ago
It's a little uglier in GEOS because a Geometry's userData needs to have a clear owner (and it cannot be the Geometry)
Performance hit seems to be about 25% although the reordering only accounts for 3% in a callgrind profile.
comment:5 by , 4 years ago
Milestone: | 3.9.0 → 3.10.0 |
---|
comment:8 by , 19 months ago
Resolution: | → fixed |
---|---|
Status: | new → closed |
Would be nice to do this, if it's not too expensive. The reason for the lack of matching order is that the Voronoi is generated off the Delaunay Triangulation graph, which has no concept of ordering.
One way to do it is to make a map(point, voronoi poly) and then read from that in the order of the input points. This should not be much extra overhead relative to the Voronoi computation time.