"Unable to complete output ring staring at" #91
Comments
|
@betovelandia There were a bunch of fixes made in master https://github.com/mfogel/polygon-clipping/commits/master that haven't yet been included in a release. Could you check these against master? When I install this in a library I then do: cd node_modules/polygon-clipping && yarnpkg install && yarnpkg run build to ensure I'm using master and the dist/build files which need to be built as well. Otherwise hoping @mfogel can do a new release with the latest fixes. |
|
Checked against master, the error is still there, any pointers of what it might be and how we might help to fix it? |
|
@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. |
|
I ran into this as well. Since the thrown error was specifically because there is no last matching segment yet there is a first segment. |
|
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 |
|
Seeing this as well on 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. |
Oooh, that's a great idea! I got so caught up in truncation/rounding, I'd forgot about that as an option =) |
|
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
} |
|
Yeah. Probably not. The whole library suffers from floating point rounding issues. As part of JSCAD, we are calculating an 'epsilon' of precision based on the scale of the shape. FYI, the EPS from constants.js is that for shapes scaled around 1.0. Not sure that will help, but might give you some more food for thought when 'rounding' those points. |
|
I was experiencing many issues with the // Utility to scale/round coords so we don't have rounding issues
const SCALE_FACTOR = 1e4;
const scaleFeature = function(feature, factor, doRounding) {
const round = (num)=>(doRounding ? Math.round(num) : num);
const geom = turf.invariant.getGeom(feature);
const recursiveScaler = function(arg) {
if (typeof arg[0]=='object') //array so recurse
return arg.map(recursiveScaler);
let [x,y] = arg;
return [round(x*factor), round(y*factor)];
};
geom.coordinates = geom.coordinates.map(recursiveScaler);
return geom;
};
// Scale a cloned copy so we don't modify original
let feature1Cloned = cloneDeep(feature1.geometry);
let feature2Cloned = cloneDeep(feature2.geometry);
scaleFeature(feature1Cloned, SCALE_FACTOR, true);
scaleFeature(feature2Cloned, SCALE_FACTOR, true);
// Ok, try the intersection again; if there is an intersection, then undo scaling on the intersection
intersectionFeature = turf.intersect(simplified, placeCloned);
if (intersectionFeature)
scaleFeature(intersectionFeature, 1/SCALE_FACTOR); |
|
I'm running into this using In my case, truncating to 6 or so significant digits is also fine, so truncating during internal calculations also helps, that would work for me, too. |
|
I've run into this error specifically when dealing with shapes that are practically on top of each other or overlapping. For example, here are all the bus stops in Bloomington, MN. I tried to build isochrones for each and union them, but for bus stops across the street from each other, the isochrones would be practically identical. Depending on what you are using the data for, you may be able to pre-process the data before attempting a
|
|
My issue was solved by switching to the |
|
I was wondering if there is any progress on this issue. I am running into the same problem. |
|
Like @markstos, I was able to resolve my issue by switching to polyclip. While it does appear that polygon-clipping and polyclip are written by the same people, for some reason polyclip is more reliable. |
just fix coordinates to 8~10 decimals |
|
@puxiao Why is that range magical? Why not 7-11? And why a range? Why not exactly 8 or 10? The comment you link to just says "use 8 to 10 decimals", so it doesn't really explain. My guess is this: When floating point math goes wrong, you end up with a case where you should get 1==1, but instead you get "1=0.9999999999999999999", so some equality check fails, like checking that the end point of a ring matches the beginning. I suspect the "8-10" suggestion is really the idea that if you truncate values enough, then you don't trigger the floating problems with small differences and end up with numbers that actually match. But if you search the source code of the |
|
Your are right. 0.1+0.2= 0.30000000000000004 Such contingencies are common. Emm.. only this option is available for the time being. |
I am getting the following error:
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:
Any idea why this might be happening?
The text was updated successfully, but these errors were encountered: