tmpvar/2d-polygon-boolean

perform boolean operations on arbitrary polygons in 2d

2d-polygon-boolean's Issues

Intersection should return more polygons

When performing a union (intersection), my subject polygon is an arbitrarily complex poly, and my clipping polygon is a rectangle horizontally across it. See this for an example:
http://geojson.io/#id=gist:anonymous/8234502304124f4a1445&map=10/-2.3106/-55.8133

When performing a clip between two polygons, I'm only getting one polygon as a result, whereas I should be getting two?

var poly = Polygon([
    Vec2(-56.03302001953125, -2.3559032430952156 ),
    Vec2(-55.99456787109375, -2.301016959572349 ),
    Vec2(-55.9423828125, -2.301016959572349 ),
    Vec2(-55.92315673828125, -2.3243438911424468 ),
    Vec2(-55.865478515625, -2.2776896463828633 ),
    Vec2(-55.81878662109375, -2.2790618517710675 ),
    Vec2(-55.76385498046875, -2.2790618517710675 ),
    Vec2(-55.71029663085937, -2.325716051620901 ),
    Vec2(-55.658111572265625, -2.3696244779626072 ),
    Vec2(-55.645751953125, -2.3998107149273102 ),
    Vec2(-55.57708740234375, -2.3902060750621508 ),
    Vec2(-55.556488037109375, -2.3613917533090936 ),
    Vec2(-55.51528930664062, -2.31611090028858 ),
    Vec2(-55.47683715820312, -2.3037613243448325 ),
    Vec2(-55.43426513671875, -2.3421818730368718 ),
    Vec2(-55.41778564453125, -2.3833455768534364 ),
    Vec2(-55.4205322265625, -2.44097268960325 ),
    Vec2(-55.513916015625, -2.52878066244035 ),
    Vec2(-55.865478515625, -2.51231711399721 ),
    Vec2(-55.9478759765625, -2.5562194448989453 ),
    Vec2(-56.023406982421875, -2.4656692707025414 ),
    Vec2(-56.03302001953125, -2.3559032430952156 )
]);

var clipper = Polygon([
    Vec2( -56.092071533203125, -2.806013679911073 ),
    Vec2( -56.092071533203125, -2.3435540161039135 ),
    Vec2( -55.34912109375, -2.3435540161039135 ),
    Vec2( -55.34912109375, -2.3806013679911073 ),
    Vec2( -56.092071533203125, -2.3806013679911073 )
]);
var clipped = poly.clip(clipper, 'union');

handle degenerecies

Confirmation of degeneracies were added as a test in 8b50945

http://arxiv-web3.library.cornell.edu/pdf/1211.3376v1.pdf is an extension of the Greiner-Hormann algorithm that apparently handles degeneracies

Error : when I use 'not' operation

   var subject = [
      [0, 0],
      [100, 0],
      [100, 100],
      [0, 100]
    ];
    
    var clip = [
      [40, 0],
      [60, 0],
      [60, 100],
      [40, 100]
    ];

    var cut = this.polygonBoolean(subject, clip, 'not');
    console.log('cut results', cut);

above is my code , what i expect is two rect [[0,0],[0,40],[40,100],[0,100]]and [[0,60],[60,100],[100,100],[60,100]]
but,your program return me a square [[40,0],[0,0],[0,100],[40,100],[60,100],[100,100],[100,0],[60,0],[40,0]]

can you fix this bug?

Strange behavior

Hello!

I ran into a rather strange behavior of the library. I think that all of the examples will be clear.

In both examples, the left side on the map can be set for the geometry subjectPolygon and clipPolygon (they can push and edit). On the map to the right shows the output for this example. The resulting polygons can pull apart to see in detail what happened.

Yellow polygon is a "clipPolygon"
Blue polygons is a "subjectPolygons"

Actually, the strange behavior is the first example - there is no right "and" polygon.

A second example, despite the fact that the geometry is really mad, everything works as it should.

What is the problem? Maybe I'm somewhere makes a mistake?

First (wierd) example - http://jsfiddle.net/romkachev/jjaaxnng/
Second (normal) example - http://jsfiddle.net/romkachev/c2o8816a/

P.S. Here is the listing of code on nodejs which process requests:

var express = require('express');
var polygonBoolean = require('2d-polygon-boolean');
var _ = require('lodash');
var router = express.Router();

