Retain order of inputs in GEOSVoronoiDiagram

[dbaston]

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.

[mdavis]

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.

[dbaston]

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.

[mdavis]

No need for PIP. Generated Voronoi polygons (in JTS at least) have their site coordinate attached as userData. Code ​here.

[dbaston]

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.

​https://github.com/libgeos/geos/pull/320

[robe]

Retargeting in prep for GEOS 3.10.0 release

[dbaston]

Resolved by ad54d81109f909f473dec6f89a444ab764308b87/git