Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Cannot handle certain input #1

Open
djozis opened this issue Apr 8, 2018 · 7 comments
Open

Cannot handle certain input #1

djozis opened this issue Apr 8, 2018 · 7 comments

Comments

@djozis
Copy link
Contributor

djozis commented Apr 8, 2018

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)]
image

@djozis
Copy link
Contributor Author

djozis commented Apr 8, 2018

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)]
image
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)]
image

@ajwerner
Copy link
Owner

ajwerner commented Apr 8, 2018

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
Copy link
Contributor Author

djozis commented Apr 8, 2018

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
Copy link
Owner

ajwerner commented Apr 8, 2018

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
Copy link
Contributor Author

djozis commented Apr 8, 2018

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 added a commit to djozis/fortune that referenced this issue Apr 21, 2018
…vertical lines are never detected as colliding with each other
djozis added a commit to djozis/fortune that referenced this issue Apr 21, 2018
… lines are never detected as colliding with each other
ajwerner added a commit that referenced this issue Apr 21, 2018
Resolving at least part of issue #1 - horizontal and vertical lines a…
djozis added a commit to djozis/fortune that referenced this issue Apr 22, 2018
@djozis
Copy link
Contributor Author

djozis commented Apr 23, 2018

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

@ajwerner
Copy link
Owner

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.

ajwerner added a commit that referenced this issue May 6, 2018
Fixing regression cases in issue #1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants