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.

Sign up for GitHub

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

Jump to bottom

delaunay.find fails when i is a coincident point. #55

Closed
jens-ox opened this issue Mar 4, 2019 · 5 comments
Closed

delaunay.find fails when i is a coincident point. #55

jens-ox opened this issue Mar 4, 2019 · 5 comments
Labels
bug Something isn't working

Comments

@jens-ox
Copy link

jens-ox commented Mar 4, 2019

I'm working with a set of lines that sometimes have coincident start points. I use d3-delaunay to find the nearest point to the cursor in order to highlight the line this point belongs to.

Screenshot of graph

If it occurs that there is a point coincident to the first point of the first line, inedges[0] will be -1. Therefore, find(x, y, i = 0) will return -1 independent of x and y (because of how the _step function is implemented) — but find(x, y, i = 1) will not return -1 (or maybe only for i = 2, 3,...).

Question:

  • Should this case be handled by me (by iteratively incrementing i and calling find(x, y, i)) or by d3-delaunay?
@mbostock
Copy link
Member

This is a bug.
@mbostock mbostock changed the title Expected behaviour of "find" for datasets with coincident points Mar 17, 2019
@plouc plouc mentioned this issue May 14, 2019
Closed
@EduardoAC
Copy link

Any progress on solving this bug?
@mbostock
Copy link
Member

If there were progress on solving this bug, you would see it here.
@Fil
Copy link
Member

Fil commented May 21, 2019

This seems to be working:

    if (inedges[i] === -1) {
      const l = points.length / 2;
      return (i + 1 + (l - 1) * Math.random() | 0) % l;
    }

It makes sure that from a coincident point i we jump to somewhere else than i, at random so it doesn't get stuck in an infinite loop.
This was referenced May 21, 2019
Closed
Closed
@mourner mourner added the bug Something isn't working label May 22, 2019
@Fil Fil closed this as completed in d180502 May 22, 2019
@Fil
Copy link
Member

Fil commented May 22, 2019

@jens-ox let us know if you can confirm on your test case
Fil added a commit that referenced this issue May 24, 2019
@Fil
find(x,y,i): if i is coincident, scan until we find a regular point
c2913d4 
with a possibly superfluous test on i0 to avoid infinite looping if no point is regular

fixes #55
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
5 participants
@Fil @mourner @mbostock @EduardoAC @jens-ox