voronoi don't cover the rectangle?

[madcowfpb]

First, I want to thank you for this library. It is extremely useful and (almost always) work flawlessly. Bravo!

Second, there are occasions where the cells that are generated do not cover the rectangle in which they are generated. I haven't found a simple way to reproduce this, but one example is the attached html file (p5.js). Restricting the copy of the initial set of points from y value 182 exhibits the issue, but changing this restriction to y value 183 does not. I hope this is enough to lead you to a fix. If not I can likely simplify this further.

<style> body {padding: 0; margin: 0;} </style> <script src="https://cdn.jsdelivr.net/npm/p5@1.5.0/lib/p5.js"></script> <script src="https://cdn.jsdelivr.net/npm/d3-delaunay@6"></script> <script>

let delaunay;
let voronoi;
let npts = 0;
let npts1 = 0;
let pt1 = [];
let pt = [];

function setup() {

pixelDensity(1);

angleMode(DEGREES);
noLoop();

createCanvas(1200,900);

pt[npts++] = [655.7969338175453, 577.1829027940203];
pt[npts++] = [636.4628405771239, 553.325417551859];
pt[npts++] = [635.8266188887942, 522.6239194536789];
pt[npts++] = [654.1557493564037, 497.98594592072374];
pt[npts++] = [670.6309766388268, 583.2713935876392];
pt[npts++] = [642.0850934324658, 297.5507522498244];
pt[npts++] = [601.7061975190675, 318.6537463423225];
pt[npts++] = [561.182416108571, 297.8303283940756];
pt[npts++] = [554.8305502982115, 252.7144177241107];
pt[npts++] = [588.0295580238832, 221.51157360880836];
pt[npts++] = [632.6654848348213, 230.64533693953035];
pt[npts++] = [650.9392367460566, 272.3809522571423];
pt[npts++] = [478.1357435242799, 385.7802448543905];
pt[npts++] = [458.35788164347815, 344.26227838815294];
pt[npts++] = [458.35788164347815, 505.0234358975614];
pt[npts++] = [730.6421183565219, 344.26227838815294];
pt[npts++] = [730.6421183565219, 505.0234358975614];
pt[npts++] = [467.643789870542, 299.2214383819292];
pt[npts++] = [467.643789870542, 550.0642759037851];
pt[npts++] = [721.3562101294581, 299.2214383819292];
pt[npts++] = [721.3562101294581, 550.0642759037851];
pt[npts++] = [502.2301432585076, 268.9115469372135];
pt[npts++] = [502.2301432585076, 580.3741673485008];
pt[npts++] = [686.7698567414924, 268.9115469372135];
pt[npts++] = [686.7698567414924, 580.3741673485008];
pt[npts++] = [548.1000375534559, 265.6163750998164];
pt[npts++] = [586.6636575974404, 290.67136600324505];
pt[npts++] = [602.2922216054137, 333.9224162461741];
pt[npts++] = [588.6518995008511, 377.8410566275826];
pt[npts++] = [551.2707412284108, 404.6282618994742];
pt[npts++] = [505.29830911771694, 403.4279094948243];
pt[npts++] = [496.7073655092109, 217.01509611018164];
pt[npts++] = [496.7073655092109, 632.2706181755327];
pt[npts++] = [692.2926344907892, 217.01509611018164];
pt[npts++] = [692.2926344907892, 632.2706181755327];
pt[npts++] = [535.2312575635592, 263.38141394162557];
pt[npts++] = [521.0748951482607, 321.97768593420426];
pt[npts++] = [465.63208849182615, 345.6424461974896];
pt[npts++] = [465.63208849182615, 503.6432680882247];
pt[npts++] = [723.3679115081738, 345.6424461974896];
pt[npts++] = [723.3679115081738, 503.6432680882247];
pt[npts++] = [662.3014810302514, 348.73282929307476];
pt[npts++] = [645.3858695889394, 330.92261063880943];
pt[npts++] = [643.7109673188338, 306.4167643703825];
pt[npts++] = [658.0460450536608, 286.4706533388392];
pt[npts++] = [447.27981036477433, 150.34568806848395];
pt[npts++] = [447.27981036477433, 698.9400262172304];
pt[npts++] = [741.7201896352257, 150.34568806848395];
pt[npts++] = [741.7201896352257, 698.9400262172304];
pt[npts++] = [485.27830313288746, 180.29106591864874];
pt[npts++] = [485.27830313288746, 668.9946483670656];
pt[npts++] = [703.7216968671125, 180.29106591864874];
pt[npts++] = [703.7216968671125, 668.9946483670656];
pt[npts++] = [483.214994123222, 228.6269104149241];
pt[npts++] = [483.214994123222, 620.6588038707903];
pt[npts++] = [705.785005876778, 228.6269104149241];
pt[npts++] = [705.785005876778, 620.6588038707903];
pt[npts++] = [590.6100086773762, 325.22270197489564];
pt[npts++] = [574.026098512677, 364.61476649492585];
pt[npts++] = [535.2071170371181, 382.49904732198854];
pt[npts++] = [494.48912078916925, 369.506526202011];
pt[npts++] = [473.2030010585171, 332.44358068612723];
pt[npts++] = [473.2030010585171, 516.8421335995871];
pt[npts++] = [715.7969989414829, 332.44358068612723];
pt[npts++] = [715.7969989414829, 516.8421335995871];
pt[npts++] = [482.49989365225963, 290.72633471277163];
pt[npts++] = [482.49989365225963, 558.5593795729427];
pt[npts++] = [706.5001063477404, 290.72633471277163];
pt[npts++] = [706.5001063477404, 558.5593795729427];
pt[npts++] = [517.5094458142983, 266.2091554110141];
pt[npts++] = [559.8912424927338, 271.735830162506];
pt[npts++] = [587.4427791216684, 304.41110602799034];
pt[npts++] = [604.8892657058583, 278.2339144725543];
pt[npts++] = [652.1646262968876, 265.6090858814057];
pt[npts++] = [701.681535979198, 378.4276838579256];
pt[npts++] = [660.3861524488689, 404.6772041402234];
pt[npts++] = [611.9525697080425, 397.71056371206487];
pt[npts++] = [579.729667386963, 360.8862431891562];
pt[npts++] = [579.2514742536039, 311.9565247422354];
pt[npts++] = [492.35438551899904, 195.06726681422836];
pt[npts++] = [492.35438551899904, 654.218447471486];
pt[npts++] = [696.645614481001, 195.06726681422836];
pt[npts++] = [696.645614481001, 654.218447471486];
pt[npts++] = [472.25772995727255, 210.74124601998844];
pt[npts++] = [472.25772995727255, 638.5444682657259];
pt[npts++] = [716.7422700427275, 210.74124601998844];
pt[npts++] = [716.7422700427275, 638.5444682657259];
pt[npts++] = [446.84125460621783, 208.8565790365407];
pt[npts++] = [446.84125460621783, 640.4291352491737];
pt[npts++] = [742.1587453937822, 208.8565790365407];
pt[npts++] = [742.1587453937822, 640.4291352491737];
pt[npts++] = [470.62129691990435, 142.5222051629507];
pt[npts++] = [470.62129691990435, 706.7635091227636];
pt[npts++] = [718.3787030800956, 142.5222051629507];
pt[npts++] = [718.3787030800956, 706.7635091227636];
pt[npts++] = [491.44637766366105, 157.21455694628634];
pt[npts++] = [491.44637766366105, 692.071157339428];
pt[npts++] = [697.553622336339, 157.21455694628634];
pt[npts++] = [697.553622336339, 692.071157339428];
pt[npts++] = [497.00778156318086, 182.08662914736513];
pt[npts++] = [497.00778156318086, 667.1990851383492];
pt[npts++] = [691.9922184368191, 182.08662914736513];
pt[npts++] = [691.9922184368191, 667.1990851383492];
pt[npts++] = [514.2284541358853, 455.8366682262695];
pt[npts++] = [486.0011204485046, 444.7394699068891];
pt[npts++] = [476.55594674149336, 415.91727583213526];
pt[npts++] = [492.74063907694233, 390.26603976746867];
pt[npts++] = [522.8213724076467, 386.3827859867524];
pt[npts++] = [544.9897579870977, 407.0828550310619];
pt[npts++] = [543.1738215956482, 437.35879519252677];
pt[npts++] = [518.6901084893021, 455.2606936997951];

npts1 = 0
for (i=0; i<npts; i++) {
if (pt[i][1] > 182) {
pt1[npts1++] = pt[i];
}
}
delaunay = d3.Delaunay.from(pt1);
voronoi = delaunay.voronoi([445.875, 636.9642857142858, 743.125, 849.2857142857143]);

}