router.get('/polygons-boolean', function (req, res) {
    res.header("Access-Control-Allow-Origin", "*");
    res.header("Access-Control-Allow-Headers", "X-Requested-With");

    var subjectPolygons = req.query['subjectPolygons'];
    var clipPolygon = req.query['clipPolygon'];
    var mode = req.query['mode'];

    var result = [];

    _.each(subjectPolygons, function (subjectPolygon) {
        var innerResult = [];
        // in case of polygons don't even intersects
        try {
            innerResult = polygonBoolean(subjectPolygon, clipPolygon, mode);
        } catch (e) {
        }

        if (innerResult.length) {
            _.each(innerResult, function (polygon) {
                result.push(polygon);
            })
        }
    });

    res.type('application/json');
    res.send(result);
});

module.exports = router;

PPS - sorry for my engrish.

README.md install command error

'and' thrown error

Is this line of code just saying that no results were found? If so I would prefer just returning empty rather than throwing an error. Not 100% sure if I'm interpreting it correctly.

use native arrays instead of vec2 to avoid peer conflicts

Right now the peer dependency on vec2 in polygon.clip prevents installation of a different version of vec2:

$ npm install vec2
npm http request GET https://registry.npmjs.org/vec2
npm http 304 https://registry.npmjs.org/vec2
npm http fetch GET https://registry.npmjs.org/vec2/-/vec2-1.6.0.tgz
npm http fetch 200 https://registry.npmjs.org/vec2/-/vec2-1.6.0.tgz
npm ERR! Linux 3.2.0-68-generic
npm ERR! argv "node" "/home/substack/prefix/bin/npm" "install" "vec2"
npm ERR! node v0.10.31
npm ERR! npm  v2.1.12
npm ERR! code EPEERINVALID

npm ERR! peerinvalid The package vec2 does not satisfy its siblings' peerDependencies requirements!
npm ERR! peerinvalid Peer [email protected] wants vec2@~1.4.0

npm ERR! Please include the following file with any support request:
npm ERR!     /home/substack/projects/svg-path-clip/npm-debug.log

This is similar to what was going on in voxeljs before threejs's native vectors were dumped in favor of native arrays, which works much better with different versions of packages.

implement XOR

polygon.clip example returns: TypeError: Object #<Object> has no method 'containsPoint'

I have bacially just copied the example code into this gist: https://gist.github.com/LarsBuur/c81af780283528b551af

Afterwards
npm install polygon.clip
npm install vec2
node app.js

---

/hidden/clip.js:149
var se = this.containsPoint(subjectList.vec);
^
TypeError: Object # has no method 'containsPoint'
at Object.Polygon.clip (/hidden/clip.js:149:17)
at Object. (/hidden/app.js:23:21)
at Module._compile (module.js:456:26)
at Object.Module._extensions..js (module.js:474:10)
at Module.load (module.js:356:32)
at Function.Module._load (module.js:312:12)
at Function.Module.runMain (module.js:497:10)
at startup (node.js:119:16)
at node.js:901:3

Containment Bug?

I am having problems with clipping when a subject is completely contained within the clipping polygon or vice versa. It seems to return just an empty array. This doesn't seem like expected behavior. I'd expect the result of the union to be the polygon that was contained. Thoughts? Thanks for the great library.

Cannot read property 'intersect' of null, generated within collectClipResults

I have been unable to find out exactly why the following causes an issue:

var subject = [
[ 129.25, 43.25 ],
[ 127.25, 43.25 ],
[ 127.25, 44.25 ],
[ 129.25, 44.25 ]
];
var clip = [
[ 129.25, 45.25 ],
[ 130.25, 45.25 ],
[ 130.25, 43.25 ],
[ 129.25, 43.25 ]
];
PolygonBoolean(subject, clip, 'or');

It seems crt is getting set to null within collectClipResults because it is getting replaced with crt.neighbor. This function works fine for hundreds of other attempts with other coordinates.

Thanks for you hard work on this library. It has proved invaluable.

difference in boolean operation definitions

union's behavior is more like an intersection boolean operation currently. It would be cool to be able to slice and dice polygons in a way that makes sense

• difference - remove clip poly from subject (functional)
• union - return the two polygons joined with no contained points remaining
• intersection - return the polygon represented by the intersection (currently what union is doing)

Maybe I'm thinking about this backwards due to the nature of this library, but I still think it's important to support the missing operation (it looks like we can build the remainder from the 3 ops).