geom.voronoi sometimes throws an error

[sebpiq]

I am using voronoi to make simple radnomized drawings. It works great most of the time, but once in a while throws an error 'TypeError: Cannot read property 'x' of null'. Is it a know error? Is there some points for which there is no Voronoi tesselation that can be calculated?

For example, this happened with the following data set :

var data = [[162.625,97.42857142857143],[540.6751658469439,97.42857142857143],[512.852513932271,140.7176197088363],[527.1340686082946,193.83092702632547],[477.96982619017825,238.62234566803937],[451.4444556682072,281.63698097906445],[483.1044046913885,292.7353428956168],[408.25114800483453,361.11349522897973],[368.4552492817462,386.43779412571894],[367.73991981069696,408.4655505584161],[327.23397423325974,440.91126844861094],[271.9441040381313,447.2783369755093],[231.3183408178836,464.8987604363098],[183.64125952641743,490.6342071874143],[139.01744689338847,425.60629082860515],[91.52476039970534,440.8609536265624],[50.7819582027996,466.7517342167433],[11.183244819866417,409.5782014996885],[-12.022138010542562,426.2499782865578],[-52.11768265327041,404.35232813819675],[-87.91180657628351,365.92763451746805],[-115.31234555488544,323.9298076521682],[-137.77305520454655,274.51946250365353],[-208.63232162457786,239.8917783235541],[-164.05196897480602,185.08788433033993],[-225.86198629074596,142.5763909605722],[-164.51515098288655,97.42857142857147],[-168.93241508152545,48.8112871990978],[-220.62094168742402,4.249358577293663],[-156.03958646319967,-28.976123962541905],[-155.59804866991823,-87.49511552151564],[-117.46219598471191,-137.50936864144467],[-114.42256168476172,-124.80797733093577],[-62.40654690401547,-173.24432815621287],[-34.92109288645628,-231.77547272408145],[13.243281327294596,-253.71290365408754],[50.108112775233224,-280.520402320271],[94.67169382248188,-289.4662314229714],[140.75187833759216,-295.76903521730037],[186.7138723643959,-252.77374498107582],[231.72212738926686,-267.7762086250434],[266.80663424058025,-219.8715369001228],[308.80693489306793,-232.91974386965757],[348.426624775039,-199.88281899388494],[373.6656986850646,-210.53607230240647],[436.75498495400694,-148.29678300908915],[442.8566733626943,-122.9898329610533],[488.7596396659666,-65.55986283677596],[527.8148963912654,-36.90405535711672],[482.29962464758825,9.630899371618412]]

[jasondavies]

Seems like there might be a bug in d3_geom_voronoiCloseCells.

[voronoipotato]

What's with all the precision? Does it work when you remove some of the digits after the decimal?

[sebpiq]

Didn't try. That's just the output of my algorithm which gives me random-ish points. Would that make a difference?

[voronoipotato]

end = halfEdges[iHalfEdge].end(), x3 = end.x, y3 = end.y; start = halfEdges[++iHalfEdge % nHalfEdges].start(), x2 = start.x, y2 = start.y; I've honestly never seen syntax like this. Why is there a comma instead of a semicolon? If the end = ...end() returns a null does it still try to fill x3 and y3?

[sebpiq]

This thing with the coma is just multiple assignment, nothing special.

[mbostock]

I believe the problem here is that the clipExtent in use does not contain all of the input points. Probably you’re using a standard clipExtent of [[0, 0], [960, 500]] or similar, but you have points with negative x and y coordinates. The clipping logic currently assumes that all of the points are contained within the clip extent.

A simple fix to this would be to ignore any points outside the clip extent on input, but that wouldn’t produce the same output since a site outside the clip extent can still affect the cells within the clip extent. I think probably the d3_geom_voronoiCloseCells would need to be changed to handle this case.

[sebpiq]

Indeed, I don't even know about the 'clipExtent' :)

On the other hand, this works in ~ 98% of my randomized points, and it works even if I place some points completely outside the range [[0, 0], [960, 500]] for example [-10000, 10000].

[jasondavies]

