polygon-clipping: "Unable to complete output ring staring at"

I am getting the following error:

polygon-clipping.umd.js:2181 Uncaught Error: Unable to complete output ring starting at [-91.86961961111155, 42.61062747659163]. Last matching segment found ends at [-91.8660566, 42.6108961].
    at Function.factory (polygon-clipping.umd.js:2181)
    at Operation.run (polygon-clipping.umd.js:2715)
    at union (polygon-clipping.umd.js:2731)
    at Object.run [as callback] (index.js:215)
    at NewClass.eval (index.js:59)
    at HTMLFormElement.handler (leaflet-src.js:2660)

Here are the arguments:

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "type": "MultiPolygon",
        "coordinates": [
          [
            [
              [-91.8681381296294, 42.610082377777616],
              [-91.8680455370368, 42.610082377777616],
              [-91.8680455370368, 42.60980459999983],
              [-91.8681381296294, 42.60980459999983],
              [-91.8681381296294, 42.60971200740724],
              [-91.868230722222, 42.60971200740724],
              [-91.868230722222, 42.60961941481465],
              [-91.86832331481459, 42.60961941481465],
              [-91.86841590740718, 42.60961941481465],
              [-91.86850849999978, 42.60961941481464],
              [-91.86850849999978, 42.60971200740725],
              [-91.86860109259237, 42.60971200740724],
              [-91.86860109259237, 42.60980459999983],
              [-91.86850849999978, 42.60980459999983],
              [-91.86841590740718, 42.60980459999983],
              [-91.86832331481459, 42.60980459999983],
              [-91.868230722222, 42.60980459999983],
              [-91.868230722222, 42.609989785185],
              [-91.8681381296294, 42.609989785185],
              [-91.8681381296294, 42.610082377777616]
            ]
          ],
          [
            [
              [-91.86961961111155, 42.61062747659163],
              [-91.86961961111089, 42.610267562962804],
              [-91.8695270185183, 42.610267562962804],
              [-91.8695270185183, 42.61054534074058],
              [-91.8694344259257, 42.61054534074058],
              [-91.8694344259257, 42.61063793333317],
              [-91.86915664814792, 42.61063793333317],
              [-91.86915664814792, 42.61073052592577],
              [-91.8669344259257, 42.61073052592577],
              [-91.8669344259257, 42.61082311851836],
              [-91.86647146296275, 42.61082311851836],
              [-91.86647146296275, 42.61045274814798],
              [-91.86637887037016, 42.61045274814798],
              [-91.86637887037016, 42.61036015555539],
              [-91.86628627777756, 42.61036015555539],
              [-91.86624536562047, 42.61036015556462],
              [-91.8659157103266, 42.610545340740664],
              [-91.86610109259237, 42.61054534074058],
              [-91.86610109259237, 42.61073052592577],
              [-91.86600849999978, 42.61073052592577],
              [-91.86600849999978, 42.610742638821925],
              [-91.86583199305461, 42.61076086072423],
              [-91.86601542361976, 42.61092414665349],
              [-91.8660566, 42.6108961],
              [-91.86610109259263, 42.610894865817954],
              [-91.86610109259263, 42.610894866465976],
              [-91.86702701851864, 42.61086919171867],
              [-91.86702701851829, 42.61082311851836],
              [-91.8686879090433, 42.61082311852055],
              [-91.86934183333335, 42.61080497199335],
              [-91.86934183333311, 42.61073052592577],
              [-91.8694344259257, 42.61073052592577],
              [-91.86950644804213, 42.61073052593223],
              [-91.86952701851854, 42.610711793936204],
              [-91.8695270185183, 42.61063793333317],
              [-91.86960812811655, 42.61063793333722],
              [-91.86961961111155, 42.61062747659163]
            ]
          ]
        ]
      }
    },
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "type": "MultiPolygon",
        "coordinates": [
          [
            [
              [-91.8681381296294, 42.610082377777616],
              [-91.8680455370368, 42.610082377777616],
              [-91.8680455370368, 42.60980459999983],
              [-91.8681381296294, 42.60980459999983],
              [-91.8681381296294, 42.60971200740724],
              [-91.868230722222, 42.60971200740724],
              [-91.868230722222, 42.60961941481465],
              [-91.86832331481459, 42.60961941481465],
              [-91.86841590740718, 42.60961941481465],
              [-91.86850849999978, 42.60961941481464],
              [-91.86850849999978, 42.60971200740725],
              [-91.86860109259237, 42.60971200740724],
              [-91.86860109259237, 42.60980459999983],
              [-91.86850849999978, 42.60980459999983],
              [-91.86841590740718, 42.60980459999983],
              [-91.86832331481459, 42.60980459999983],
              [-91.868230722222, 42.60980459999983],
              [-91.868230722222, 42.609989785185],
              [-91.8681381296294, 42.609989785185],
              [-91.8681381296294, 42.610082377777616]
            ]
          ],
          [
            [
              [-91.8686879090433, 42.61082311852055],
              [-91.86860109259237, 42.61082311851836],
              [-91.86850849999978, 42.61082311851836],
              [-91.86841590740718, 42.61082311851836],
              [-91.86832331481459, 42.61082311851836],
              [-91.868230722222, 42.61082311851836],
              [-91.8681381296294, 42.61082311851836],
              [-91.8680455370368, 42.61082311851836],
              [-91.86795294444421, 42.61082311851836],
              [-91.86786035185165, 42.61082311851836],
              [-91.86776775925905, 42.61082311851836],
              [-91.86767516666646, 42.61082311851835],
              [-91.86758257407384, 42.61082311851836],
              [-91.86748998148126, 42.61082311851836],
              [-91.86739738888866, 42.61082311851836],
              [-91.86730479629607, 42.61082311851836],
              [-91.86721220370347, 42.61082311851836],
              [-91.86711961111088, 42.61082311851836],
              [-91.86702701851829, 42.61082311851836],
              [-91.86702701851864, 42.61086919171867],
              [-91.86610109259263, 42.610894866465976],
              [-91.86610109259237, 42.61082311851836],
              [-91.86600849999978, 42.61082311851835],
              [-91.86600849999978, 42.61073052592577],
              [-91.86610109259237, 42.61073052592577],
              [-91.86610109259237, 42.61054534074058],
              [-91.86600849999978, 42.61054534074057],
              [-91.86591590740719, 42.61054534074058],
              [-91.8659157103266, 42.610545340740664],
              [-91.86624536562047, 42.61036015556462],
              [-91.86628627777756, 42.61036015555539],
              [-91.86637887037016, 42.61036015555539],
              [-91.86637887037016, 42.61045274814798],
              [-91.86647146296275, 42.61045274814798],
              [-91.86647146296275, 42.61082311851836],
              [-91.86656405555534, 42.61082311851836],
              [-91.86665664814792, 42.61082311851835],
              [-91.86674924074052, 42.61082311851835],
              [-91.86684183333311, 42.61082311851836],
              [-91.8669344259257, 42.61082311851836],
              [-91.8669344259257, 42.61073052592577],
              [-91.86702701851829, 42.61073052592577],
              [-91.86711961111088, 42.61073052592576],
              [-91.86721220370347, 42.610730525925774],
              [-91.86730479629607, 42.610730525925774],
              [-91.86739738888866, 42.61073052592576],
              [-91.86748998148126, 42.61073052592577],
              [-91.86758257407384, 42.610730525925774],
              [-91.86767516666646, 42.61073052592576],
              [-91.86776775925905, 42.610730525925774],
              [-91.86786035185165, 42.610730525925774],
              [-91.86795294444421, 42.61073052592577],
              [-91.8680455370368, 42.61073052592577],
              [-91.8681381296294, 42.61073052592577],
              [-91.868230722222, 42.61073052592577],
              [-91.86832331481459, 42.610730525925774],
              [-91.86841590740718, 42.61073052592577],
              [-91.86850849999978, 42.610730525925774],
              [-91.86860109259237, 42.61073052592577],
              [-91.86869368518497, 42.61073052592577],
              [-91.86878627777756, 42.610730525925774],
              [-91.86887887037014, 42.610730525925774],
              [-91.86897146296273, 42.610730525925774],
              [-91.86906405555533, 42.61073052592577],
              [-91.86915664814792, 42.610730525925774],
              [-91.86915664814792, 42.61063793333317],
              [-91.86924924074052, 42.61063793333317],
              [-91.86934183333311, 42.61063793333317],
              [-91.8694344259257, 42.61063793333317],
              [-91.8694344259257, 42.61054534074058],
              [-91.8695270185183, 42.61054534074058],
              [-91.8695270185183, 42.610267562962804],
              [-91.86961961111089, 42.610267562962804],
              [-91.86961961111155, 42.61062747659163],
              [-91.86960812811655, 42.61063793333722],
              [-91.8695270185183, 42.61063793333318],
              [-91.86952701851854, 42.610711793936204],
              [-91.86950644804213, 42.61073052593223],
              [-91.8694344259257, 42.61073052592577],
              [-91.86934183333311, 42.610730525925774],
              [-91.86934183333335, 42.61080497199335],
              [-91.8686879090433, 42.61082311852055]
            ]
          ]
        ]
      }
    }
  ]
}

