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

Can't render Voronoi diagram for particular set of points #37

Closed
chnn opened this issue Apr 10, 2018 · 8 comments · Fixed by #38
Closed

Can't render Voronoi diagram for particular set of points #37

chnn opened this issue Apr 10, 2018 · 8 comments · Fixed by #38
Labels
bug Something isn't working

Comments

@chnn
Copy link

chnn commented Apr 10, 2018

Hello,

I'm having trouble rendering a Voronoi diagram for a set of points with a certain structure. The set of points looks like this:

voronoi

Here is a notebook that describes the issue in more detail.

This sounds like it might be related to #20, though no error is thrown in this case.

@mourner
Copy link
Collaborator

mourner commented Apr 10, 2018

Hmm, maybe browser-specific? I'm seeing results for both in your notebook:

image

Are there any errors in the console?

@chnn
Copy link
Author

chnn commented Apr 10, 2018

Ah, great! I had not thought to try another browser.

I was using Firefox 59.0.2 on macOS. It throws no errors in the console.

@mourner mourner added the bug Something isn't working label Apr 10, 2018
@mourner
Copy link
Collaborator

mourner commented Apr 10, 2018

When I replace the render line to this:

voronoi.render({moveTo: console.log, lineTo: console.log});

I see some weird huge values, which Firefox probably can't handle:

664.4831297076121 -31.1735912402529
672.3576712448785 -72.0304244992434
664.4831297076121 -31.1735912402529
680.819008033027 -16.631376838536138
633.5412543174806 393.00884225846926
23813793908081870 21199061956212450
121.41720113242671 -231.98418498812734
-26277289829606750 -23392068365475628
121.41720113242671 -231.98418498812734
154.39760765467472 -237.02142549637443
...

@mbostock I suspect this is some unhandled edge case in the clipping code?

@mbostock
Copy link
Member

Confirmed. If you zoom out in Chrome:

image

This is almost certainly caused by the collinear points, but I don’t know yet whether it’s a problem with the construction of the Delaunay hull or with Voronoi clipping.

@mbostock
Copy link
Member

The issue here is that because the points are (nearly) collinear, some of the circumcenters have huge coordinates. We’re not doing anything special to handle these huge coordinates in voronoi.render, but we probably should clip the line segments before rendering, as we do in voronoi.renderCell.

@mbostock
Copy link
Member

image

@mbostock
Copy link
Member

Unfortunately, it looks like voronoi.renderCell is still broken with this fix:

image

@mbostock mbostock reopened this Apr 10, 2018
@mbostock
Copy link
Member

Made some progress, but now I’m stuck.

image

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
3 participants