I’m seeing the error even with the default clipExtent of [[-1e6, -1e6], [1e6, 1e6]].

[mbostock]

Hmm. I tested it with [[-width, -height], [width, height]], but yeah. I wonder if the bug more generally is negative coordinates. I did catch a bug related to that when I was porting the code, so it's possible another bug remains.

[mbostock]

Here’s a test case for one variant of the bug:

I think the problem here is that the voronoi cell is completely outside the clip extent.

[mbostock]

That bug is actually unrelated to this bug, but good to fix anyway. Here’s a reduction of the original test case. The correct output should look like this:

Instead it crashes (as reported). It seems like what’s happening here is that the four cells are meeting almost exactly at a point. If you change any of the points slightly, it computes the tessellation correctly.

[mbostock]

All fixed!

[jasondavies]

Nice work!

[sebpiq]

Nice!!! That was quick :) Thanks!

[mbostock]

Thanks, but it was @gorhill who figured it out! Also, Jason, he mentioned catastrophic cancellation which you might find interesting. :)

[Marsup]

I get the same error as this one, the problem seems to come from the same method @jasondavies mentioned as well. I'm using d3 3.4.1. I don't really know where to look from here so I dumped the whole data in a gist in the hope someone would spot what I don't.

[mbostock]

The most likely explanation is that you have coincident points in your input data. Did you check?

[Marsup]

The input data is unique, but the rounding introduced in 6fd4625 changes this, 4023 -> 621 unique values.

[mbostock]

Well, then by our definition you have coincident points, so you’ll need to resolve those before computing the Voronoi.

[Marsup]

So you're saying I should pre-round it at 1e-6 and make it unique from there ? If the points are too close to each other I don't really see how I could achieve that, other than removing the (almost) duplicates from the dataset, any suggestion ?

[gorhill]

@mbostock > most likely explanation is that you have coincident points

Isn't d3_geom_voronoi supposed to work fine with duplicate points?

if (site.x !== x0 || site.y !== y0)

Ref.: d3/src/geom/voronoi/index.j @ line 32

[gorhill]

Note that I had to fix yet another loss of precision problem occurring in the Liang-Barsky algorithm, could it be the same problem here?

My fix was to prune more while attempting to connect dangling lines in connectEdge: https://github.com/gorhill/Javascript-Voronoi/commit/41a3cae6178385836187fdacd760b6abc96cc6d9

Anyway maybe this has nothing to do, just FYI in case.

[mbostock]

d3.geom.voronoi does handle with coincident points (in that it doesn’t throw an error); however it returns a null cell for each point that is a duplicate of an earlier point, so code that doesn’t explicitly check for null cells is likely to throw a TypeError.

And yes, you’d need to either remove the points that are coincident after rounding (say using d3.nest as in the Multi-Line Voronoi example — although this example doesn’t round), or represent coincident points as a cluster.

[Marsup]

Well I've tried, the gist is updated with another file containing only the 621 non-duplicated x values, I've confirmed the uniqueness before and after the sites call, and I still get a Cannot read property 'x' of null.

[mbostock]

Seems to work fine if you round a little bit more.

Do you really need to create Voronoi cells for points that are as little as 1e-6 distance apart? Or would something like 1 or 2 pixels apart be sufficient?

[Marsup]

The data is used to shape line charts paths, the Voronoi being the invisible part that helps find the nearest point from the mouse. In this context, 1px might be enough as long as I do not miss anything visible on the screen. Should I round it to integer pixels and take only the 1st of duplicates or would I miss visible points this way ?

[mbostock]

Yes, that sounds like a reasonable approach.

[Marsup]

In my attempts to reduce the number of points, I noticed that voronoi sometimes brings back an array with gaps, some indexes just don't exist, is this normal ?

[Marsup]

@mbostock Any idea ?

[mbostock]

The only known cause of the array containing null elements is coincident input points.

[Marsup]

Oh, I expected an actual null value, not a missing index, thanks for the explanation :)

[mbostock]

Yep; when skipping coincident points, the implementation simply doesn’t assign anything to that index in the returned array.