For some inputs, polygons covering the entire plot are returned

[ctrlcctrlv]

I discovered this while writing a toy program to learn Rust, https://github.com/ctrlcctrlv/interactive-voronoi

For some inputs, strange results are returned, for example:

Creating Voronoi plot for points: [(177.0, 289.0), (195.0, 290.0), (210.0, 293.0), (224.0, 293.0)]
Drawing polygon: [(179.5, 406.5), (156.0, 600.0), (0.0, 600.0), (0.0, 0.0), (202.1, 0.0)]
Drawing polygon: [(239.7, 0.0), (217.0, 0.0), (202.1, 0.0), (0.0, 0.0), (0.0, 600.0), (156.0, 600.0), (600.0, 600.0), (600.0, 0.0)]

You can see if I add one more point, the strange polygon that covers the entire screen goes away:

Creating Voronoi plot for points: [(177.0, 289.0), (195.0, 290.0), (210.0, 293.0), (224.0, 293.0), (328.0, 409.0)]
Drawing polygon: [(217.0, 403.9), (174.6, 447.0), (179.5, 406.5), (217.0, 219.0)]
Drawing polygon: [(217.0, 219.0), (179.5, 406.5), (202.1, 0.0), (239.7, 0.0)]
Drawing polygon: [(174.6, 447.0), (217.0, 403.9), (600.0, 60.5), (600.0, 600.0), (53.0, 600.0)]
Drawing polygon: [(217.0, 403.9), (217.0, 219.0), (239.7, 0.0), (600.0, 0.0), (600.0, 60.5)]
Drawing polygon: [(179.5, 406.5), (174.6, 447.0), (53.0, 600.0), (0.0, 600.0), (0.0, 0.0), (202.1, 0.0)]

Looks like there's something wrong with the library in these cases. 😞

[ctrlcctrlv]

I am unsure if this is a separate issue or not, but it's also possible to receive glitchy self-intersecting polygons from the library if you try hard enough.

