Incorrect union edge case

[egjiri]

Hi,

I'm working on an application with places of complex boundaries and allow users to union them when desired. I have tried about 5 JS polygon libraries and I have to say yours is the best. They all error out on different edge cases but polybooljs seems to handle most cases well.

I have encountered a few edge cases where your polygon union I believe does not give accurate results.

Here is an example:

polygon 1 coords

[[[-79.28426250055173,43.68075543492089],[-79.28335754511745,43.67858119554888],[-79.28272426128387,43.67753878734541],[-79.28426250055173,43.68075543492089]]]

polygon 2 coords

[[[-79.2839527130127,43.67786274564595],[-79.28335754511743,43.67858119554888],[-79.2829332351944,43.67755625060114],[-79.2839527130127,43.67786274564595]]]

polybooljs union result of the above 2 polygons

[[],[[-79.28272426128387,43.67753878734541],[-79.28335754511737,43.67858119554873],[-79.2829332351944,43.67755625060114],[-79.2839527130127,43.67786274564595],[-79.28335754511743,43.67858119554888],[-79.28426250055173,43.68075543492089]]]

I am able to plot both my polygons on geojson.io but not the generated union polygon.

I would really appreciate if you could look into this and provide some guidance.

Thanks

[velipso]

I just published a pseudo-fix for this issue under v1.1.2.

The problem is the data. In particular, you have two points that are really close to each other, which is screwing up the floating point calculations:

poly1 has: [-79.28335754511745,43.67858119554888]
poly2 has: [-79.28335754511743,43.67858119554888]

Notice that these points only differ by the X coordinate at the 14th decimal place. This is a problem for the algorithm because the epsilon value defaults to 0.0000000001 (10 decimal places).

You might think a good solution would be to make the epsilon value more precise, but I wasn't able to find a value that worked. Either it was too sensitive or too rough.

I'm not entirely satisfied that the current epsilon code is the correct solution to these problems, and I would be open to someone taking the time to figure out a more reliable method for calculating the different functions inside of lib/epsilon.js.

The change I made will detect the zero-length segment during the last phase of the algorithm in order to skip over segments with zero-length. It also emits a warning. This fixes this test case, but I think it's possible you'll run into more issues in the future.

One way to permanently solve this (on your end) would be to clean up the coordinates before sending them to PolyBool by rounding all values to the 9th decimal place. I could easily do this inside of PolyBool but that feels more like a hack than the correct solution.

---

For posterity, opening up demo.html and pasting the following code into the browser's console will inject this test case into the program:

scaleToFit = true;
setMode('Union');
polyCases.push({
    name: '',
    poly1: {
        regions: [[
            [-79.28426250055173,43.68075543492089],
            [-79.28335754511745,43.67858119554888],
            [-79.28272426128387,43.67753878734541],
            [-79.28426250055173,43.68075543492089]
        ]],
        inverted: false
    },
    poly2: {
        regions: [[
            [-79.2839527130127,43.67786274564595],
            [-79.28335754511743,43.67858119554888],
            [-79.2829332351944,43.67755625060114],
            [-79.2839527130127,43.67786274564595]
        ]],
        inverted: false
    }
});
nextDemo(-1);

[velipso]

Also: I want to leave this issue open until a more permanent fix is written for the epsilon code. The current solution is good and works most of the time, but edge cases like this need to be better understood.

[egjiri]

Thanks for taking the tile to look into this issue. I updated to v1.1.2 and make changes to my code to truncate my points to 9 decimal places and the usecase above now works :)

Unfortunately those data points were a subset of my actual real data where each polygon has over 100 points and the above changes do not seem to work with this dataset. I had tried to reproduce the error with simpler polygons to better understand the problem and also make it easier to test.

For reference, my actual polygons that are now working are the following:

polygon 1 coords

