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

Minor change: Only compute bl and cl when needed. #125

Closed martinfrances107 closed 3 years ago

martinfrances107 commented 3 years ago

I want to propose a change to voronoi.js

It is a minor cosmetic change in the loop which computes circumcenters.

With modern jit compilers I don't expect to see much of a performance improvement and it only save time in the two degenerate cases "collinear diagram" and "almost equal points"

But

It just breaks a simple rule .. "Don't do calculations until you know it is needed."

      const dx = x2 - x1;
      const dy = y2 - y1;
      const ex = x3 - x1;
      const ey = y3 - y1;
/*  Remove does not always need to be computed.
      const bl = dx * dx + dy * dy; 
      const cl = ex * ex + ey * ey; 
*/
      const ab = (dx * ey - dy * ex) * 2;

      if (!ab) {
        // degenerate case (collinear diagram)
        x = (x1 + x3) / 2 - 1e8 * ey;
        y = (y1 + y3) / 2 + 1e8 * ex;
      }
      else if (Math.abs(ab) < 1e-8) {
        // almost equal points (degenerate triangle)
        x = (x1 + x3) / 2;
        y = (y1 + y3) / 2;
      } else {
        const d = 1 / ab;
        const bl = dx * dx + dy * dy; // delay calculation of bl and cl to here.
        const cl = ex * ex + ey * ey;
        x = x1 + (ey * bl - dy * cl) * d;
        y = y1 + (dx * cl - ex * bl) * d;
      }

Anyway as usual I am about to generate a PR.

Fil commented 3 years ago

Fix will be merged when https://github.com/d3/d3-delaunay/pull/120 lands. Thank you!