Co-location issues with Graph triangulation builders

[martinfleis]

I have encountered an issue with triangulation where the precision used by shapely does not match the precision used by QHull, leading to inability of our tooling to filter out points seen as equal. Repr:

s = gpd.GeoSeries.from_wkt(
    ['POINT (4071747.2387195 3117751.359062438)',
 'POINT (4071747.2396468357 3117751.359621293)',
 'POINT (4071799.634601838 3117828.4939858434)',
 'POINT (4071770.345504768 3117986.514968087)',
 'POINT (4071827.410512167 3117723.096411029)']
)
Graph.build_triangulation(s)

The first two points are not seen as duplicated by shapely but are seen as duplicated by QHull.

I think that the best way around this is to refactor our handling of co-located points and rely on the output of Delaunay.coplanar instead of trying to filter this before triangulation. At the same time, we can let QHull to deal with jittering as well, by passing the QJ option to QHull, to simplify our codebase.

We would then only need custom treatment in Voronoi, but only for jittering as shapely returns duplicated faces for duplicated points, so a clique is created automatically.

[ljwolf]

Just as a consideration—I did think about doing jittering in QHull, but we also potentially need jittering for KNN. So, using Qhull to jitter triangulations but a different one for KNN will give us two different jittering implementations with potentially different effects. I thought it simpler to route everything through our jittering, hence the implementation.

If we move to QHull jittering for Delaunay, how do you propose we deal with it when it's needed in KNN?

[martinfleis]

We can still jitter ourselves, that is not a big issue. We also need it in voronoi. In any case, I think we need to always jitter when coincident="jitter" because we can't check ourselves for coincidence within QHull.