[[[-79.283357545,43.678581196],[-79.282933235,43.677556271],[-79.282392574,43.676250248],[-79.282156448,43.675679843],[-79.281664513,43.674491451],[-79.281419073,43.673898512],[-79.281397446,43.673808559],[-79.28126301,43.673839287],[-79.28083745,43.672810987],[-79.280247762,43.671386034],[-79.280222389,43.671320812],[-79.280330283,43.671297371],[-79.280277846,43.671171578],[-79.280262414,43.671097384],[-79.280237508,43.670991746],[-79.280224361,43.670940718],[-79.280264293,43.67095892],[-79.280315921,43.671079908],[-79.280362214,43.671160336],[-79.280512968,43.671147724],[-79.280604426,43.671129859],[-79.280680883,43.671114924],[-79.280839281,43.671082129],[-79.280948937,43.671023525],[-79.281023201,43.670992551],[-79.281081693,43.670968155],[-79.281236935,43.670903647],[-79.281436991,43.670919027],[-79.281440864,43.670802993],[-79.281538987,43.670811654],[-79.281600659,43.670856826],[-79.281677497,43.670862839],[-79.281777828,43.67087069],[-79.281984628,43.670761882],[-79.282135016,43.670600762],[-79.282181235,43.670553503],[-79.282286839,43.67058545],[-79.28244715,43.670604501],[-79.282539159,43.670593295],[-79.282686946,43.670564818],[-79.282767301,43.670512672],[-79.282893193,43.670430977],[-79.282900624,43.67033609],[-79.28304449,43.670311578],[-79.283151094,43.670346114],[-79.283242239,43.670374827],[-79.283331504,43.670369244],[-79.283433369,43.670362872],[-79.283669945,43.670297838],[-79.283740747,43.670194884],[-79.28373448,43.670085435],[-79.283823193,43.670084489],[-79.283908412,43.670100857],[-79.283978326,43.670116451],[-79.284170603,43.670087478],[-79.284333271,43.670062597],[-79.28447264,43.670041164],[-79.284534606,43.670031635],[-79.284680941,43.670003149],[-79.284738129,43.66996855],[-79.284802023,43.669929893],[-79.28497326,43.669810911],[-79.285049358,43.669759602],[-79.285144359,43.669695547],[-79.285231236,43.66968383],[-79.285291751,43.669683506],[-79.285341015,43.669748252],[-79.285415038,43.669766785],[-79.285507421,43.669752738],[-79.28556783,43.669742845],[-79.285737379,43.66971579],[-79.285892025,43.669670574],[-79.286036708,43.669611453],[-79.286162825,43.669545329],[-79.286292698,43.669398281],[-79.286404968,43.669395245],[-79.286597571,43.669414081],[-79.286693662,43.669402347],[-79.286868866,43.669380952],[-79.287148943,43.669353081],[-79.287259367,43.669334085],[-79.287351921,43.669318162],[-79.287499221,43.669274914],[-79.287562455,43.66924206],[-79.287615809,43.669215482],[-79.287695798,43.669190881],[-79.28774803,43.66917292],[-79.287811148,43.669147793],[-79.287898359,43.66911092],[-79.287998525,43.669062607],[-79.288067113,43.668993933],[-79.288147783,43.66892626],[-79.288231801,43.668886894],[-79.288412587,43.668818509],[-79.288507107,43.668772367],[-79.28863772,43.668701248],[-79.288757978,43.668665777],[-79.28886174,43.668693813],[-79.288923599,43.668690103],[-79.289248167,43.669514871],[-79.289532739,43.66966646],[-79.290274839,43.67138608],[-79.290337214,43.671774819],[-79.290207202,43.671900175],[-79.290262221,43.672046052],[-79.290302604,43.67217372],[-79.29035878,43.672279412],[-79.290576775,43.672386761],[-79.290814144,43.672788483],[-79.291364836,43.673876061],[-79.291651894,43.674646472],[-79.291833633,43.674612881],[-79.292074541,43.675175899],[-79.292197904,43.675475619],[-79.291704395,43.675581448],[-79.291737488,43.675670003],[-79.292242315,43.675583511],[-79.292317813,43.675766908],[-79.292157831,43.675868616],[-79.292100011,43.676091982],[-79.291850924,43.676704894],[-79.291392776,43.677426793],[-79.291538173,43.677746629],[-79.291638987,43.677822876],[-79.292388441,43.677721964],[-79.292716099,43.677969775],[-79.292467007,43.678582686],[-79.291945437,43.678817809],[-79.292941179,43.680037527],[-79.292891443,43.680043121],[-79.292794826,43.68005394],[-79.292494474,43.680069305],[-79.292162605,43.680086342],[-79.292078738,43.680090684],[-79.292021064,43.680094959],[-79.291459297,43.680143762],[-79.291237843,43.680163704],[-79.29089653,43.680194401],[-79.29015205,43.680228599],[-79.289405389,43.680308856],[-79.288611585,43.680339498],[-79.288389275,43.680367999],[-79.28728967,43.680483878],[-79.286290488,43.680571666],[-79.286176344,43.680578774],[-79.285270152,43.680664095],[-79.285231873,43.680666367],[-79.285165531,43.680670306],[-79.284262501,43.680755435],[-79.283928885,43.679953912],[-79.283550606,43.679045058],[-79.283357545,43.678581196]]]

