Difference between polygons results in "Unable to complete output ring starting at ..."

[val-o]

Version: 6.5.0

turf.difference crushes with

turf.min.js:88 Uncaught Error: Unable to complete output ring starting at [54.56795530519258, 24.44447467409078]. Last matching segment found ends at [54.57080496898934, 24.4416737163564].

Input polygons

  
{
    "type": "Feature",
    "geometry": {
        "type": "Polygon",
        "coordinates": [
            [
                [
                    54.56658645236534,
                    24.445194105819738
                ],
                [
                    54.56658654953498,
                    24.441605817571325
                ],
                [
                    54.57000000000001,
                    24.43981171174874
                ],
                [
                    54.57341345046501,
                    24.441605817571325
                ],
                [
                    54.573413547634665,
                    24.445194105819738
                ],
                [
                    54.57000000000001,
                    24.44698828825126
                ],
                [
                    54.56658645236534,
                    24.445194105819738
                ]
            ],
            [
                [
                    54.56795530519258,
                    24.44447467409078
                ],
                [
                    54.57000000000001,
                    24.4455493756693
                ],
                [
                    54.57204469480743,
                    24.44447467409078
                ],
                [
                    54.57204465994316,
                    24.442325298422087
                ],
                [
                    54.57000000000001,
                    24.441250624330703
                ],
                [
                    54.56795534005685,
                    24.442325298422087
                ],
                [
                    54.56795530519258,
                    24.44447467409078
                ]
            ]
        ]
    }
}

{
    "type": "Feature",
    "geometry": {
        "type": "Polygon",
        "coordinates": [
            [
                [
                    54.569778932416476,
                    24.441366817541834
                ],
                [
                    54.56977894449294,
                    24.441074136738756
                ],
                [
                    54.57000000000001,
                    24.441190327160086
                ],
                [
                    54.57084694057397,
                    24.440745161222193
                ],
                [
                    54.57084693745136,
                    24.44028034081218
                ],
                [
                    54.571147760242575,
                    24.44043845608456
                ],
                [
                    54.57114771720956,
                    24.441853864959285
                ],
                [
                    54.57080496898934,
                    24.4416737163564
                ],
                [
                    54.57080502276297,
                    24.441026402022757
                ],
                [
                    54.57074511559248,
                    24.441057889217532
                ],
                [
                    54.57074509421786,
                    24.441642246152345
                ],
                [
                    54.57000000000001,
                    24.441250624330703
                ],
                [
                    54.569778932416476,
                    24.441366817541834
                ]
            ]
        ]
    }
}

[rowanwins]

This is an upstream problem in polygon-clipping library. Had a quick look but the martinez-polygon-clipping library also struggles with it (although doesn't crash).

[eric-g-97477]

I am wondering if there is any progress on this.

I did see https://github.com/mfogel/polygon-clipping/issues/91 and it was recently noted that someone solved it by switching to polyclip-ts. Perhaps polyclip is a better library?

With my own code, I used polyclip directly when computing an intersection and it worked. While it does appear that polygon-clipping and polyclip are written by the same people, for some reason polyclip is more reliable.

This issue is a blocker and I am unable to proceed using turf. I hope it can be fixed soon.

[rowanwins]

Thanks for the link @eric-g-97477 to polyclip-ts, I haven't seen that library before. It looks like a fork of polygon-clipping that has had some modifications, some of which are obviously making a difference. I'll try and set aside some time to do a more thorough assessment.

[markstos]

@rowanwins To help with your assessment, the author of polyclip-ts took 20 bug reports from polygon-clipping and turned them to test cases, confirming that polyclip-ts fixes all those cases. Since polygon-clipping is a dependency of Turf.js, that means the new library is tested to fix the same 20 bugs in Turf.js as well.

https://github.com/luizbarboza/polyclip-ts/issues/1

There doesn't seem to be a downside to swapping out the dependency. I'm one of the people that ran into a bug with Turf/polygon-clipping and confirmed it was fixed by switching to polyclip-ts. The algorithms it uses are based on a 2009 paper published on the topic of boolean operations on polygons:

https://www.sciencedirect.com/science/article/abs/pii/S0965997813000379

The only way I could see to improve it would to swap in a more performant algorithm for a case where you would be sure it wouldn't crash like polygon-clipping does. Personally, I'm happy to stick with a single, correct algorithm!

[twelch]

@markstos you'll find more discussion here -- https://github.com/Turfjs/turf/issues/2409. I think the open question is what is the performance decrease of polyclip-ts, if any (benchmark welcome), and will this fork continue to be maintained.

[luizbarboza]

@markstos you'll find more discussion here -- https://github.com/Turfjs/turf/issues/2409. I think the open question is what is the performance decrease of polyclip-ts, if any (benchmark welcome), and will this fork continue to be maintained.

@twelch Some performance improvements can be achieved using the current approach. However, with certain changes, this package can attain great flexibility and achieve excellent performance when not requiring high precision. An update is planned.