search

d3 / d3-delaunay

Compute the Voronoi diagram of a set of two-dimensional points.
https://d3js.org/d3-delaunay
ISC License
611 stars 57 forks source link

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

Closed jens-ox closed 5 years ago

jens-ox commented 5 years ago

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:

mbostock commented 5 years ago

This is a bug.

EduardoAC commented 5 years ago

Any progress on solving this bug?

mbostock commented 5 years ago

If there were progress on solving this bug, you would see it here.

Fil commented 5 years ago

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.

Fil commented 5 years ago

@jens-ox let us know if you can confirm on your test case