"Unable to complete output ring" error using @turf/difference

[sonicseaweed]

Using turf 6.5.0 I get an odd error in a very specific case and I cannot understand why.

import { difference, Polygon } from "@turf/turf";

const area1 = {
  type: "Polygon",
  coordinates: [
    [
      [
        11.79926,
        59.307999
      ],
      [
        18.80383,
        60.15596
      ],
      [
        18.73765340635914,
        60.23951348693759
      ],
      [
        18.58133,
        60.34301
      ],
      [
        11.79926,
        59.307999
      ]
    ]
  ]
};

const area1_subtract = {
  type: "Polygon",
  coordinates: [
    [
      [
        11.79926,
        59.307999
      ],
      [
        18.80383,
        60.15596
      ],
      [
        18.73765340635913, // Subtract 1 to final digit
        60.23951348693759
      ],
      [
        18.58133,
        60.34301
      ],
      [
        11.79926,
        59.307999
      ]
    ]
  ]
};

const area1_add = {
  type: "Polygon",
  coordinates: [
    [
      [
        11.79926,
        59.307999
      ],
      [
        18.80383,
        60.15596
      ],
      [
        18.73765340635915, // Add 1 to final digit
        60.23951348693759
      ],
      [
        18.58133,
        60.34301
      ],
      [
        11.79926,
        59.307999
      ]
    ]
  ]
};

const area2 = {
  type: "Polygon",
  coordinates: [
    [
      [
        18.35554,
        60.35768
      ],
      [
        18.58133,
        60.34301
      ],
      [
        18.75959,
        60.22499
      ],
      [
        18.80383,
        60.15596
      ],
      [
        18.35554,
        60.35768
      ]
    ]
  ]
};



describe('Turfjs bug?', () => {
  it('difference broken', () => {
    difference(area1 as Polygon, area2 as Polygon)
  });
  it('works', () => {
    difference(area1_subtract as Polygon, area2 as Polygon)
  });
  it('works', () => {
    difference(area1_add as Polygon, area2 as Polygon)
  });
});

Providing a minimal test case to illustrate the extremely specific error I'm getting.

"Error: Unable to complete output ring starting at [18.58133, 60.34301]. Last matching segment found ends at [18.737653406359147, 60.23951348693759]."

Typescript version: 4.9.5
Node version: v16.17.1
NPM version: 8.15.0

[sonicseaweed]

Found this issue mfogel/polygon-clipping#142
This suggests that they have solved the issue, but not in polygon-clipping that turf uses, instead in polyclip-ts https://github.com/SBanksX/polyclip-ts
I ran my tests against polygon-clipping and get the same results as against turf (not surprisingly), and against polyclip-ts where it seems to work.

Have they abandoned polygon-clipping? Any chance of turf using polyclip-ts instead?

[JamesLMilner]

Thanks for raising this. I'd need to spin this up on Codesandbox to properly verify but this sounds like a bug. I am not familiar with polyclip-ts but if it is handling a case that polygon-clipping is not perhaps you could raise a bug with the polygon-clipping repo explaining the issue and we could get it fixed it upstream and simply update the package version?

[twelch]

@JamesLMilner I looked at this a little closer and you'll see polyclip-ts does suggest to have addressed a variety of existing bugs in polygon-clipping - luizbarboza/polyclip-ts#1. It's more than just a simple TS migration.

I didn't find breadcrumbs to suggest what was done to address these issues, it's all lumped into one big migration commit (luizbarboza/polyclip-ts@141a6a1), but I did see use of BigNumber and precision in geom-in - https://github.com/SBanksX/polyclip-ts/blob/main/src/geom-in.ts#L1

Difference in performance vs. polygon-clipping, and a sense of whether polyclip-ts will be actively maintained is unclear. @SbanksX perhaps you can share a little bit more and any performance differences? Thank you for the work you did on it.

[luizbarboza]

@twelch I haven't done benchmark tests, but probably my version is relatively slower than the original.

I used the bignumber.js library to get more precision and work around floating-point arithmetic errors, which can reduce performance.

Also I changed the splay tree library that was being used by splaytree-ts, as the previous one was causing known errors.

Possibly there are optimizations that can be done, an example would be the use of priority queue instead of splay trees for some occasions, as already pointed out in the paper of the algorithm. There are also additional operations that were necessary when dealing with floating-point arithmetic, but which may not be useful now, and may even be removed, which could compensate for some of the performance losses. There is also this optimization to be done.

There is a trade-off when using this version, so I recommend knowing what your intentions are and what you want to achieve before you go for it.

It is also possible to solve several problems of the original library without making big changes, just using better logic to deal with floating-points (see The Floating-Point Guide). Before I decided on another approach that didn't involve floating-point, I had made some modifications to the original library and ended up solving several, but not all, problems that had already been pointed out, without breaking any of the tests that already existed in the library.

[markstos]

I'm not sure what to make the conversation around performance here. Only one library, polyclip-ts, solves 20 or so correctness bugs that polygon-clipping does not. @luizbarboza mentioned trying another approach with polygon-clipping that still didn't solve all the bugs.

I would suggest this: go ahead and switch to polyclip-ts now because it fixes 20 correctness bugs with polygon-clipping. This change does not preclude to switching to something later that's proven to be equally correct but faster later.

In terms of maintenance, I don't see why polygon-clipping would expect to see any better maintenance over time, considering it's not TypeScript native and it 20 bugs related to it's design that seems hard to fix. As a user, if both module maintainers were being unresponsive, it would be the more correct module that I choose to fork and continue maintenance on myself.

[twelch]

@markstos I think your suggestions are well founded and what I think as well. What we're short on here is maintainers with time to contribute. Any help is welcome. Opening a PR that makes the initial switch, passes all existing tests, and shares a couple of performance numbers for non-trivial examples would be super appreciated and likely pick up contributor interest to help get it over the line (potentially adding tests for the 20 tickets it may resolve).

[markstos]

@twelch I took a swing at contributing such a PR, but ran into an issue with polyclip-ts not supporting a require interface and left a comment about it:

#2237 (comment)

[dennemark]

Also running into similar issues with intersect of newest turf version. I would appreciate a switch to polyclip-ts, as mentioned here and in other issues / PRs, if it really helps. It seems to solve quite some issues.