search

gorhill / Javascript-Voronoi

A Javascript implementation of Fortune's algorithm to compute Voronoi cells
http://www.raymondhill.net/voronoi/
Other
1.02k stars 166 forks source link

closeCells() fails with "this makes no sense!" exception #27

Open tg8 opened 9 years ago

tg8 commented 9 years ago

The following parameters cause "this makes no sense!" exception:

var  sites =
 [
  { id:"A", x:0      , y:1994781.61 }
 ,{ id:"B", x:2225857, y:34336      }
 ,{ id:"C", x:2575935, y:33225      }
 ,{ id:"D", x:5464269, y:0          }
 ]
;
var  buffer = 360000;
var  bbox = { xl:0          - buffer
            , yt:0          - buffer
            , xr:5464269    + buffer
            , yb:1994781.61 + buffer
//            , yb:2000000    + buffer
            };

var  v = new Voronoi();
var  r = v.compute( sites, bbox );

When yb:2000000 line is uncommented - exception goes away. If I put some visualizing code just in front of this.closeCells(bbox); call, I get the following picture: Visualization results where in green are this.edges state just before the call. Exception happens when the cell for the "B" site is processed. I'm using rhill-voronoi-core.js from the current master branch. Complete example https://gist.github.com/tg8/4b4b2b5c853fbb41f7e1

JaksaVucicevic commented 6 years ago

Same here. The code fails for certain choices of sites, for apparently no good reason.

The problem cannot always be fixed by making the bbox bigger.

Here is another example. One cell cannot be closed because it has one extra nonsensical edge.

<!DOCTYPE html>
<html>
<head>
  <script
              src="https://code.jquery.com/jquery-1.12.4.js"
              integrity="sha256-Qw82+bXyGq6MydymqBxNPYTaUXXq7c8v3CwiYwLLNXU="
              crossorigin="anonymous">
  </script>
</head>

