w8r / greinerhormann Goto Github PK

Hello,
I have a case where I intersect 2 convex polygons and the result of the intersection is not correct. Here is a piece of code:

var poly1 = [[175, 105],
                [130, 60],
                [210, 45],
                [215, 65]];

    var poly2 = [[256, 106],
                [207.14285714285714, 57.14285714285714],
                [215, 0],
                [256, 0]];

var intersection = greinerHormann.intersection(poly1, poly2);
/*
gives:
[208.78107457898957, 45.22854851643946],
[210, 45],
[215, 65],
[175, 105], <-- should not be here, belongs to poly1 only
[130, 60], <-- should not be here, belongs to poly1 only
[208.78107457898957, 45.22854851643946]

While it should give:
[207.14285714285714, 57.14285714285714],
[208.78107457898957, 45.22854851643945],
[210, 45],
[215, 65]

I am not sure what's going wrong, and if I use .intersection(poly2, poly1) instead of .intersection(poly1, poly2), it gives me two points of poly2 that should not be there either.

To get the proper result I used PolyBool js, which is 2.5x slower...
Cheers.
Jo.

I am pretty stunned that in such project that involves a lot of math, the documentation calls difference as XOR. Both operations are totally different: XOR is a symmetric difference, resulting in areas not included in the intersection. From the documentation I went and wrote code that created intersection and performed xor on the initial polygon and the intersection to get the difference, and the behaviour was weird. Then I look closely on the example and find out that there is actually no XOR support whatsoever.

Clipping of Arbitrary Polygons with Degeneracies Erich L Foster and James Overfelt, 2012

var greinerHormann = require('greiner-hormann');
var intersection = greinerHormann.intersection([[1,1],[2,1],[2,2],[2,1],[1,1]], [[1,1],[3,2],[2,2],[2,1],[1,1]]);
var out = []
if(intersection){
    if(typeof intersection[0][0] === 'number'){ 
        out = [intersection]
        console.log("single linear ring")
    }
    console.log("length:"+intersection.length)
    for(var i = 0, len = intersection.length; i < len; i++){
        out.push([intersection[i]])
    }
} else {console.log("no intersection")}
console.log("output"+out)

Gives:
length:1
output2,1.5,2,1,1,1,1,1,2,1,2,2,2,1.5

????

Probably related to #9:

union of non-intersecting polygons returns null here, but returns the input polygons with "martinez".

> m.union([ pencilPolygon.map(p2arr) ], [ eraserPolygon.map(p2arr) ]);
[ [ [ 0.11612903225806452, 0.33455451259745367 ],
    [ 0.11720430107526882, 0.33455451259745367 ],
    [ 0.11720430107526882, 0.33064826259745367 ],
    [ 0.11612903225806452, 0.33064826259745367 ] ],
  [ [ 0.14516129032258066, 0.4109600939072074 ],
    [ 0.14623655913978495, 0.4109600939072074 ],
    [ 0.14623655913978495, 0.3718975939072074 ],
    [ 0.14516129032258066, 0.3718975939072074 ] ] ]
> gh.union(pencilPolygon, eraserPolygon)
null

with below polygons, it does not provide same results doing intesrection A and B or B and A.

let polyA = [
    [49.05351, 1.44728],
    [48.43959, 1.88663],
    [48.77105, 2.22033],
    [48.98882, 2.12906],
    [49.05351, 1.44728]
];
let polyB = [
    [48.33984375, 1.93359375],
    [48.515624999, 1.93359375],
    [48.515624999, 2.109374999],
    [48.33984375, 2.109374999],
    [48.33984375, 1.93359375]
];

console.log(GreinerHormann.intersection(polyA, polyB));
console.log(GreinerHormann.intersection(polyB, polyA));

Not sure whether this is a bug or a lack in my understanding:

I got surprised that I get an null result for the diff of non-intersecting polygons.

Is this expected and should my code first check whether the polygons are intersecting and only then try to calculate the diff?

Examples

const gh = require('greiner-hormann')
const pencilPolygon = [{"x":0.11612903225806452,"y":0.33455451259745367},{"x":0.11720430107526882,"y":0.33455451259745367},{"x":0.11720430107526882,"y":0.33064826259745367},{"x":0.11612903225806452,"y":0.33064826259745367}];
const eraserPolygon = [{"x":0.14516129032258066,"y":0.4109600939072074},{"x":0.14623655913978495,"y":0.4109600939072074},{"x":0.14623655913978495,"y":0.3718975939072074},{"x":0.14516129032258066,"y":0.3718975939072074}];

gh.diff(pencilPolygon, eraserPolygon); // -> null
gh.intersection(pencilPolygon, eraserPolygon); // -> null

I would assume either one or the other to return something. In this case diff returning the pencilPolygon.

Polygon.clip method has n^2 complexity.
Try https://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm or linear quad tree(via Z code), as earcut do.

When polygon is not closed, everything is OK
When polygon is closed (firstPoint==lastPoint), the intersection is weird. Weird means

FWIW, @jasondavies is utilizing Greiner-Hormann for D3's polygon clipping operations (2D and spherical). He recently gave a demo of boolean operations on polygons based on as-of-yet unreleased work here.

Earlier clipping demos here and here.

Anyway ... he writes high quality stuff so may be worth comparing implementations.

Hi !
i had a question concerning the intersections,
if the clipper is the same size as the source polygon, why doesnt it return the on-line intersection ?
var src = [[0,0], [100,0], [100,100], [0,100]];
var clipper = [[0,0] , [100,0] , [100,100], [0,100]];
it returns null, could you comfirm the behaviour ? thx

var selfpointvec = [{"x":0,"y":0},{"x":10,"y":10},{"x":15,"y":5},{"x":20,"y":10},{"x":25,"y":0}];
var otherpointvec = [{"x":6,"y":6},{"x":8,"y":8},{"x":25,"y":8},{"x":25,"y":6}];
let m = clip(selfpointvec,otherpointvec, false, true);
for(var i = 0;i<m.length;i++) {
console.log(JSON.stringify(m[i]));
}
/****************/
[{"x":12,"y":8},{"x":10,"y":10},{"x":0,"y":0},{"x":25,"y":0},{"x":22,"y":6},{"x":25,"y":6},{"x":25,"y":8},{"x":21,"y":8},{"x":20,"y":10},{"x":18,"y":8},{"x":12,"y":8}]
[{"x":14,"y":6},{"x":15,"y":5},{"x":16,"y":6},{"x":14,"y":6}]

Only intersection, union, difference

• browserify modules
• new pip
• 3 different build combinations in src
• standalone, externs

Hi, I see there are a CDN at cdn.rawgit.com, but it is not updated.. There are a newer one?

Hi,

Could you publish this as a Node module and publish it on NPM? It would be great!

Thanks in advance.

Tcherno