function draw() {
noLoop();
console.log(pt1);
fill(255,0,0);

for (i=0; i<npts1; i++) {
point(pt1[i][0],pt1[i][1]);
let polygon = voronoi.cellPolygon(i);
if (polygon != null) {
console.log(polygon);
beginShape();
for (j=0; j<polygon.length; j++) {
vertex(polygon[j][0],polygon[j][1]);
}
endShape(CLOSE);
}
}
}
</script>

[mbostock]

I’ve reproduced this in a notebook: https://observablehq.com/d/cbcdfb87c58882b4. See the gap in cell 96.

I suspect that this is a numerical precision problem with the finite clipping implementation, and given that this library doesn’t use robust predicates (other than to compute the Delaunay triangulation thanks to the underlying delaunator library), I’m not sure it’s readily fixable. But maybe there’s a way.

[Fil]

Slightly tweaking the coordinates fixes the notebook:

    Plot.voronoi(delaunay136, {
      x: (d,i) => d[0] + i * 1e-13,
      y: (d) => d[1],

Fixing the bug is another matter; the fun part is that it happens at the bottom of the screen, but it is not triggered if you remove the points at the top with delaunay136.filter(d => d[1] > 183).

[madcowfpb]

Here's a version exhibiting the issue with 9 points. It makes no sense to me, but the issue does not seem to occur unless the input array of points is copied.

html source:

<style> body {padding: 0; margin: 0;} </style> <script src="https://cdn.jsdelivr.net/npm/p5@1.5.0/lib/p5.js"></script> <script src="https://cdn.jsdelivr.net/npm/d3-delaunay@6"></script> <script>

let delaunay;
let voronoi;
let npts = 0;
let npts1 = 0;
let pt1 = [];
let pt = [];

function setup() {

pixelDensity(1);

angleMode(DEGREES);
noLoop();

createCanvas(1200,900);

pt[npts++] = [447.27981036477433, 698.9400262172304];
pt[npts++] = [485.27830313288746, 668.9946483670656];
pt[npts++] = [611.9525697080425, 397.71056371206487];
pt[npts++] = [491.44637766366105, 692.071157339428];
pt[npts++] = [697.553622336339, 692.071157339428];
pt[npts++] = [497.00778156318086, 667.1990851383492];
pt[npts++] = [691.9922184368191, 667.1990851383492];
pt[npts++] = [544.9897579870977, 407.0828550310619];
pt[npts++] = [543.1738215956482, 437.35879519252677];

npts1 = 0
for (i=0; i<npts; i++) {
pt1[npts1++] = pt[i];
}
delaunay = d3.Delaunay.from(pt1);
voronoi = delaunay.voronoi([440, 380, 740, 850]);

}

function draw() {
noLoop();
console.log(pt1);
fill(255,0,0);

for (i=0; i<npts1; i++) {
point(pt1[i][0],pt1[i][1]);
let polygon = voronoi.cellPolygon(i);
if (polygon != null) {
console.log(polygon);
beginShape();
for (j=0; j<polygon.length; j++) {
vertex(polygon[j][0],polygon[j][1]);
}
endShape(CLOSE);
}
}
fill(0);
for (i=0; i<npts; i++) {
text(i,pt[i][0],pt[i][1]);
}
}
</script>

[madcowfpb]

Walking through the execution of this, it looks like there's a bug in the clipping implementation. The circumcenters for the botched cell are correctly computed and passed to _clipfinite. The first two circumcenters are in the region (these are coincidentally the same, and are the top right point of the botched cell). The third is out of (below) the region and this segment is correctly clipped at the bottom of the enclosing rectangle. The problem arises when dealing with the fourth circumcenter which is back in the region. I don't understand exactly where the bug is, but instead of adding a segment along the edge and another clipped segment to the fourth circumcenter what happens is the array holding the clipped version is reinitialized and ends up containing only the clipped segment from the third circumcenter to the fourth.

[Fil]

Thanks! I traced the problem to the code that we introduced for #88 in order to simplify the polygons when three consecutive points are aligned.

See #140 for a fix, build at https://observablehq.com/@d3/voronoi-issue-136

[madcowfpb]

@Fil - Any idea when this fix will show up in the version at https://cdn.jsdelivr.net/npm/d3-delaunay@6 ?

[mbostock]

@madcowfpb I just published it and it is live now. Thank you again for the bug report.