"Key Error" in lps.weights.Queen.from_iterable.

[rrrzhan]

We met a Key Error when using the API lps.weights.Queen.from_iterable when evaluating Moran's Index in spatial analysis, which caused by replicated points. We submitted our coordinates data array.tsv and here is our code:

import pandas as pd
from shapely.geometry import Point
# Input my coordinates
df = pd.read_csv("array.tsv", sep='\t', index_col=0)
points = [Point(xy) for xy in zip(df['array_row'], df['array_col'])]
# calculate weights
wq = lps.weights.Queen.from_iterable(points)

Output:

Traceback (most recent call last):
  File "/home/rzh/anaconda3/envs/spatial/lib/python3.9/site-packages/IPython/core/interactiveshell.py", line 3397, in run_code
    exec(code_obj, self.user_global_ns, self.user_ns)
  File "<ipython-input-30-0b3b020fc447>", line 4, in <cell line: 4>
    wq = lps.weights.Queen.from_iterable(points)
  File "/home/rzh/anaconda3/envs/spatial/lib/python3.9/site-packages/libpysal/weights/contiguity.py", line 416, in from_iterable
    w = cls(new_iterable, **kwargs)
  File "/home/rzh/anaconda3/envs/spatial/lib/python3.9/site-packages/libpysal/weights/contiguity.py", line 335, in __init__
    polygons, vertices = voronoi_frames(get_points_array(polygons))
  File "/home/rzh/anaconda3/envs/spatial/lib/python3.9/site-packages/libpysal/cg/voronoi.py", line 245, in voronoi_frames
    regions, vertices = voronoi(points, radius=radius)
  File "/home/rzh/anaconda3/envs/spatial/lib/python3.9/site-packages/libpysal/cg/voronoi.py", line 57, in voronoi
    vor = voronoi_regions(Voronoi(points), radius=radius)
  File "/home/rzh/anaconda3/envs/spatial/lib/python3.9/site-packages/libpysal/cg/voronoi.py", line 99, in voronoi_regions
    ridges = all_ridges[p1]
KeyError: 3499

We tried to locate where the bug happens and found in voronoi.py:

...
  all_ridges = {}
  for (p1, p2), (v1, v2) in zip(vor.ridge_points, vor.ridge_vertices):
      all_ridges.setdefault(p1, []).append((p2, v1, v2))
      all_ridges.setdefault(p2, []).append((p1, v1, v2))

  for p1, region in enumerate(vor.point_region):
      vertices = vor.regions[region]

      if all(v >= 0 for v in vertices):
          new_regions.append(vertices)
          continue

      ridges = all_ridges[p1]
...

Further, we evaluated the p1 form vor.ridge_points and vor.point_region:

import numpy as np
from scipy.spatial import Voronoi
pts = [xy for xy in zip(df['array_row'], df['array_col'])]
vor = Voronoi(pts)
all_ridges = {}
for (p1, p2), (v1, v2) in zip(vor.ridge_points, vor.ridge_vertices):
    all_ridges.setdefault(p1, []).append((p2, v1, v2))
    all_ridges.setdefault(p2, []).append((p1, v1, v2))

print(f"p1 has {len(all_ridges)} candidates from `all_ridges` ")
#   for p1, region in enumerate(vor.point_region):
print(f"p1 has {len(vor.point_region)} candidates from `vor.point_region` ")
#       ridges = all_ridges[p1]

We found that they were not matched:

>>> p1 has 4801 candidates from `all_ridges` 
>>> p1 has 5328 candidates from `vor.point_region` 

And your code used p1 from vor.point_region as an index for all_ridges , this would cause Key Error. This may be caused by replicated points in our data. But in our scenario, removing the replicated points is not allowed. We hope the replicated points have same neighbors. We would be appreciated if you take this problem into your consideration.

• Platform information:

>>> posix linux
>>> posix.uname_result(sysname='Linux', nodename='rzh-MS-7A74', release='5.15.0-75-generic', version='#82~20.04.1-Ubuntu SMP Wed Jun 7 19:37:37 UTC 2023', machine='x86_64')

• Python version:

>>> 3.9.7 (default, Sep 16 2021, 13:09:58) 
>>> [GCC 7.5.0]

• SciPy version:

>>> import scipy; print(scipy.__version__)
>>> 1.8.0

• NumPy version:

>>> import numpy; print(numpy.__version__)
>>> 1.21.6

• libpysal version:

>>> 4.8.0

Also, please upload any relevant data as a file
attachment. Please do not upload pickled objects, since it's nearly impossible to troubleshoot them without replicating your exact namespace. Instead, provide the minimal subset of the data required to replicate the problem. If it makes you more comfortable submitting the issue, feel free to:

1. remove personally identifying information from data or code
2. provide only the required subset of the full data or code

[rrrzhan]

Our data is available here: array.txt

[martinfleis]

Can you check what happens with the latest libpysal 4.10? We have recently refactored the Voronoi logic and I suppose the issue will materialise differently now.

[rrrzhan]

Thank you, we found this issued solved by libpysal >= 4.9.0. However, in our scenario python 3.9 is required, which only supports libpysal <= 4.8.1. How can I solve this problem without upgrading my python version?

[martinfleis]

I am not sure. I am afraid that we do not have a capacity to provide support on outdated versions. Sorry. You may try to adapt the codebase of current libpysal to be compatible with Python 3.9 and install that. It should not be too complicated.

[ljwolf]

@rrrzhan, the issue is that your points are coincident. Delaunay Triangulations/Voronoi Diagrams are not well-defined mathematically when this is the case. The underlying Qhull library used by scipy (upon which we rely) silently drops the values that are coincident.

The fastest way you can deal with this is to add a very small random component to the input points. This is one of the supported options in Qhull, too, and is also implemented in the new weights as the "jitter" option.

It would be more complicated, but you can compute the unique locations, then construct the weights on locations, and expand the weights from locations back to the points. This is the "expand clique" option in the new implementation.