polygon 2 coords

[[[-79.301139094,43.686050646],[-79.301103005,43.6860616],[-79.30101767,43.686085627],[-79.300905837,43.686117116],[-79.30090052,43.686119663],[-79.300895368,43.686120064],[-79.300691408,43.686177299],[-79.300457655,43.686248322],[-79.299866348,43.686427981],[-79.299675981,43.686477703],[-79.299420478,43.686544437],[-79.298953314,43.686669129],[-79.298185549,43.686865038],[-79.297969112,43.686917419],[-79.297182788,43.687082149],[-79.296503238,43.687237606],[-79.29547923,43.687472176],[-79.294620774,43.687668814],[-79.294327964,43.687735084],[-79.293209458,43.687988219],[-79.292678861,43.688108297],[-79.290538179,43.688592717],[-79.289236299,43.688887299],[-79.287673118,43.689239667],[-79.287204373,43.687883351],[-79.286959547,43.687288882],[-79.286778407,43.686849045],[-79.286649815,43.686532062],[-79.286451944,43.686044301],[-79.28614114,43.685296511],[-79.286061607,43.685105154],[-79.285748289,43.684353138],[-79.28548395,43.683718666],[-79.28536819,43.683431462],[-79.285311044,43.683289679],[-79.285182391,43.682983901],[-79.28487865,43.682255622],[-79.28470919,43.68184688],[-79.284582021,43.681540141],[-79.284355767,43.680984482],[-79.284283541,43.680807105],[-79.283928885,43.679953912],[-79.283550606,43.679045058],[-79.283357545,43.678581196],[-79.282933235,43.677556271],[-79.282392574,43.676250248],[-79.282156448,43.675679843],[-79.281664513,43.674491451],[-79.281335635,43.673846411],[-79.28083745,43.672810987],[-79.280266811,43.671334739],[-79.280288547,43.671139652],[-79.280577811,43.671135058],[-79.280839281,43.671082129],[-79.281017944,43.670994744],[-79.281236935,43.670903647],[-79.281463458,43.670863175],[-79.281708453,43.670865261],[-79.281984628,43.670761882],[-79.28220103,43.670579905],[-79.282493154,43.670598898],[-79.282727124,43.670538745],[-79.282896908,43.670383533],[-79.283097792,43.670328846],[-79.28336012,43.670367454],[-79.283705346,43.670246361],[-79.283861103,43.670096808],[-79.284251937,43.670075038],[-79.284503623,43.670036399],[-79.284740364,43.669967197],[-79.285011309,43.669785256],[-79.285222449,43.669687628],[-79.285457826,43.669752655],[-79.285814702,43.669693182],[-79.286099767,43.669578391],[-79.286348833,43.669396763],[-79.286645616,43.669408214],[-79.286868866,43.669380952],[-79.287227293,43.669339602],[-79.287559162,43.669244152],[-79.287825009,43.669140726],[-79.288032819,43.66902827],[-79.288189792,43.668906577],[-79.288459847,43.668795438],[-79.288697849,43.668683513],[-79.28889267,43.668691958],[-79.289082409,43.668681626],[-79.289406962,43.668645408],[-79.289659897,43.668568832],[-79.289863755,43.668484741],[-79.290076523,43.668441679],[-79.290251121,43.66839155],[-79.290559481,43.668275889],[-79.290867125,43.668139072],[-79.291116253,43.668016145],[-79.29139158,43.667928424],[-79.291682464,43.667954636],[-79.291975116,43.667904364],[-79.292267142,43.667821805],[-79.292499531,43.667714376],[-79.292712176,43.667606404],[-79.292950388,43.667496445],[-79.293162031,43.667377678],[-79.293302333,43.667297086],[-79.293455719,43.667195444],[-79.293605088,43.66707857],[-79.29374058,43.666975237],[-79.293930017,43.666832578],[-79.294161982,43.666643746],[-79.294396638,43.666433327],[-79.294534728,43.66630591],[-79.294686609,43.666135129],[-79.29490816,43.665972398],[-79.295183136,43.666002015],[-79.295364045,43.665911813],[-79.29554068,43.665822087],[-79.295805453,43.665739557],[-79.295965426,43.66565958],[-79.296111106,43.665553378],[-79.296386437,43.665495998],[-79.296621311,43.665427644],[-79.296859909,43.66535193],[-79.297216808,43.665250189],[-79.29746616,43.665231336],[-79.297646786,43.665211855],[-79.297897591,43.6651989],[-79.298134313,43.665261297],[-79.298305234,43.665339004],[-79.298472836,43.665423777],[-79.298695373,43.665473398],[-79.298965034,43.665456113],[-79.299310901,43.6654355],[-79.299467259,43.66554589],[-79.299725,43.665600778],[-79.300009503,43.665526427],[-79.300234091,43.665431841],[-79.300867741,43.66626916],[-79.301014215,43.666519978],[-79.301066181,43.666608436],[-79.301714916,43.667718223],[-79.302356788,43.669395361],[-79.302084426,43.669504253],[-79.302500559,43.669490261],[-79.302812681,43.669782347],[-79.303232072,43.670756855],[-79.303274946,43.670856477],[-79.303352169,43.670985695],[-79.303398799,43.67115715],[-79.303529031,43.671361864],[-79.3037254,43.671567559],[-79.303865893,43.672060585],[-79.304018543,43.672383031],[-79.304106862,43.672640486],[-79.304109553,43.672805951],[-79.303986553,43.673257713],[-79.304010538,43.673450178],[-79.304168462,43.673754663],[-79.305207212,43.676381563],[-79.304923414,43.676548007],[-79.304717339,43.676680009],[-79.304564963,43.67674978],[-79.304339758,43.676858987],[-79.30409298,43.676963372],[-79.303580521,43.67717309],[-79.303156268,43.677346545],[-79.302688781,43.677537674],[-79.301697496,43.677942448],[-79.301378122,43.67807568],[-79.30120438,43.678155705],[-79.300960632,43.678244268],[-79.300677358,43.678350853],[-79.300164788,43.678448253],[-79.299838087,43.678508273],[-79.29913112,43.678637408],[-79.298528558,43.678765431],[-79.29860011,43.678953256],[-79.298643893,43.679202275],[-79.298822567,43.679486864],[-79.299000661,43.679668301],[-79.299225772,43.680131174],[-79.299051727,43.680382724],[-79.299162777,43.680503474],[-79.299566643,43.680959496],[-79.29990061,43.681611202],[-79.300113639,43.682102576],[-79.300152535,43.682288737],[-79.300243897,43.68241305],[-79.300603643,43.682996343],[-79.300615258,43.683473191],[-79.300664345,43.683797413],[-79.300801317,43.683913447],[-79.301006591,43.684193932],[-79.301304511,43.68483859],[-79.300698819,43.685015808],[-79.300786757,43.68522161],[-79.301139094,43.686050646]]]

