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

Fix delaunay.find performance regression #77

Closed mourner closed 5 years ago

mourner commented 5 years ago

Closes #76 by inlining neighbors loop in delaunay.find (so that it doesn't touch a generator). Brings performance back to v4.0.2 levels (~4x faster).

Before merging, I guess I should add the collinear handling that's in neighbors too?

Fil commented 5 years ago

hmmm, I hadn't tested delaunay.find on collinear input — pushing a test now; it's already working with your code, so it seems the algorithm does indeed converge to a correct point without the special handling of neighbors for this case.

mourner commented 5 years ago

Hmm, what did that collinear code in neighbors target then? Should we remove it there as well? In theory, collinear input doesn’t have triangles so neighbors as a concept don’t make sense.

Fil commented 5 years ago

In a collinear diagram A B C D E, the neighbors of B are A and C.

mourner commented 5 years ago

I mean, what is A B etc here? We return zero triangles in the triangulation. So neighbors can only make sense in the context of Voronoi cells.

Fil commented 5 years ago

A B C D E are consecutive points on an axis. Their voronoi cells do exist (the blue, orange, green, … areas on the image below); the neighbors of a cell are the cells that are immediately before and after them on the axis (except for the two extremal points which have only 1 neighbor). image

Ref. https://observablehq.com/@fil/d3-delaunay-degenerate-cases

Fil commented 5 years ago

Ha I understand your remark after clicking "send". Yes it's a concept with voronoi, not delaunay.