This is how it looks:

Screen Shot 2019-10-24 at 8 46 30 PM

Any idea why this might be happening?

About this issue

Original URL
State: open
Created 5 years ago
Comments: 19 (1 by maintainers)

Most upvoted comments

@andrewharvey I went ahead released v0.14.3 just now with the latest on master

@betovelandia thanks for the failing coordinates. If you want a quick fix, I would try trimming the number of digits after the decimal place before running the coords through the library.

mfogel on Oct 26, 2019

Unfortunately, that doesn’t resolve the issue =/ At first I thought it was possibly my implementation but even moving the numbers to just ints or shifting the decimal continues to encounter the issue:

const polygonClipping = require('polygon-clipping');
const poly1 = [
  [
    [-896913437618266, 325917775294804],
    [-896913420772531, 325863246737333],
    [-896932638650491, 325863115360137],
    [-896913437618266, 325917775294804], // Technically not needed, will fail still without this line
  ],
];
const poly2 = [
  [
    [-896871254313303, 325917917879984],
    [-896913437618266, 325917775294802],
    [-896956011358121, 32591762995718], // Technically not needed, will fail still without this line
    [-896871254313303, 325917917879984], // Technically not needed, will fail still without this line
  ],
];
console.log(polygonClipping.difference(poly1, poly2));

