mfogel / polygon-clipping

Apply boolean polygon clipping operations (union, intersection, difference, xor) to your Polygons & MultiPolygons.
MIT License
543 stars 63 forks source link

Error: Unable to complete output ring when subtracting polygons with collinear edges #141

Open BadIdeaException opened 1 year ago

BadIdeaException commented 1 year ago

I am using this on production data to perform pairwise difference operations on polygons, and am getting a lot of errors ("unable to complete output ring") when the two polygons have a collinear edge. One example:

var polygonClipping = require("polygon-clipping")

let A = [[
    [0.07131661646825423,1.2035759718134211],
    [0.9757440430556349,1.294546613586706],
    [1.075547467556301,1.6413473673458308]
]]

let B = [[
    [1.6284121572971344,1.6568617522716522],
    [1.1186468601226807,1.791110783815384],
    [0.6031952991119243,0]
]];

polygonClipping.difference(A,B)

This errors saying Error: Unable to complete output ring starting at [0.07131661646825423, 1.2035759718134211]. Last matching segment found ends at [0.9757440430556349, 1.294546613586706]. The error disappears if I shift point A[2] to the right by 0.2 (although not when shifting by 0.1, strangely.) Here is an image of the constellation:

Screenshot from 2022-09-24 17-58-14

However, it seems that collinear edges are not a problem per se, because this works:

let A = [[
    [ 1.0, 1.0 ],
    [ 3.0, 1.0 ],
    [ 1.0, 3.0 ]
]]
let B = [[
    [ 2.5,1.0 ],
    [ 1.5,1.0 ],
    [ 2.0,0 ]
]]