Polygon generation problems

[Sch1nken]

Hello, I think I found a problem with the polygon generation algorithm. When using a specific set of coordinates I get a polygon with only 2 sides (in my code).

I adapted the iOS example with my own values to get a visualization for the problem at it is quite strange. Without filling in the polygons everything looks alright, but when turning on polygon fill you can clearly see that something is not right.

I modified the iOS example like this:

private func makeSites(forViewSize size: CGSize) {
        let numberOfSites = 30

        Random.setGlobalSeed(pointsSeed)

        var coords: [Double] = [467.14, 115.11, 467.14, 160.03, 467.14, 204.94, 467.14, 249.86, 467.14, 294.78, 467.14, 339.7, 496.64, 115.11, 496.64, 160.03, 496.64, 204.94, 496.64, 249.86, 496.64, 294.78, 496.64, 339.7, 526.14, 115.11, 526.14, 160.03, 526.14, 204.94, 526.14, 249.86, 526.14, 294.78, 526.14, 339.7, 674.12, 160.03, 555.64, 204.94, 555.64, 249.86, 555.64, 294.78, 555.64, 339.7, 585.14, 115.11, 585.14, 160.03, 585.14, 204.94, 585.14, 249.86, 585.14, 294.78, 585.14, 339.7, 614.64, 115.11, 614.64, 160.03, 614.64, 204.94, 614.64, 249.86, 614.64, 294.78, 614.64, 339.7, 644.14, 160.03, 644.14, 204.94, 644.14, 249.86, 644.14, 294.78, 644.14, 339.7, 673.64, 204.94, 673.64, 249.86, 673.64, 294.78, 673.64, 339.7, 703.14, 294.78, 703.14, 339.7]

        sitePoints = []

        var i: Int = 0

        while(i < coords.count) {
            let point = SIMD2<Double>(x: coords[i], y: coords[i+1])
            let color = randomColor()
            sitePoints.append(SitePoint(point: point, userData: color))

            i = i + 2
        }
        /*for _ in 0..<numberOfSites {
            let point = randomPointInArea(withSize: size)
            let color = randomColor()
            sitePoints.append(SitePoint(point: point, userData: color))
        }*/
    }

[Sch1nken]

After some investigation it turned out that a single site is responsible for this behaviour. The coordinate pair [555.64, 204.94]. When slightly modifying the coordinates to for example [556.64, 203.94] everything is working again.

This is sadly not a good solution. I'm currently debugging through the code to see where it goes wrong but my guess is one edge "detection".

Edit: Turns out that even a slight change to the coordinates like [555.65, 204.93] (+- 0.01) "fixes" it. It really IS an edge case (pun intended...)

[WilhelmOks]

Thank you for figuring that out and providing the detailed information. After testing with your code, I believe that the algorithm fails if there are multiple points which have very similar x or y components.

I have ported the site generation algorithm (fortunes algorithm) from the original C# code without understanding how it really works. There is some code which sorts points by their coordinates. I suspect that the problem is somewhere in that part of the code but I am not sure. I will look into that.

As a workaround, I have added an option to randomly offset the site locations in version 1.0.1

You can set the optional parameter of Voronoi.runFortunesAlgorithm() to a small value like this:

Voronoi.runFortunesAlgorithm(sitePoints: sitePoints, clipRect: clipRect, options: options, randomlyOffsetSiteLocationsBy: 0.00001)

The value 0.00001 should work well for your case.

This is of course not optimal because it relies on randomness, but I hope it's a good enough pragmatic solution.

[Sch1nken]

Hello, you're welcome.

If I find the time I'll see if the C# Version has the same problem and report an issue there too.

That "fix" is actually the very same thing I did in my program. I offset every loaded point/coordinate by +-0.01. Thanks for your fast response :).

[WilhelmOks]

The C# version sadly doesn't provide a way to generate polygons for the sites. So you probably won't be able to see any problems.

However, when I play around with your values and the random offsets, I can sometimes see errors even without the polygons. The value 0.00000000001 is sometimes triggering wrong edge generation or crashes due to nil values. This information will hopefully help to find out if the problem comes from the C# version or if I did something wrong when porting it (or maybe both).