<body id='main_node'>
  <script src="Javascript-Voronoi/rhill-voronoi-core.min.js"></script>

  <script>
    dpts = [[0.20001000000000002,1],[0.80001,0.9],[0.10001,0.1],[0.6000099999999999,0.1],[0.8,1],[0.6000099999999999,0.9],[1.00001,0.1],[0.90001,0.1],[0.20001000000000002,0.8],[0.9,0.10001],[0.599995,0.10000866025403785],[0.10001,0.4],[0.80001,0.4],[0.10001,0],[0.6000099999999999,0.2],[0.199995,0.8000086602540379],[0.40001000000000003,1],[0.4,0.8],[0.90001,0.4],[0.59999,0.2],[0.9,0.2],[0.90001,0],[0.90001,0.8],[0.80001,0.2],[1,0.8],[0.2,0.6],[0.999995,0.10000866025403785],[0.099995,0.10000866025403785],[0.8999900000000001,1.2246467991473532e-21],[0.7999900000000001,0.9],[0.8999900000000001,0.8],[0.9,1],[0.7999900000000001,0.2],[0.09999000000000001,0.4],[0.59999,0.9],[0.6,0.8],[0.4,0.1],[0.8999900000000001,0.1],[0.2,0.1],[1,0.2],[0.7999900000000001,0.4],[0.6,0.6],[0.40001000000000003,0.4],[0.1,0.8],[0.10001,0.2],[0.09999000000000001,0.2],[0.099995,0.09999133974596217],[0.09999000000000001,1.2246467991473532e-21],[0.80001,0.8],[0.599995,0.09999133974596217],[0.19999,1],[0.39999,0.4],[0.7999900000000001,0.8],[0.199995,0.7999913397459621],[0.90001,0.6],[0.8999900000000001,0.6],[1,0],[0.8,0.1],[0.9,0.09999000000000001],[0.6,0.4],[0.999995,0.09999133974596217],[0.1,0.6],[0,0.6],[0.8999900000000001,0.4],[0.39999,1]]

  var voronoi = new Voronoi();
  //dpts = dpts.slice(0);
  //spread_identical_points(dpts);
  xs = [];
  ys = [];
  dpts.forEach( function(dpt) { xs.push(dpt[0]); ys.push(dpt[1]); } );

  var eps = 1e-2; 
  var bbox = {xl: Math.min.apply(null, xs)-eps, xr: Math.max.apply(null, xs)+eps, yt: Math.min.apply(null, ys)-eps, yb: Math.max.apply(null, ys)+eps};
  // xl is x-left, xr is x-right, yt is y-top, and yb is y-bottom

  //var bbox = {xl:-1000, xr: 1000, yt: -1000, yb: 1000};
  var sites = [];
  dpts.forEach(function (el) { sites.push({x: el[0], y: el[1]} ); });  

  // a 'vertex' is an object exhibiting 'x' and 'y' properties. The
  // Voronoi object will add a unique 'voronoiId' property to all
  // sites. The 'voronoiId' can be used as a key to lookup the associated cell
  // in diagram.cells.
  try {
    var diagram = voronoi.compute(sites, bbox);
  }
  catch (err) { 
    function scale_and_shift(x) { return x*1000+100; } 
    var html = "<svg height=\"1200\" width=\"1200\">";

    voronoi.edges.forEach(function(edge){
      x1 = scale_and_shift(edge.va.x);
      y1 = scale_and_shift(edge.va.y);
      x2 = scale_and_shift(edge.vb.x);
      y2 = scale_and_shift(edge.vb.y);
      html+=" <line x1=\""+x1+"\" y1=\""+y1+"\" x2=\""+x2+"\" y2=\""+y2+"\" style=\"stroke:rgb(0,0,0);stroke-width:2\" />";
    });

    voronoi.cells.forEach(function(cell){
      x = scale_and_shift(cell.site.x);
      y = scale_and_shift(cell.site.y);
      html+=" <circle cx=\""+x+"\" cy=\""+y+"\" r=\"10\" stroke-width=\"0\" fill=\""+((cell.closeMe)?"red":"#0000FF88")+"\" />;";
      if (cell.closeMe) {
        cell.halfedges.forEach(function(halfedge){
          x1 = scale_and_shift(halfedge.edge.va.x);
          y1 = scale_and_shift(halfedge.edge.va.y);
          x2 = scale_and_shift(halfedge.edge.vb.x);
          y2 = scale_and_shift(halfedge.edge.vb.y);
          html+=" <line x1=\""+x1+"\" y1=\""+y1+"\" x2=\""+x2+"\" y2=\""+y2+"\" style=\"stroke:#FF0000;stroke-width:4\" />";
        });
        voronoi.edges.forEach(function(edge, index){ if (edge===cell.halfedges[1].edge) console.log("edge index:",index);});
      }
    });

    html+="</svg>"; 
    $("body").append(html);
  }
  </script>
</body>
</html>
wassfila commented 4 years ago

@tg8 , I know this ticket is quite old, but as it's still open, I'm documenting the solution as I think this is actually a fix that can allow it to be closed.

Long story short, but first before getting to the solution, I went through a replacement of all "1e-9" instances in the code with the constantVoronoi.ε, although I think that replacement within the comparison functions might have been enough, yet would not be consistent enough.

So in one sentence, richer numbers, are subject to bigger errors and needs wider comparison margin => bigger "ε"

Changing the following lines (after replacement) do fix the issue : file : rhill-voronoi-core.js ~ line 125

//Voronoi.prototype.ε = Voronoi.ε = 1e-9;//crash
//Voronoi.prototype.ε = Voronoi.ε = 1e-8;//crash
Voronoi.prototype.ε = Voronoi.ε = 1e-7;//no crash

Voronoi.prototype.invε = Voronoi.invε = 1.0 / Voronoi.ε;
Voronoi.prototype.equalWithEpsilon = function(a,b){return this.abs(a-b)<Voronoi.ε;};
Voronoi.prototype.greaterThanWithEpsilon = function(a,b){return (a-b)>Voronoi.ε;};
Voronoi.prototype.greaterThanOrEqualWithEpsilon = function(a,b){return (b-a)<Voronoi.ε;};
Voronoi.prototype.lessThanWithEpsilon = function(a,b){return (b-a)>Voronoi.ε;};
Voronoi.prototype.lessThanOrEqualWithEpsilon = function(a,b){return (a-b)<Voronoi.ε;};