From what I could tell the issue is related. Rounding the points to the 9th decimal place just shifts the data problem somewhere else. If the points are too close to each other on the 9th decimal place the same error occurs. Looking at the data I submitted in the first issue, I routed it and manually changed that last decimal place of the second point by 1

coods1 = [[
  [-79.2842625,43.68075543],
  [-79.28335755,43.6785812],
  [-79.28272426,43.67753879],
  [-79.2842625,43.68075543]
]]

coods2 = [[
  [-79.28395271,43.67786275],
  [-79.28335754,43.6785812],
  [-79.28293324,43.67755625],
  [-79.28395271,43.67786275]
]]

Now the points [-79.28335755,43.6785812] and [-79.28335754,43.6785812] are still too close and they error.

I just wanted to provide these more usecases as we try to solve this.

Please let me know if you have any suggestions that I can persue and I'll also try to delve a bit into lib/epsilon.js as you mentioned and see if I can uncover anything there.

Thanks

[egjiri]

Woups, looks like in the last example is have truncated the data to 8 decimal places instead of 9. In any case the problem is the same, weather 8 or 9 decimal places. A slight change in the last point results in an error

[velipso]

Just out of curiosity, what happens if you round to something more extreme, like the 4th decimal place? It should easily work at that resolution, so if it still doesn't work, then something more serious might be wrong.

