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

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

Open
tg8 opened this issue Oct 9, 2015 · 2 comments
Open

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

tg8 opened this issue Oct 9, 2015 · 2 comments

Comments

@tg8
Copy link

tg8 commented Oct 9, 2015

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
Copy link

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
Copy link

wassfila commented Apr 12, 2020 •
edited

@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.

  • To explain it, I would first ask why is "ε" existing at all.
    the reason is that we're dealing with numeric numbers not exact equations, we all know that. As a consequence, we're aware that each operation is going to take a bit of the result resolution correctness away. In order to compensate that, and if we'd like to compare processed numbers, we set a tolerance margin "ε" used in the functions equalWithEpsilon, greaterThanWithEpsilon, ...
    Now this "ε" is actually only relative to the resolution of the numbers we feed in as input.
    The numbers you provided are extremely big in comparison with the numbers usually used for testing and taken as examples to configure the "ε" value to 1e-9

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.ε;};

@wassfila wassfila mentioned this issue Apr 13, 2020
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@JaksaVucicevic @wassfila @tg8