Cannot handle certain input

[djozis]

This breaks for the following set of 60 points:
[(0.984, 0.422), (0.260, 0.856), (0.602, 0.336), (0.346, 0.646), (0.234, 0.642), (0.374, 0.692), (0.388, 0.780), (0.078, 0.516), (0.956, 0.354), (0.278, 0.184), (0.644, 0.258), (0.846, 0.270), (0.472, 0.592), (0.228, 0.436), (0.696, 0.124), (0.336, 0.830), (0.510, 0.382), (0.660, 0.478), (0.278, 0.496), (0.254, 0.984), (0.510, 0.954), (0.894, 0.478), (0.928, 0.144), (0.878, 0.894), (0.704, 0.404), (0.460, 0.132), (0.484, 0.486), (0.734, 0.956), (0.056, 0.950), (0.332, 0.950), (0.404, 0.176), (0.640, 0.954), (0.940, 0.936), (0.416, 0.226), (0.752, 0.826), (0.902, 0.594), (0.706, 0.812), (0.240, 0.770), (0.006, 0.322), (0.216, 0.240), (0.036, 0.560), (0.006, 0.292), (0.738, 0.140), (0.628, 0.744), (0.602, 0.686), (0.624, 0.390), (0.040, 0.794), (0.584, 0.760), (0.792, 0.308), (0.918, 0.404), (0.038, 0.280), (0.090, 0.412), (0.310, 0.504), (0.576, 0.432), (0.602, 0.216), (0.392, 0.248), (0.154, 0.650), (0.472, 0.646), (0.328, 0.848), (0.156, 0.836)]

[djozis]

It seems this implementation breaks whenever two neighbors share the same y value.
[(0.800, 0.400), (0.200, 0.600), (0.200, 0.700), (0.600, 0.200), (0.300, 0.700)]

Incrementing the y value of the last point doesn't exhibit this issue, example:
[(0.800, 0.400), (0.200, 0.600), (0.200, 0.700), (0.600, 0.200), (0.300, 0.750)]

[ajwerner]

The problem is with collinear points. Adding a small amount of jitter to the point coordinates should prevent collinearity.

That being said, it is a bug, if I find some time I can try to go back and fix it (and maybe even add some tests). I haven’t touched this code since the original assignment.

[djozis]

Thanks for the response. I'd hoped to use this in a personal game-dev project since I noticed it was MIT licensed and then I ran into this issue. I did notice the last commit was 4 years ago but figured I'd go ahead and submit this anyway in hopes for a fix, or to let other users be aware of it. If you find the time, awesome, else I understand.

[ajwerner]

Do be aware that a lot of Voronoi libraries carry this same problem as it's the main degenerate case. d3/d3-voronoi#12 was closed with the advice to add jitter.

[djozis]

Thanks. You're not wrong, I tried the top 3 github hits for Voronoi Java Fortune libraries and they all exhibited issues with a 3x3 grid of points. I'll try to figure out a way to make jitter work for my use-case.

[djozis]

Even with that second PR, this still doesn't yet handle the 3+ highest points sharing the same y value yet.

[ajwerner]

Yes, the horizontal points should be handled better. In general however floating-point imprecision is a real problem that the original framing of Fortune's algorithm doesn't take in to account. Dealing with horizontal co-linear points will just take some tuning but seems fine. I made that work in a Clojure implementation. Dealing with high-cardinality co-circular points is really hard because the point where the circle events occur should be exactly the same making a fall-back ordering plausible but because of imprecision the events are going to be a jumbled order. The logic needs to be changed to take epsilon differences in to account to cope with the float math but even using epsilons everywhere can turn out to be insufficient for certain cases like when 3 points A, B, and C are such that A and B are <epsilon apart and B and C are epsilon apart.