voronoi weights fail on duplicate points.

[ljwolf]

Voronoi weights do not work when there are co-incident points.

import geopandas
import shapely
import numpy

points = [geometry.Point(*t) for t in numpy.random.normal(0,1,(3,2))]
df = geopandas.GeoDataFrame(geometry=points+[points[1]])

from libpysal.weights import Voronoi

Voronoi(numpy.row_stack((df.geometry.x, df.geometry.y)).T)

fails on a key error.

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-117-38ea3c415855> in <module>
----> 1 lpVoronoi(numpy.row_stack((testdf.geometry.x, testdf.geometry.y)).T)

~/anaconda3/envs/ana/lib/python3.7/site-packages/libpysal/weights/contiguity.py in Voronoi(points)
    347     """
    348     from ..cg.voronoi import voronoi_frames
--> 349     region_df, _ = voronoi_frames(points)
    350     return Queen.from_dataframe(region_df)
    351 

~/anaconda3/envs/ana/lib/python3.7/site-packages/libpysal/cg/voronoi.py in voronoi_frames(points, radius)
    215 
    216     """
--> 217     regions, vertices = voronoi(points, radius=radius)
    218     return as_dataframes(regions, vertices, points)

~/anaconda3/envs/ana/lib/python3.7/site-packages/libpysal/cg/voronoi.py in voronoi(points, radius)
     56     """
     57     vor = Voronoi(points)
---> 58     return voronoi_regions(vor, radius=radius)
     59 
     60 def voronoi_regions(vor, radius=None):

~/anaconda3/envs/ana/lib/python3.7/site-packages/libpysal/cg/voronoi.py in voronoi_regions(vor, radius)
     90             continue
     91 
---> 92         ridges = all_ridges[p1]
     93         new_region = [v for v in vertices if v >= 0]
     94 

KeyError: 3

[ljwolf]

This is an interesting conceptual problem, akin to the issue we face with KNN weights in #23
I see 3 options:

1. Treat it like a graph clique: use an "entry" node that corresponds to the voronoi cell for one of the points. Connect each other coincident observation to the entry. The non-entry points (called the inner clique) are then connected exclusively to one another & the entry. The entry could be synthetic (i.e. introduced into the graph) or assigned (chosen from existing coincident points). The way I see it,
   a. Using synthetic entry points, the output weights would no longer be conformal to the input dataframe. That's a pain.
   b. there's no good way to pick an assigned entry point, especially in cases where the observations' features matter, like in spatial lags or autoregressive study.
   c. For regionalization, this would be nice, because either the inner clique is assigned to its own cluster, or the entry's assignment determines the inner clique's assignment.
2. Ignore it: make coincident points share their voronoi polygon, so that the voronoi tesselation is now not planar. This is simple, and has a few desirable properties:
   a. the standard Rook/Queen contiguity constructors would ensure that the coincident points are neighbors. Since their polygons are the same, they share all points/all lines on the boundary.
   b. the output weights are conformal to the input weights.
   c. the spatial lag still makes sense, since all the observations are considered "near", the lag at the coincident site is the average of all coincident observations pooled with the observations nearby.
   d. for regionalization, this means that the same site can be assigned to different clusters, which is a pretty annoying feature.

[github-actions]

Stale issue message