unable to complete output ring starting at

[MitchellMonaghan]

Doing a intersect on these two shapes seems to produce the unable to complete output ring starting at error

{
        type: 'Feature',
        properties: {},
        geometry: {
          type: 'Polygon',
          coordinates: [
            [
              [
                -94.01653361819794,
                44.91274384567805
              ],
              [
                -94.01648672631458,
                44.91275462177405
              ],
              [
                -94.01653344003874,
                44.91275386419229
              ],
              [
                -94.01653361819794,
                44.91274384567805
              ]
            ]
          ]
        }
      }

      {
        type: 'Feature',
        properties: {},
        geometry: {
          type: 'Polygon',
          coordinates: [
            [
              [
                -94.01654779292787,
                44.91274058822198
              ],
              [
                -94.0164867263146,
                44.91275462177405
              ],
              [
                -94.01650378031933,
                44.91275434520002
              ],
              [
                -94.01654762526815,
                44.912753634142746
              ],
              [
                -94.01654779292787,
                44.91274058822198
              ]
            ]
          ]
        }
      }

[luizbarboza]

This issue can be resolved by setting the precision to something like 1e-12 before performing the operation.

For example:

polyclip.setPrecision(1e-12)

polyclip.intersection(poly1, poly2)

will give the following result:

[
  [ -94.01653361819794, 44.91274384567805 ],
  [ -94.01648672631458, 44.91275462177405 ],
  [ -94.01653344003874, 44.91275386419229 ],
  [ -94.01653361819794, 44.91274384567805 ]
]

[kade-robertson]

JSFiddle of another case that produces this: https://jsfiddle.net/Lp280jcw/1/ -- these are two polygons that should be considered identical (i.e. result of difference is null).

As mentioned in Turfjs/turf#2890 -- it doesn't seem to matter what precision I set, any precision value being set produces the expected result, but unsetting the precision produces the error again.

[Cyber-Ware]

Thank you for making this ticket because I'm also a TurfJS user who was left wondering why the math was not mathing in some seemingly random cases. Setting the precision also got rid of the error for me.

I was left wondering which precision to set so I had a look at version 0.15.3 of this library which is the last one before setPrecision() was introduced and the float comparison got overhauled.
You can find the float comparison algorithm here. It is not really a standard implementation.

