KeyError for a set of specific points.

[personnumber3377]

Hi! I used parts of your project in my own project (you can take a look at my project here: https://personnumber3377.github.io/projects/implementing_weighted_voronoi_stippling.html and here is the source code: https://github.com/personnumber3377/pythondelaunay )

If you set the points to this:

seeds = [(0.2666666666666666, 0.19999999999999996), (-0.2666666666666667, 0.2666666666666666), (0.1333333333333333, 0.1333333333333333), (0.0, 0.46666666666666656), (0.19999999999999996, 0.19999999999999996), (-0.19999999999999996, 0.46666666666666656), (-0.6, 0.19999999999999996), (-0.2666666666666667, 0.33333333333333326), (-0.06666666666666665, 0.19999999999999996), (0.2666666666666666, 0.0), (-0.19999999999999996, 0.19999999999999996), (0.1333333333333333, 0.2666666666666666), (-0.5333333333333333, -0.06666666666666665), (0.0, -0.4), (0.33333333333333326, 0.06666666666666665), (-0.06666666666666665, -0.33333333333333337), (-0.4, 0.46666666666666656), (0.06666666666666665, -0.2666666666666667), (-0.2666666666666667, 0.19999999999999996), (0.19999999999999996, 0.1333333333333333)]
# Convert each element to a numpy array
seeds = [np.array(x) for x in seeds]

inside of delaunay2D_plotDemo.py and then when you try running it, you should get this error:

    for i, neigh in enumerate(self.triangles[tri_op]):
KeyError: (13, 8, 6)

I don't really understand how your code works, so I don't really know how to fix it, but maybe you can add some insight to this?

Thanks in advance!

[jmespadero]

Yep, the problem here is in the robustness of the method to determine if a seed is inside a triangle. Your input set has some seeds that are perfectly aligned (seeds 16, 5, 3),

One silly solution is just to change the order of your input data, calling random.shuffle.

    random.shuffle(seeds)
    for s in seeds:
        dt.addPoint(s)

with produce this graph:

If you don't want to relay into random.shuffle (which could produce another bad permutation of your seeds), you can also sort the seed by coordinate X or coordinate Y

    #Compute the permutation that sort the input points by X-coordinate
    perm = sorted(range(len(seeds)), key=lambda x: seeds[x][0])    
    #Add points to delaunay using that permutation order
    for i in perm:
        dt.addPoint(seeds[i])```