Creating Voronoi plot for points: [(342.0, 267.0), (396.0, 312.0), (383.0, 381.0), (271.0, 357.0), (255.0, 302.0), (281.0, 294.0), (310.0, 324.0), (316.0, 325.0), (341.0, 339.0), (359.0, 339.0), (372.0, 330.0), (382.0, 306.0), (380.0, 298.0), (355.0, 277.0), (330.0, 268.0), (301.0, 261.0), (288.0, 261.0), (284.0, 265.0), (282.0, 265.0), (272.0, 265.0), (260.0, 265.0), (251.0, 265.0), (242.0, 265.0), (237.0, 265.0), (233.0, 265.0), (224.0, 265.0), (222.0, 265.0), (213.0, 265.0), (202.0, 265.0), (197.0, 265.0), (196.0, 265.0), (184.0, 263.0), (176.0, 263.0), (174.0, 263.0), (159.0, 262.0), (159.0, 262.0), (153.0, 261.0), (148.0, 257.0), (136.0, 256.0), (123.0, 256.0), (120.0, 256.0), (118.0, 254.0), (118.0, 254.0), (118.0, 254.0), (118.0, 254.0), (118.0, 254.0), (118.0, 254.0)]
Drawing polygon: [(379.7, 355.0), (350.0, 372.0), (350.0, 312.1)]
Drawing polygon: [(383.9, 320.9), (354.5, 308.6), (393.3, 298.9)]
Drawing polygon: [(317.9, 295.2), (307.1, 360.1), (278.1, 325.8), (311.9, 293.1)]
Drawing polygon: [(199.5, 325.0), (196.5, 329.7), (196.5, 225.0), (199.5, 205.5)]
Drawing polygon: [(207.5, 313.6), (199.5, 325.0), (199.5, 205.5), (207.5, 133.5)]
Drawing polygon: [(228.5, 292.7), (223.0, 297.3), (223.0, 0.0), (228.5, 0.0)]
Drawing polygon: [(235.0, 288.9), (228.5, 292.7), (228.5, 0.0), (235.0, 0.0)]
Drawing polygon: [(239.5, 286.7), (235.0, 288.9), (235.0, 0.0), (239.5, 0.0)]
Drawing polygon: [(277.0, 279.3), (266.0, 282.8), (266.0, 207.0), (277.0, 251.0)]
Drawing polygon: [(255.5, 283.2), (246.5, 284.2), (246.5, 50.2), (255.5, 133.5)]
Drawing polygon: [(283.0, 279.6), (277.0, 279.3), (277.0, 251.0), (283.0, 260.0)]
Drawing polygon: [(296.7, 281.0), (283.0, 279.6), (283.0, 260.0), (294.5, 271.5)]
Drawing polygon: [(169.0, 225.5), (159.0, 375.6), (131.6, 407.8), (158.0, 249.7)]
Drawing polygon: [(129.5, 309.5), (121.5, 357.5), (121.5, 252.5), (129.5, 232.5)]
Drawing polygon: [(342.6, 306.8), (310.3, 364.6), (307.1, 360.1), (317.9, 295.2), (333.0, 299.0)]
Drawing polygon: [(405.4, 349.5), (383.9, 320.9), (393.3, 298.9), (600.0, 62.7), (600.0, 386.2)]
Drawing polygon: [(393.3, 298.9), (354.5, 308.6), (350.6, 307.6), (600.0, 10.7), (600.0, 62.7)]
Drawing polygon: [(196.5, 329.7), (181.8, 353.1), (176.7, 357.3), (180.0, 324.0), (196.5, 225.0)]
Drawing polygon: [(263.8, 284.4), (255.5, 283.2), (255.5, 133.5), (266.0, 207.0), (266.0, 282.8)]
Drawing polygon: [(217.5, 302.2), (207.5, 313.6), (207.5, 133.5), (216.7, 0.0), (217.5, 0.0)]
Drawing polygon: [(246.5, 284.2), (239.5, 286.7), (239.5, 0.0), (242.1, 0.0), (246.5, 50.2)]
Drawing polygon: [(176.7, 357.3), (175.0, 359.0), (175.0, 135.0), (180.0, 50.0), (180.0, 324.0)]
Drawing polygon: [(140.8, 271.2), (129.5, 309.5), (129.5, 232.5), (155.3, 0.0), (163.4, 0.0)]
Drawing polygon: [(121.5, 357.5), (109.8, 434.6), (0.0, 598.8), (0.0, 374.0), (121.5, 252.5)]
Drawing polygon: [(350.0, 372.0), (319.9, 402.1), (310.3, 364.6), (342.6, 306.8), (348.9, 308.2), (350.0, 312.1)]
Drawing polygon: [(333.0, 299.0), (317.9, 295.2), (311.9, 293.1), (309.6, 288.8), (330.6, 202.1), (337.6, 286.2)]
Drawing polygon: [(158.0, 249.7), (131.6, 407.8), (109.8, 434.6), (121.5, 357.5), (129.5, 309.5), (140.8, 271.2)]
Drawing polygon: [(309.6, 288.8), (296.7, 281.0), (294.5, 271.5), (294.5, 0.0), (360.1, 0.0), (330.6, 202.1)]
Drawing polygon: [(350.0, 372.0), (379.7, 355.0), (405.4, 349.5), (600.0, 386.2), (600.0, 600.0), (277.5, 600.0), (319.9, 402.1)]
Drawing polygon: [(379.7, 355.0), (350.0, 312.1), (348.9, 308.2), (350.6, 307.6), (354.5, 308.6), (383.9, 320.9), (405.4, 349.5)]
Drawing polygon: [(196.5, 225.0), (180.0, 324.0), (180.0, 50.0), (182.0, 0.0), (216.7, 0.0), (207.5, 133.5), (199.5, 205.5)]
Drawing polygon: [(350.6, 307.6), (348.9, 308.2), (342.6, 306.8), (333.0, 299.0), (337.6, 286.2), (557.7, 0.0), (600.0, 0.0), (600.0, 10.7)]
Drawing polygon: [(294.5, 271.5), (283.0, 260.0), (277.0, 251.0), (266.0, 207.0), (255.5, 133.5), (246.5, 50.2), (242.1, 0.0), (294.5, 0.0)]
Drawing polygon: [(311.9, 293.1), (278.1, 325.8), (276.5, 325.6), (263.8, 284.4), (266.0, 282.8), (277.0, 279.3), (283.0, 279.6), (296.7, 281.0), (309.6, 288.8)]
Drawing polygon: [(276.5, 325.6), (181.8, 353.1), (196.5, 329.7), (199.5, 325.0), (207.5, 313.6), (217.5, 302.2), (223.0, 297.3), (228.5, 292.7), (235.0, 288.9), (239.5, 286.7), (246.5, 284.2), (255.5, 283.2), (263.8, 284.4)]
Drawing polygon: [(337.6, 286.2), (330.6, 202.1), (360.1, 0.0), (374.0, 0.0), (0.0, 374.0), (0.0, 374.0), (374.0, 0.0), (374.0, 0.0), (0.0, 374.0), (0.0, 374.0), (374.0, 0.0), (374.0, 0.0), (0.0, 374.0), (0.0, 0.0), (155.3, 0.0), (129.5, 232.5), (121.5, 252.5), (0.0, 374.0), (0.0, 374.0), (374.0, 0.0), (374.0, 0.0), (0.0, 374.0), (0.0, 374.0), (374.0, 0.0), (374.0, 0.0), (0.0, 374.0), (0.0, 374.0), (374.0, 0.0), (557.7, 0.0)]
Drawing polygon: [(319.9, 402.1), (277.5, 600.0), (144.0, 600.0), (175.0, 135.0), (175.0, 359.0), (159.0, 375.6), (169.0, 225.5), (221.0, 0.0), (223.0, 0.0), (223.0, 297.3), (217.5, 302.2), (217.5, 0.0), (221.0, 0.0), (169.0, 225.5), (158.0, 249.7), (140.8, 271.2), (163.4, 0.0), (182.0, 0.0), (180.0, 50.0), (175.0, 135.0), (144.0, 600.0), (0.0, 600.0), (0.0, 598.8), (109.8, 434.6), (131.6, 407.8), (159.0, 375.6), (175.0, 359.0), (176.7, 357.3), (181.8, 353.1), (276.5, 325.6), (278.1, 325.8), (307.1, 360.1), (310.3, 364.6)]