• both floats are 0, if they are in the range ]-Number.EPSILON, Number.EPSILON[
• both floats are equal if their squared difference (a - b)² is less than Number.EPSILON² * a * b

As of version 0.16.1 (see algorithm), two floats are never deemed to be the same as long as there's no precision set (doomed to fail as we see with the error). If a precision is set, the result of abs(b - a) must be less than or equal to that value.

In other words: define for yourself what a good precision is in your context. Watch out with using Number.EPSILON for "maximum accuracy" because 1000.1 + 1000.2 has an error of 10^-13 whereas the value of Number.EPSILON is only around 10^-16. The bigger the number and the more decimals it has, the larger the inaccuracy can become.

[MarcThu]

I’m hitting the same Unable to complete output ring starting at … error, but I’m a bit confused about how setPrecision is supposed to be used.

In my case (two polygons with very little overlap), the error does not go away unless the precision is set to 1e-13 or lower. If I use anything larger (e.g. 1e-8), I still get:

Unable to complete output ring starting at [10.14934905, 50.85059454]. Last matching segment found ends at [10.149354, 50.850595].

Example (fails with 1e-8, works with <= 1e-13):

import * as turf from '@turf/turf';
import * as polyclip from "polyclip-ts"

const polyA = turf.polygon([[[10.146314,50.854236],[10.145187,50.854907],[10.144967,50.855038],[10.144555,50.855331],[10.144026,50.85576],[10.143254,50.856385],[10.142833,50.856743],[10.142808,50.856763],[10.14261,50.856504],[10.142858,50.856228],[10.143288,50.855864],[10.143773,50.855517],[10.144365,50.855037],[10.144597,50.85491],[10.14478,50.854808],[10.144911,50.854694],[10.145027,50.854592],[10.145139,50.854467],[10.145258,50.854335],[10.145395,50.854155],[10.14568,50.853784],[10.145788,50.853617],[10.145892,50.853456],[10.146095,50.85318],[10.146376,50.85294],[10.146424,50.852899],[10.146626,50.852695],[10.146827,50.852492],[10.14731,50.85211],[10.14765,50.851842],[10.148137,50.850834],[10.148355,50.850566],[10.148458,50.85044],[10.149354,50.850595],[10.149841,50.850549],[10.149319,50.850757],[10.149051,50.850948],[10.148912,50.851106],[10.148834,50.851273],[10.148652,50.851836],[10.148618,50.852047],[10.148717,50.852458],[10.148716,50.852631],[10.148613,50.852778],[10.148486,50.852885],[10.148048,50.853168],[10.147263,50.853676],[10.146314,50.854236]]]);

const polyB = turf.polygon([[[10.14189911,50.85653248],[10.14190367,50.85644582],[10.14193449,50.85636133],[10.14199042,50.85628214],[10.14223842,50.85600615],[10.14228699,50.85595919],[10.14271699,50.85559519],[10.14275388,50.8555665],[10.14322441,50.85522986],[10.14380297,50.85476076],[10.14389836,50.85469728],[10.14412795,50.85457159],[10.14424962,50.85450378],[10.14433341,50.85443086],[10.14442596,50.85434948],[10.14451903,50.85424562],[10.14451995,50.85424458],[10.14462671,50.85412617],[10.14475299,50.85396026],[10.14475411,50.85395879],[10.14502918,50.85360072],[10.14512852,50.85344712],[10.14523247,50.8532862],[10.14524598,50.85326663],[10.14544898,50.85299063],[10.14552223,50.85291272],[10.14580322,50.85267273],[10.14583473,50.85264581],[10.14602204,50.85245665],[10.14622304,50.85225365],[10.14627035,50.85221147],[10.14675335,50.85182948],[10.14675409,50.8518289],[10.14700863,50.85162826],[10.14745576,50.85070281],[10.14750344,50.85062858],[10.14772144,50.85036058],[10.1477221,50.85035977],[10.1478251,50.85023377],[10.14790018,50.85016042],[10.14799631,50.85009761],[10.14810986,50.85004772],[10.14823654,50.85001263],[10.14837158,50.84999366],[10.14850988,50.84999153],[10.14864622,50.85000633],[10.14939726,50.85013625],[10.14973562,50.85010429],[10.14979744,50.85010229],[10.14985438,50.85034675],[10.14995755,50.85049862],[10.14984526,50.85055368],[10.14934905,50.85059454],[10.1484645,50.85044138],[10.14835397,50.85056837],[10.14813313,50.85083134],[10.14764654,50.85184335],[10.14682421,50.85248995],[10.14642223,50.85289859],[10.14608818,50.85318065],[10.14589594,50.85345233],[10.14567683,50.85378723],[10.14526393,50.85433087],[10.14502885,50.85459397],[10.14477846,50.85481226],[10.14437205,50.85504108],[10.14377271,50.85551459],[10.14328391,50.85586112],[10.14285237,50.85622507],[10.1426035,50.85650629],[10.14280873,50.85676508],[10.14275279,50.8568016],[10.14294339,50.85704255],[10.14256805,50.85718504],[10.14245778,50.85715456],[10.14234024,50.85710212],[10.1422418,50.85703585],[10.14216647,50.85695843],[10.14196848,50.85669943],[10.14192099,50.85661808],[10.14189911,50.85653248]]])

polyclip.setPrecision(1e-8)

const fc = turf.featureCollection([polyA, polyB])
turf.intersect(fc)

Is this expected? I’m trying to understand why a value as small as 1e-13 is needed here (especially since 1e-8 already sounds “very precise” in lon/lat degrees) and whether this indicates a bug or a mismatch in how setPrecision is intended to be interpreted.

Thanks for your help!