[egjiri]

It still doesn't work. It looks like if the last digit on one point is different it doesn't work, at least for this dataset.

Here is the data

var coords1 = [[
  [-79.2843,43.6808],
  [-79.2834,43.6786],
  [-79.2827,43.6775],
  [-79.2843,43.6808]
]]

var coords2 = [[
  [-79.284,43.6779],
  [-79.2833,43.6786],
  [-79.2829,43.6776],
  [-79.284,43.6779]
]]

The slight difference is 79.2834 and 79.2833

[velipso]

Hmm okay, maybe it isn't an epsilon problem after all then -- I'll have to look into this more deeply. Thanks for your help.

[velipso]

Are you sure rounding to 4 places doesn't work? When I load your test data into the demo.html file, it works fine for me.

scaleToFit = true;
setMode('Union');
polyCases.push({
    name: '',
    poly1: {
        regions: [[
            [-79.2843, 43.6808],
            [-79.2834, 43.6786],
            [-79.2827, 43.6775],
            [-79.2843, 43.6808]
        ]],
        inverted: false
    },
    poly2: {
        regions: [[
            [-79.2840, 43.6779],
            [-79.2833, 43.6786],
            [-79.2829, 43.6776],
            [-79.2840, 43.6779]
        ]],
        inverted: false
    }
});
nextDemo(-1);

[egjiri]

Sorry, that does seem to work. I was messing with a few things and might have made a mistake somewhere.

[velipso]

Okay, so rounding to some decimal level (7 places? 8 places?) should be a hacky fix for you, for the time being. I don't have the time to look at lib/epsilon.js at the moment to dig into the floating point complexity, but I'll add it to my TODO list. If you or anyone else decides to take a look and figure it out, just ping me and I'll take a look.

[egjiri]

Thank @voidqk i think I'm gonna delve into lib/epsilon.js now myself.

[egjiri]

I made a bunch of changes to lib/epsilon.js and seem to have made it more resilient, at least to my data. Most of my usecases are now working although there are still a couple edge cases where I don't get the desired behaviour so I wouldn't call this done just yet.

You can take a look at my changes so far and let me know what you think https://github.com/egjiri/polybooljs/commit/77ef05b9391a8bb492d4c7c5ce7fa4650669ce91

I'll see if I can take it all the way and make a PR.

Do you have a test suite or anything to run this against? Right now I'm going off my data but I want to make sure all the scenarios you've tested against are still working.

[velipso]

I think you have the right idea. I like the idea of rounding all values according to the epsilon. There is some sort of bug though, see attached image.

I believe the bug is in linesIntersect, because you are always using the X coordinate when calculating the alongA/alongB values: here.

These values need to take both X and Y into account in order to calculate where the intersection happens.

[egjiri]

Thanks for the tip @voidqk, I made some changes to my intersectionAlong function to also take into account Y. That example in the demo now works well.

I still a few issues remaining however.

I have compiled a list on the Readme of my fork https://github.com/egjiri/polybooljs#fork-remaining-issues if you want to take a look

[egjiri]

I made one more fix on my fork and now most of the issues are fixed except for a couple of extra points and undesired lines that still need to be fixed.

This is probably the worst example:

Other than this I have one remaining issue with my data where I get a console error and I think we're getting close

[velipso]

Well I found one potential issue, inside pointsCollinear:

https://github.com/egjiri/polybooljs/blob/master/lib/epsilon.js#L70

By comparing the slopes in this manor, a vertical line will have an infinite slope, because deltaX will be 0, which will produce a divide by zero. This is why test case 12 doesn't correctly remove the extra vertices. I will continue to poke around.

[egjiri]

I changed my code to account for the divide by zero and also tried to revert the code on that function to what it was originally but I'm still seeing the same issues I've listed. The problem must be somewhere else