[petosegan]

Thanks for reporting this. I think that the first bug is exercising a known edge case for Fortune's algorithm that comes up when there are two points with the same y-coordinate that have larger y-coordinate than any other points. I'll figure out a workaround.

The second bug is most likely running into some kind of geometric degeneracy caused by some points having the same x or y coordinate, but I'll have to look at it more closely.

[Luz]

• I fully agree with the first bug.
• The second bug is probably appearing when there are two dots on the exactly same spot. (same x AND same y coordinate)

In a pull request to #https://github.com/ctrlcctrlv/interactive-voronoi/pull/1 there is a workaround for both cases. I am not sure, if there are more degeneracies. Would be better, if these two edge cases are fixed in #rust_voronoi though.

[ydl1991]

Had some similar issues, for certain set of points the DCEL generated is incorrect, and it happens quite frequently, I randomly generate like 10 sites with certain distance in between to make sure they are sort of evenly distributed, and compute the voronoi and test result, 3 out of 10 times it's generating only 9 faces. And if I do 1000 sites, it always gonna generate 1006 faces.

[ydl1991]

found the bug regarding my issue, in the extend_edges function at lines 302, 303 in voronoi.rs, the value should not be a fixed '-1000', but a variable number according to your world size, otherwise it's not gonna extend the edge correctly and you will get error result. I replaced the -1000 with 'max_world_size * 2.0' fixed my issue