In case anyone would like the code for scaling, here’s what I was working on – but it’s more likely rounding is still the workaround for now =/

import assert from "assert"
import cloneDeep from "lodash/cloneDeep"
import difference from "@turf/difference"
import { getGeom } from "@turf/invariant"

// Wrapped `@turf/difference` (`polygon-clipping`) with magnitude scaling to avoid factor issues
//   https://github.com/mfogel/polygon-clipping/issues/91#issuecomment-974614399
const FEATURE_DIFFERENCE_MULTIPLY_FACTOR = 10e3 // Alternatively, consider using 4096 or other 2^n to avoid float issues
function _scaleFeatureCoordinates(feature, factor) {
  // WARNING: THIS WILL MUTATE OUR FEATURE IN-PLACE
  // https://github.com/Turfjs/turf/blob/v6.5.0/packages/turf-difference/index.js#L39-L47
  // https://github.com/Turfjs/turf/blob/v6.5.0/packages/turf-invariant/index.ts#L236-L243
  // DEV: Coordinates are always an array of arrays, https://github.com/mfogel/polygon-clipping/blob/v0.15.3/src/geom-in.js#L4-L77
  const geom = getGeom(feature)
  geom.coordinates = geom.coordinates.map((ring) =>
    ring.map(([x, y]) => [x * factor, y * factor])
  )
  return geom
}
export function featureDifference(_featureA, _featureB) {
  // Deep clone our features
  const featureA = cloneDeep(_featureA)
  const featureB = cloneDeep(_featureB)

  // Sanity check we won't lose any precision
  // DEV: Disabled due to encountering some precision loss =/
  // _scaleFeatureCoordinates(featureA, FEATURE_DIFFERENCE_MULTIPLY_FACTOR)
  // _scaleFeatureCoordinates(featureA, 1 / FEATURE_DIFFERENCE_MULTIPLY_FACTOR)
  // _scaleFeatureCoordinates(featureB, FEATURE_DIFFERENCE_MULTIPLY_FACTOR)
  // _scaleFeatureCoordinates(featureB, 1 / FEATURE_DIFFERENCE_MULTIPLY_FACTOR)
  // assert.deepEqual(JSON.stringify(getGeom(featureA).coordinates), JSON.stringify(getGeom(_featureA).coordinates))
  // assert.deepEqual(JSON.stringify(getGeom(featureB).coordinates), JSON.stringify(getGeom(_featureB).coordinates))

  // Scale up our features for-real, clip, and scale back down
  // DEV: During our testing, we do encounter occasional precision loss at 1e-12 or 1e-13 due to the nature of numbers in JS
  _scaleFeatureCoordinates(featureA, FEATURE_DIFFERENCE_MULTIPLY_FACTOR)
  _scaleFeatureCoordinates(featureB, FEATURE_DIFFERENCE_MULTIPLY_FACTOR)
  const result = difference(featureA, featureB)
  if (result) {
    _scaleFeatureCoordinates(result, 1 / FEATURE_DIFFERENCE_MULTIPLY_FACTOR)
  }
  return result
}

twolfson on Nov 23, 2021

Seeing this as well on 0.15.3, here’s a very reduced JS snippet that still runs into the issue:

const polygonClipping = require('polygon-clipping');
const poly1 = [
  [
    [-89.6913437618266, 32.5917775294804],
    [-89.6913420772531, 32.5863246737333],
    [-89.6932638650491, 32.5863115360137],
    [-89.6913437618266, 32.5917775294804], // Technically not needed, will fail still without this line
  ],
];
const poly2 = [
  [
    [-89.6871254313303, 32.5917917879984],
    [-89.6913437618266, 32.5917775294802],
    [-89.6956011358121, 32.591762995718], // Technically not needed, will fail still without this line
    [-89.6871254313303, 32.5917917879984], // Technically not needed, will fail still without this line
  ],
];
console.log(polygonClipping.difference(poly1, poly2));

Full non-reduced JS version in this gist: https://gist.github.com/twolfson/bfd03b9e4b254374c32a6d91427f36df

My suggestion, given the issues with floating point issues, is scale those number by 1000. That might work.

z3dev on Nov 20, 2021

I am running into this error as well, using turf’s difference function (which uses polygon-clipping’s difference function) to get the difference between a polygon and a multipolygon

EmilyRagan on May 12, 2021