Weird clipping behaviour with grid-like Voronoi diagram

[OneEyeMaker]

I'm trying to build Voronoi diagram from grid-like set of points.

I've two such sets of sites: for first one this implementation works perfectly, but for second one it panics at runtime with message Edge crosses box, intersection must exist. The problem is that sites of these sets differ only by few (floating point) epsilons. And there are no sites outside bounding box.

Links:

• first set of sites.
• second set of sites.

Code that I use to create Voronoi diagram:

VoronoiBuilder::default()
        .set_bounding_box(BoundingBox::new(Point {x: 800.0, y: 800.0}, 1600.0, 1600.0))
        .set_sites(points)
        .set_clip_behavior(ClipBehavior::Clip)
        .build()
        .unwrap();

What causes such weird behavior with clipping enabled (for almost identical sets of points)?

[andreesteve]

Hi, Thanks for reporting, @OneEyeMaker. My first thought is that this is a precision bug, i.e. the clipping algorithm thinks the site is outside of the box, but when calculating the projection it turns out to be parallel to the edge.

I'll debug this later to see what I find. It would be super helpful in case you are able to narrow down your set of sites that reproduce the issue. For example, if you can get a smaller number of sites that produce the same problem, that will help with the investigation.

For my own records, here's your second set of sites on the inspector.

[OneEyeMaker]

Thank you for quick response.

What I found is that Delaunator (because it's internal epsilon value is small enough) produces few extra triangles for points which are almost on the same line. As result in some cases Voronoice can't build diagram: it sometimes prodices vertices with (almost) infinite coordinates,

And as you asked, I narrowed sets of points that cause this problem.

This one works perfectly:

(100, 100)
(240, 660)
(380, 1220)
(660, 240)
(800, 800)
(940, 1360)
(1220, 380)
(1360, 940)
(1500, 1500)

and this one doesn't:

(99.99999999999989, 100.00000000000011)
(239.99999999999997, 660)
(380.00000000000006, 1220)
(660, 240)
(800, 800)
(940, 1360)
(1220, 379.99999999999994)
(1360, 940)
(1500, 1500)

(I received second set just by rotating points of first set by 180 degrees around center of bounding box - and error in calculations is big enough to cause this problem.)

[andreesteve]

I think the problem are the degenerated triangles <0,2,6> and <6,8,7> - same can be seen here (notice that you cannot see the hull edges colored in blue because the inner edges are rendered on top of them).

When we get the triangulation from delaunator, it thinks only the following sites are on the hull:

Hull: [
    5,
    8,
    6,
    3,
    0,
    2,
]

So sites 1 and 7 are inside the triangulation hull, and therefore it creates the degenerated triangles I mentioned above. Voronoice tries to calculate the circumcenters for those triangles and they end up in the infinite and that just messes with the clipping calculation.

Ideally delaunator would have a way to detect these almost collinear vertices and add them to the hull. I cannot think of an easy way to deal with these in voronoice because the triangulation topology directly influences the voronoi diagram, so we cannot ignore the extra degenerated triangles, we'd have to explicitly fix the hull in voronoice.

I'll try to play with delaunator next, as I think addressing it there is likely easier, but I am not sure when I'll be able to get to it.

[OneEyeMaker]

Thank you for response and detailed explanation. Is there any workaround that I can apply from my side?

[andreesteve]

Is there any workaround that I can apply from my side?

Sorry for the delay. I believe if you round your points to a lower precision that should be enough to solve the problem (e.g. round to no integers, as it seems your input is integers).