clipCells causes 'cannot read property 0 of null'

[twhitbeck]

Repro: http://jsbin.com/cucerakofa/edit?js,console

Ran into this with certain datasets (most work fine). I tried debugging and don't have a clue what's going on, but

in the clipCells function, there's a chain of ternary operators ending with null. It's precisely this null (which is passed into createBorderEdge as the final argument creating an edge with a null point on the end) which is later being accessed for property 0 and is causing the TypeError.

[mbostock]

I’ve reduced the test case down to four points that reliably reproduce the error. If I nudge any one of the points by a tiny amount, I’m able to compute the diagram successfully:

The failure is probably because there are collinear or cocircular points. Such a configuration of points has multiple valid Delaunay triangulations, as described in d3/d3#1895. This has been a problem in the past (see gorhill/Javascript-Voronoi#12). It was partially fixed by updating the port (d3/d3#1538), but I’m pretty sure we still don’t handle cocircular points correctly. As @jasondavies says, “I think a reasonable fix is to pick an arbitrary Delaunay triangulation in this situation.” But it’ll be some work to figure out how to implement that suggestion.

There was a pull request a while back that’s related (d3/d3#2238). But I haven’t had time to investigate it in detail and see if that’s an appropriate fix. I’ll try to look now.

[mbostock]

Yeah, that fix just replaces the crash with an infinite loop, which is worse. 😁

[mbostock]

Oops, I found something obviously wrong, and fixing it fixed this bug. I’m also testing some other changes which might make the code more reliable, but at least for your example, the above commit solves the problem.

[mbostock]

[twhitbeck]

Excellent! thanks for looking into it

[mbostock]

Fixed in 0.3.3.