w8r / martinez

Martinez-Rueda polygon clipping algorithm, does boolean operation on polygons (multipolygons, polygons with holes etc): intersection, union, difference, xor

Martinez-Rueda polygon clipping algorithm

Details

The algorithm is specifically fast and capable of working with polygons of all types: multipolygons (without cascading), polygons with holes, self-intersecting polygons and degenerate polygons with overlapping edges.

Example

Play with it by forking this Codepen

import * as martinez from 'martinez-polygon-clipping';
const gj1 = { "type": "Feature", ..., "geometry": { "type": "Polygon", "coordinates": [ [ [x, y], ... ] ]};
const gj2 = { "type": "Feature", ..., "geometry": { "type": "MultiPolygon", "coordinates": [ [ [ [x, y], ...] ] ]};

const intersection = {
  "type": "Feature",
  "properties": { ... },
  "geometry": {
    "type": "Polygon",
    "coordinates": martinez.intersection(gj1.geometry.coordinates, gj2.geometry.coordinates)
  }
};

API

• .intersection(<Geometry>, <Geometry>) => <Geometry>
• .union(<Geometry>, <Geometry>) => <Geometry>
• .diff(<Geometry>, <Geometry>) => <Geometry>
• .xor(<Geometry>, <Geometry>) => <Geometry>

<Geometry> is GeoJSON 'Polygon' or 'MultiPolygon' coordinates structure. <Operation> is an enum of { INTERSECTION: 0, UNION: 1, DIFFERENCE: 2, XOR: 3 } in case you have to decide programmatically which operation do you need

Benchmarks

Hole_Hole
Martinez x 29,530 ops/sec ±1.65% (85 runs sampled)
JSTS x 2,051 ops/sec ±2.62% (85 runs sampled)
- Fastest is Martinez

Asia union
Martinez x 9.19 ops/sec ±3.30% (26 runs sampled)
JSTS x 7.60 ops/sec ±4.24% (23 runs sampled)
- Fastest is Martinez

States clip
Martinez x 227 ops/sec ±1.10% (82 runs sampled)
JSTS x 100 ops/sec ±2.54% (73 runs sampled)
- Fastest is Martinez

Features

The algorithm of Martinez et al. was extended to work with multipolygons without cascading.

Authors

• Alexander Milevski
• Vladimir Ovsyannikov

Based on

• A new algorithm for computing Boolean operations on polygons (2008, 2013) by Francisco Martinez, Antonio Jesus Rueda, Francisco Ramon Feito (and its C++ code)

License

The MIT License (MIT)

Copyright (c) 2018 Alexander Milevski

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

martinez's Issues

Algorithm based on 2013 paper

Hi, i've been looking into the Martinez algorithm lately and i understand this implementation is based on the 2009 paper / implementation, and was wondering why you choose it over the 2013 paper ( + implementation ) titled "A simple algorithm for Boolean operations on polygons" by the same author, which is supposed to be simpler and faster. Are you planning to implement this newer algorithm?

Overlapping edges drops some vertices

When I try to intersect shape1 and shape2, I get something back like shape2, but which is missing vertex 3. I expect the result to be the same shape as shape2.

........0.................
:     /   \              :  <---- shape1
:   /       \            : 
:5/    3     \1          :
:  \   / \   /           :
:   \ /   \ /  <---------:----shape2
:    4     2             :
:........................:

var shape1 = [
          [291.3333333283663,259.3333333333333],
          [291.3333333283663,139.33333333333331],
          [1491.3333333283663,139.33333333333331],
          [1491.3333333283663,259.3333333333333]
        ]

var shape2 = [
          [355.9999999950329,139.33333333333331],
          [420.9999999950329,202.33333333333331],
          [384.3333333283663,237.66666667163372],
          [353.9999999950329,205.33333333333331],
          [330.6666666616996,230.33333332339922],
          [291.3333333283663,197.33333333333331]
        ]

In codepen here https://codepen.io/anon/pen/OmeeLY

intersection() fails if one polygon has no area.

This is probably in the category of just handling invalid input. See my comments below that seek to clarify the contract of the API. I'm willing to add a quick PR fix for this, depending on what the solution should be.

 const notQuiteAPolygon = [[[-93.621844, 44.154535],[-93.621672, 44.154625],[-93.621844, 44.154535]]];
const aPolygon = [[[-93.621887, 44.154764],[-93.621844, 44.154535],[-93.621672, 44.154625],[-93.621887, 44.154764]]];
intersect(aPolygon,notQuiteAPolygon); // Fails with connectEdges() infinite inner loop 

The above code causes the inner loop inside of connectEdges() to loop forever and crash the JS execution environment. (My loop guard PR is coming for this.)The first polygon only contain 2 points (3 including closing), so it's really just a line. If I add one more unique point to the first polygon, the test passes.

The question I have is whether you want to interpret this as valid input or not. I know the TurfJS people have asked for clipping functions that work with points and line segments. (Although, I think if we did pass a set of LineString coordinates, it should probably be just 2 levels of array depth.)

If it is valid input, I think you'd want execution to branch to a more trivial evaluation of the intersection, or at least a change that prevents connectEdges() from freaking out. Especially, if that helps avoid adding special case logic inside of loop-iterated code of connectEdges() (performance and readability).

If it's not valid input, I think it would be good to throw an early exception instead of descending into connectEdges().

Crash during union operation - Cannot read property 'push' of undefined

This generates a crash:

const martinez = require('martinez-polygon-clipping')

const p1 = [
  [[12.91,6.09],[12.91,6.91],[12.09,6.91],[12.09,6.09],[12.91,6.09]]
]

const p2 = [
  [[12.75,6.25],[12.75,6.75],[11.75,6.75],[11.75,8.25],[12.75,8.25],[12.75,8.75],[11.75,8.75],[11.75,9.75],[11.25,9.75],[11.25,8.75],[10.25,8.75],[10.25,8.25],[11.25,8.25],[11.25,6.75],[10.25,6.75],[10.25,6.25],[12.75,6.25]],
  [[4.75,2.25],[4.75,2.75],[4.25,2.75],[4.25,2.25],[4.75,2.25]]
]

martinez.union(p1, p2)

Stack trace:

$ node foo.js 
/Users/josephg/src/b/svg/node_modules/martinez-polygon-clipping/src/index.js:490
      result[result.length - 1].push([contour]);
                               ^

TypeError: Cannot read property 'push' of undefined
    at connectEdges (/Users/josephg/src/b/svg/node_modules/martinez-polygon-clipping/src/index.js:490:32)
    at boolean (/Users/josephg/src/b/svg/node_modules/martinez-polygon-clipping/src/index.js:627:10)
    at Object.module.exports.union (/Users/josephg/src/b/svg/node_modules/martinez-polygon-clipping/src/index.js:635:10)
    at Object.<anonymous> (/Users/josephg/src/b/svg/foo.js:13:10)

Union operation splitting the resulting polygon in two

Hi, we're using your library and it's working out good so far (at least when rounding the input values onto a certain grid), but sometimes the union doesn't behave like it should. Instead, its output is multiple polygons

I've managed to extract the relevant polygons into a CodePen here (use the union mode).
Here's a screenshot for a quick look:

Is this something you have encountered before perhaps? Thanks a lot for your help :)

Crash: JavaScript heap out of memory

Stack trace is from 0.4.1:

<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x223684e25879 <JSObject>
    1: connectEdges(aka connectEdges) [/Users/seth/src/americanredcross/osm-stats-workers/node_modules/martinez-polygon-clipping/dist/martinez.umd.js:~1389] [pc=0x30a376e96f73](this=0x22360a3822d1 <undefined>,sortedEvents=0x223662602451 <JSArray[2801]>,operation=0)
    2: boolean(aka boolean) [/Users/seth/src/americanredcross/osm-stats-workers/node_modules/martinez-polygon-clipping/dist/martinez...

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
 1: node::Abort() [/Users/seth/.nvm/versions/node/v8.11.2/bin/node]
 2: node::FatalException(v8::Isolate*, v8::Local<v8::Value>, v8::Local<v8::Message>) [/Users/seth/.nvm/versions/node/v8.11.2/bin/node]
 3: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [/Users/seth/.nvm/versions/node/v8.11.2/bin/node]
 4: v8::internal::Factory::NewUninitializedFixedArray(int) [/Users/seth/.nvm/versions/node/v8.11.2/bin/node]
 5: v8::internal::(anonymous namespace)::ElementsAccessorBase<v8::internal::(anonymous namespace)::FastPackedObjectElementsAccessor, v8::internal::(anonymous namespace)::ElementsKindTraits<(v8::internal::ElementsKind)2> >::GrowCapacity(v8::internal::Handle<v8::internal::JSObject>, unsigned int) [/Users/seth/.nvm/versions/node/v8.11.2/bin/node]
 6: v8::internal::Runtime_GrowArrayElements(int, v8::internal::Object**, v8::internal::Isolate*) [/Users/seth/.nvm/versions/node/v8.11.2/bin/node]
 7: 0x30a376c042fd
 8: 0x30a376e96f73

Geometry being intersected:

{
    "type": "Polygon",
    "coordinates": [
      [
        [
          85.0801983,
          26.9416201
        ],
        [
          85.0801983,
          26.9416201
        ],
        [
          85.0802667,
          26.9416093
        ],
        [
          85.0802667,
          26.9416093
        ],
        [
          85.0801983,
          26.9416201
        ]
      ]
    ]
  }

The larger geometry is China from Natural Earth, so they're both in this gist: https://gist.github.com/mojodna/4a98b2c0bb44e0224a3bce52aebb5000

Dissolve : Please have a talk with voidqk/polybooljs

In here we are trying to "dissolve" a huge mass of geojson Polygons / MultiPolygons.

We naturally thought of making a successive and recursive union, with that

  const dissolved = polygons.reduce(
    (dissolvedAccumulator, feature) => (
      (!dissolvedAccumulator && feature) ||
      union(dissolvedAccumulator, feature)
    ),
    null
  )

(This simple implementation uses turf.union, which uses w8r/martinez under the hood. I also tested it with raw w8r/martinez.union, please trust me)

We are encountering bugs like this :

The base "larger" polygon has many holes, and you can see some are respected, others are curiously understood as other polygons, which comes "over" the first.

I cannot really provide any dataset, because this one is huge, and I could not reproduce on a smaller one.

One the other side, voidqk/polybooljs perfectly succeed in dissolving the whole. See

... but it takes like 20 seconds to achieve this, whereas w8r/martinez takes under 400ms...

Sooo, is there a chance we can engage in a discussion between the 2 repos, to come up with a solution fully working, in less than 400ms ? 😄

(Note: I duplicated the issue there)

Failure in intersection()

let p1 = [[-19.304686742200616, 126.92383121744365],
	  [-19.304686742200587, -357.48241878255635],
	  [10.695313257799413, -357.48241878255635],
	  [10.695313257799384, 126.92383121744365]];
let p2 = [[-96.66033269728321, -107.63400219275148],
	  [13.370917302716792, -107.63400219275148],
	  [13.370917302716792, -126.63400219275148],
	  [-96.66033269728321, -126.63400219275148]];
let result = Martinez.intersection([p1],[p2]);

Results in:

Uncaught TypeError: Cannot read property 'point' of undefined
    at connectEdges (martinez.js:1157)
    at boolean (martinez.js:1415)
    at Object.boolean.intersection (martinez.js:1436)

According to PolyBool, the result should be

[10.695313257799397, -107.63400219275148]
[10.695313257799398, -126.6340021927515]
[-19.3046867422006, -126.6340021927515]
[-19.3046867422006, -107.63400219275148]

Buggy output +warnings for "touching" polygons

Hi,

I know touching polygons are probably considered an edge case, but I'd like to supply a test case where the clipping algorithm produces buggy results:

Codepen

Situation:

Big: [[0, 0], [3, 0], [3, 3], [0, 3], [0, 0]]
Small: [[3, 1], [4, 1], [4, 2], [3, 2], [3, 1]]

First case: Union produces a polygon which consist out of the merged surfaces (good), but also a degenerated polygon with only two points (less good):

[
  [[0,0],[3,0],[3,1],[4,1],[4,2],[3,2],[3,3],[0,3],[0,0]],
  [[3,2],[3,3]]
]

Second case: Diff misses the upper left corner and produces a triangular polygon with a collinear point:

[
   [[0,0],[3,0],[3,1],[3,2],[3,3],[0,0]]
]

Warning in all cases: "Edges of the same polygon overlap" [3, 1] [3, 3] [3, 2] [3, 3] - this is neither the input data nor the output data - so probably some in between (internal) result?

From the polygon clipping libraries I tested so far, this one works best. How can I best help you resolve this issue?

Mourner ESLint config

Have you considered using eslint-config-mourner? It's very similar to your current eslint config file and you can easily include it in your package.json instead of defining each specific rule yourself in the .eslintrc.

Mourner's linter is strict when writing in ES5, however it does allow ES6 syntax for your tests (it's painful writing tests in pure ES5).

Dead code - Condition is always true

I am working on porting this to Scala and have noticed that the condition on Line 363 of index.js is checking equality between 2 different types which will always have the same outcome.
Based on the https://github.com/mikolalysenko/functional-red-black-tree source and when debugging, prev.node in this context will be a RBNode and sweepLine.begin will be a RedBlackTreeIterator. So this condition will always return true for not equal.
Additionally, what is the purpose of these 2 lines in the following else block?

prev.prev();
prev.next();

If I am just missing something here, an explanation would be appreciated. Thanks!

Drop test/fixtures from npm bundle

Notice the published npm library contains all the test/fixtures which is about 6.7MB (95% of the size of the library).

https://unpkg.com/[email protected]/test/fixtures/

$ du -h
4.0K	./demo/css
260K	./demo/js
272K	./demo
 64K	./dist
 64K	./src
6.7M	./test/fixtures
6.7M	./test
7.2M	.

Wrong result for union operation

Hi, thanks for creating this library!

I am getting wrong results when using the union operation for this specific case:

• big rectangle (grey): [[-25,-25],[25,-25],[25,25],[-25,25]]
• small rectangle (red): [[-26,-22.5],[-26,-27.5],[-15,-27.5],[-15,-22.5]]
• union result (cyan): [[-26,-27.5],[-15,-27.5],[-15,-25],[25,-25],[25,25],[-26,-27.5]]

(svg coordinates, so origin is in the center, y-plus goes downwards)

The union result has a duplicate point and is missing one point of the original input. Any thoughts, am I doing something wrong?

Edges of the same polygon overlap

Can you please explain it?

Return values - Polygon vs MultiPolygon

Hi,

I have a question regarding the return values of the operations - more specifically, in what cases is a MultiPolygon (since the API docs specify <Geometry> as either Polygon or MultiPolygon) returned?

Take this example looking at the difference operation:

The big polygon is split in two by the smaller polygon - so far so good. However, the return value is one Polygon with a hole (with the hole not being within the outline, which makes not that much sense):

returnValue = [
  [[0,0],[2,0],[2,1],[0,1],[0,0]], //Left polygon (first array = outline)
  [[3,0],[4,0],[4,1],[3,1],[3,0]]  //Right polygon (all subsequent arrays = holes)
]

I did expect a MultiPolygon return value, since the two polygons aren't connected to each other anymore, so a value like:

returnValue = [
  //First polygon with only an outline
  [
    [[0,0],[2,0],[2,1],[0,1],[0,0]] 
  ],
  //Second polygon with only an outline
  [
    [[3,0],[4,0],[4,1],[3,1],[3,0]]
  ]
]

Is this a known limitation / a bug / should that be like this?

Thanks 😄 !

Union show hole as multipolygon

When I arrange multiple polygons in a way so that they should form a polygon with a hole, the resulting geoJson is formated as if the hole is another polygon in the multipolygon
[
[ [ outer polygon ] ],
[ [ inner polygon/hole ] ]
]
Whereas it should be
[
[ [ outer polygon ],
[ inner polygon/hole ] ]
]
I have an example (strangly it shows correct, in the viewer, but with F12 you'll see the wrong geoJson
https://codepen.io/Sakke/pen/aYbeEM?editors=0010

The following example is related and does show the error in the viewer:
When I add an additional polygon (making it a true multipolygon), then I also goes wrong.
https://codepen.io/Sakke/pen/dmPoMp?editors=0010

Incorrect inner ring added to diff result.

This is similar to #68 but maybe different:

The code below attempts to subtract the square (with the hole) from the triangle.

var arg1 = [[[2, 0],[10, 10],[10, 0],[2, 0]]];
var arg2 = [[[5, 1],[12, 1],[12, 9],[5, 9],[5, 1]],[[6, 2],[11, 8],[6, 8],[6, 2]]];
var d = diff(arg1, arg2);
console.log(JSON.stringify(d));

Output of log above:

[[[[2,0],[10,0],[10,1],[5,1],[5,3.75],[2,0]],[[6,2],[10,6.800000000000001],[10,8],[8.399999999999999,8],[6,5],[6,2]]],[[[9.2,9],[10,9],[10,10],[9.2,9]]]]

This produces a nifty-looking multipolygon like this:

The middle shape is actually an inner ring, and it should be present in the result as a POLYGON--not an inner ring. As it stands, the inner ring is not contained by an outer ring, so makes objectively incorrect geoJson as well. My hunch is there is some bug with setting the status to "inside" or "outside" during sweep evaluation, but I am just learning how the Martinez algorithm works and reluctant to jump into the deeper code to make changes. (At least today, I am. :) )

Better support for polygons with holes and multipolygons

Gday @w8r

I'm just thinking through how we can better support polygons with holes and multipolygons to get the ball rolling on this issue...

Currently the input is simply the coordinates array which is obviously limited. One option would be to go up a level in the geojson heirachy to the geometry object which includes the type such as Polygon or MultiPolygon. That would more clearly align the input to the geojson spec which probably is a pro (although possibly a con for those unfamiliar with geojson). Alternatively we could come up with a suitable object to use an input format

• I don't think it'a great idea for us to try and 'guess' whether the user is trying to input a multipoly or poly with a hole so I'd prefer a more structured input approach

Is this a reasonable starting point for this, to start by addressing the format of the input polys?

cc @DenisCarriere

Wrong intersection

Pictures show themselves, where the green square in the first picture is the clipping polygon, the weird polygon in the second picture is the result which doesn't looks good.


The GeoJSON files can be found here.

intersection() infinite loop for valid MultiPolygons.

I tried to narrow this down as tight as I could. The initial polygons that generated the error had many more points, but I removed as many as possible to still produce the error. This call below will cause an infinite loop and crash the JS stack:

const multiPolygon1 = [
          [
            [
              [-89.7235275385363, 42.0439388757895],
              [-89.7237188969195, 42.0442244474719],
              [-89.7237975, 42.0456047],
              [-89.7235275385363, 42.0439388757895]
            ]
          ],
          [
            [
              [-89.7214720193067, 42.042492561329],
              [-89.7161784, 42.046186],
              [-89.7195447358245, 42.042911552283],
              [-89.7214720193067, 42.042492561329]
            ]
          ]
        ];
const multiPolygon2 = [
          [
            [
              [-89.7232165, 42.0413833],
              [-89.723708, 42.0440331],
              [-89.7237975, 42.0456047],
              [-89.7145748, 42.0462076],
              [-89.7144372, 42.0462097],
              [-89.7239301, 42.0397921],
              [-89.7232165, 42.0413833]
            ]
          ],
          [
            [
              [-89.7240178, 42.0405696],
              [-89.7239695, 42.0422763],
              [-89.7236804, 42.0423162],
              [-89.7240178, 42.0405696]
            ]
          ]
        ];
intersection(multiPolygon1, multiPolygon2);

I stepped through it in the debugger. connectEdges() gets caught in an endless loop on the i=6 iteration of the for(i = 0 loop. More specifically in the inner while(pos >= i) loop where nextPos() continuously returns 12 for the next pos value, and the same coordinate is added to resultEvents until the JS stack runs out of memory.

It's a little tough for me to understand how the code is meant to work with my current ignorance, or I would probably just fix the bug and send you the fix. I'll keep messing around with it. Insights, ideas, or of course, your own bug fix would be very welcome.

Fails Simple Union / Intersection

        let poly1 = [[0, 0],[22.75, -12],[22.75, 0]];
	let poly2 = [[-2.42, 0],[-2.42, -5.45],[2, 0]];
        let result = Martinez.intersection([poly1], [poly2]);
        // result == null

Union also fails, returning the two original polygons.

Images

Invalid polygon in expected result of test 'disjoint union testing'

FYI, there's an invalid polygon in the test result here. The nesting goes 6 deep on that array of coordinates... the furthest a valid multipolygon can go is 4. The test passes, though with an invalid polygon as an expected result, I would expect the test to fail.

Looks like according to the comment there this test case is related to #47

Unnecessary exports for testing purposes

Would be useful to remove any unnecessary exports that are used for testing purpose in the main /index.js.

This allows the require() to only returns methods that are used in the current API.

Question: Is .boolean even worth adding to the API? This just adds complexity to 4 simple methods union, diff, xor & intersection. Running these functions programmatically can easily be done on the user's side, there's no strong reason to include in the core methods.

$ node
> require('./')
{ union: [Function],
  diff: [Function],
  xor: [Function],
  intersection: [Function] }

Current

/index.js

module.exports = require('./src/index');

/src/index.js

module.exports = boolean;

module.exports.union = function(subject, clipping) {
  return boolean(subject, clipping, UNION);
};

module.exports.diff = function(subject, clipping) {
  return boolean(subject, clipping, DIFFERENCE);
};

module.exports.xor = function(subject, clipping) {
  return boolean(subject, clipping, XOR);
};

module.exports.intersection = function(subject, clipping) {
  return boolean(subject, clipping, INTERSECTION);
};

/**
 * @enum {Number}
 */
module.exports.operations = {
  INTERSECTION: INTERSECTION,
  DIFFERENCE:   DIFFERENCE,
  UNION:        UNION,
  XOR:          XOR
};

// for testing
module.exports.fillQueue            = fillQueue;
module.exports.computeFields        = computeFields;
module.exports.subdivideSegments    = subdivideSegments;
module.exports.divideSegment        = divideSegment;
module.exports.possibleIntersection = possibleIntersection;

Proposed

/index.js

var martinez = require('./src/index');

module.exports = {
  union: martinez.union,
  diff: martinez.diff,
  xor: martinez.xor,
  intersection: martinez.intersection
};

/src/index.js

Unchanged

Crash: JavaScript heap out of memory

Using Node-8.11.1 (or 9.11.1, though the stack trace is from 8), martinez crashes the runtime with this pair of geometries: https://gist.github.com/mojodna/6e4ed77135ffdb629577574298307dd6

Standalone reproduction:

const martinez = require("martinez-polygon-clipping");

const a = [[[117.659922722,3.255275783000087],[117.64844811300017,3.246039130000042],[117.63795006600017,3.248724677000112],[117.63331139400017,3.268215236000103],[117.62484785200004,3.283270575000117],[117.57178795700011,3.313137111000017],[117.55640709700006,3.331854559000078],[117.54363040500002,3.354803778000147],[117.53467858200011,3.379380601000079],[117.53126061300006,3.403143622000158],[117.54151451900012,3.428452867000118],[117.56666100400011,3.438421942000105],[117.62525475400005,3.437689520000077],[117.64047285199999,3.436509507000054],[117.65699303500017,3.433539130000128],[117.67156009200019,3.426988023000064],[117.68165123800006,3.415513414000102],[117.68392988400015,3.399603583000086],[117.68197675900004,3.37750885600002],[117.67725670700011,3.356431382000082],[117.66537519600016,3.329291083000072],[117.66732832099999,3.271551825000117],[117.659922722,3.255275783000087]]];
const b = [[[117.6315403,3.2711246],[117.631605,3.2711063],[117.6315993,3.2710864],[117.6321104,3.2709415],[117.6320843,3.2708497],[117.6316732,3.2709663],[117.631666,3.2709411],[117.6315646,3.2709699],[117.6315529,3.2709289],[117.6314897,3.2709469],[117.6315403,3.2711246]]];

martinez.intersection(a, b);

Stack trace:

<--- Last few GCs --->

[98975:0x103001800]     6728 ms: Mark-sweep 578.0 (585.6) -> 578.0 (585.6) MB, 138.1 / 0.0 ms  allocation failure GC in old space requested
[98975:0x103001800]     6867 ms: Mark-sweep 578.0 (585.6) -> 577.9 (582.6) MB, 139.0 / 0.0 ms  last resort GC in old space requested
[98975:0x103001800]     7007 ms: Mark-sweep 577.9 (582.6) -> 577.9 (582.6) MB, 140.2 / 0.0 ms  last resort GC in old space requested


<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x34e1f74a57c1 <JSObject>
    1: connectEdges(aka connectEdges) [/Users/seth/src/americanredcross/osm-stats-workers/node_modules/martinez-polygon-clipping/dist/martinez.js:~1091] [pc=0x3b6e887061d1](this=0x34e11aa022d1 <undefined>,sortedEvents=0x34e1c508a031 <JSArray[39]>,operation=0)
    2: boolean(aka boolean) [/Users/seth/src/americanredcross/osm-stats-workers/node_modules/martinez-polygon-clipping/dist/martinez.js:13...

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
 1: node::Abort() [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 2: node::FatalException(v8::Isolate*, v8::Local<v8::Value>, v8::Local<v8::Message>) [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 3: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 4: v8::internal::Factory::NewUninitializedFixedArray(int) [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 5: v8::internal::(anonymous namespace)::ElementsAccessorBase<v8::internal::(anonymous namespace)::FastPackedObjectElementsAccessor, v8::internal::(anonymous namespace)::ElementsKindTraits<(v8::internal::ElementsKind)2> >::GrowCapacity(v8::internal::Handle<v8::internal::JSObject>, unsigned int) [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 6: v8::internal::Runtime_GrowArrayElements(int, v8::internal::Object**, v8::internal::Isolate*) [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 7: 0x3b6e885842fd
 8: 0x3b6e887061d1
 9: 0x3b6e8863d196
10: 0x3b6e8863d196
11: 0x3b6e8863d196
12: 0x3b6e8863d196
13: 0x3b6e8863d196
14: 0x3b6e8863d196
15: 0x3b6e8863d196
Abort trap: 6

Switch gh-pages branch to 'master'

Github pages can now be supported from any branch making the gh-pages branch pretty much redundant. It would be awesome to update this repo's gh-pages settings so it points at the master branch given that it contains the up to date code :)

Performance benchmarks

Are there any performance benchmarks vs other libs available?

JsClipper, the javascript port of Angus Johnsons Clipper (based on Vatti´s algorithm) come to mind for example

A case where intersection is incorrect

Hi,

I am not sure if it is due to the polygons are self-intersecting, or that the borders are overlapping, but I have a case where the intersection (as well as most of the other operations) give incorrect results.

The polygons used:
var p0_x = [ [ [0,0], [0,1], [1,0], [1,1], [0,0] ] ];
var p1_x = [ [ [0, 0.5], [0, 1.5], [1, 0.5], [1, 1.5], [0, 0.5] ] ];

Using the pen by AtiX (thx:) -

Gives an intersection -

and union -

`connectEdges` initial numbering causes exception

Labelling step here https://github.com/w8r/martinez/blob/master/src/index.js#L446 puts undefined in pos, when the otherEvent is ahead of the current one in resultEvents

Possible solutions are:

• split it into two loops
• use indexOf() (could be worse)

Problems with polygon clipping (intersection)

Hey there, I am not sure if this is a duplicate of the other issues or if it is related in any form. Also I tried to use another library for line clipping (mapbox/lineclip) where I also have this kind of issue. I am not sure how to solve it.

I am currently on a project where we want to visualize ship routes. For doing that we want to clip a world map containing all coastlines by a bounding box (depending on the envelope of the route). Sadly we get strange results by the algorithm. E.g. like this is the clipped output that occurs (just) sometimes:

So the out coming polygon already has that false points in the featureCollection
And when we want to draw it (iterating over all features of the featureCollection) we get this kind of result:

I tried your demo and it also seems that there are sometimes cases where the clipping (intersection method) does not produce the correct results. See this picture for example:

It seems there is some problem in the algorithm :(
I also posted this issue in the mapbox/lineclip repository: mapbox/lineclip#1
Maybe you're internally using the lineclip library?

For any sort of help you would help our routing project big times!

coords array: polygon with holes vs multipolygon

Hey there, I'm trying to replace turfs difference and intersect with your library in leaflet.pm (drawing plugin for leaflet) due to size.
To illustrate the problem I've included gifs of using your library.

When using difference, I'm having a bit trouble figuring out if the result is a MultiPolygon or a Polygon with a hole.
In your examples, you always expect it to be a Multipolygon but if you treat a hole that way - two layers are being drawn.

Using diff on a polygon when the result is a regular polygon

Using diff on a polygon, cutting it in half, and the result is a multipolygon:

Using diff on a polygon, cutting a hole in it. The resulting coords array looks exactly like a multipolygon, so both are getting drawn:

How would you recommend to find out if it's a hole or a multipolygon?

Minified file is empty

The minified file /dist/martinez.min.js is empty.

diff between polygon-with-hole and polygon results in multipolygon

This might be related to #44, and the library is just reporting it back using the wrong structure. But then again, it might be something completely different.

I have a polygon with a hole, coordinates are:

[
  [
    [6.399999999999977, -552], 
    [49.60000000000002, 19.200000000000045], 
    [748.8, 28.799999999999955], 
    [774.3999999999999, -574.4], 
    [6.399999999999977, -552]
  ], 
  [
    [227.2, -441.6], 
    [228.8, -283.19999999999993], 
    [430.40000000000003, -289.6], 
    [428.8, -448], 
    [227.2, -441.6]
  ]
]

I have another polygon, coordinates are:

[
  [
    [344,-211.2],
    [344,-123.2],
    [552,-121.6],
    [547.2,-216],
    [344,-211.2]
  ]
]

I ask martinez to diff them, expecting a polygon with 2 holes. Instead, I get my original polygon with hole, and my other polygon, in a multipolygon structure. Coordinates are:

[
  [
    [
      [6.399999999999977, -552],
      [774.3999999999999, -574.4],
      [748.8, 28.799999999999955],
      [49.60000000000002, 19.200000000000045],
      [6.399999999999977, -552]
    ],
    [
      [227.2, -441.6],
      [428.8, -448],
      [430.40000000000003, -289.6],
      [228.8, -283.19999999999993],
      [227.2, -441.6]
    ]
  ],
  [
    [
      [344, -211.2],
      [547.2, -216],
      [552, -121.6],
      [344, -123.2],
      [344, -211.2]
    ]
  ]
]

Overlapping edges still a problem

Look at this codepen:
https://codepen.io/anon/pen/LLdEbM

Polygon 1:

[
	[
		[
			-492.1913921306456,
			-246.09569606532278
		],
		[
			-492.1913921306456,
			246.09569606532278
		],
		[
			328.12759475376373,
			164.06379737688187
		],
		[
			328.12759475376373,
			82.03189868844093
		],
		[
			0,
			98.43827842612912
		],
		[
			0,
			-98.43827842612912
		],
		[
			328.12759475376373,
			-82.03189868844093
		],
		[
			328.12759475376373,
			-164.06379737688187
		],
		[
			-492.1913921306456,
			-246.09569606532278
		]
	]
]

Polygon 2:

[
	[
		[
			118.12593411135472,
			92.53198172056138
		],
		[
			328.12759475376373,
			82.03189868844093
		],
		[
			328.12759475376373,
			92.53198172056136
		],
		[
			118.12593411135472,
			92.53198172056138
		]
	]
]

Does not work under react16/webpack3

I know, I know... what does react16 have to do with this JS library?
We're moving from react 15 + webpack2 -> react 16 + webpack 3.
Martinez 0.3 works fine for us with react 15+webpack 2.
Martinez 0.3 fails under react15+webpack3.
The exception thrown is "TypeError: Tree is not a constructor" in subdivide_segments.js (line 11).
The stack trace is:

Uncaught TypeError: Tree is not a constructor
    at subdivide (subdivide_segments.js:11)
    at boolean (index.js:69)
    at Object../node_modules/@rms/geometry/node_modules/martinez-polygon-clipping/src/index.js.boolean.diff (index.js:84)
    ..... our code ....

Upon closer inspection, it appears that in this situation, the statement:
var Tree = require('avl');
doesn't actually give access to the Tree constructor. Look at the attached screenshot to see what the Tree variable is... looks like it's an ES6 module with default property, instead of the constructor itself.
Perhaps this is something I can work-around by configuring my environment?
Open to suggestions

Add benchmark against functional-rb-tree and bintrees

Importing with webpack fails!

Trying to use this awesome lib, but it always gives me:
Error: TypeError: Tree is not a constructor Which have its origin right here

I don't know if the problem is the build process from martinez or avl,
but the workaround I found is changing the line
var Tree = require('avl'); to
var Tree = require('avl').default;

But changing this line, also screw up the tests. So this is a build inconsistency

So I checked avl build process and I think there should be a minified UMD ES5 file.

Like I did for my PR of this lib
My minified file has only 14.3kb(Webpack), instead of 54kb(current size)

I can't make a pull request because the test are failing, and the problem probably begins in the avl lib.

My suggestion is: migrate martinez and avl build process from rollup/browserify to Webpack.

Would support LineString?

In some cases, I need to clip rivers or other line objects. Would martinez support it? Thanks for advice!

Difference fails on shared edge case

const polygon1 = {
    'type': 'Polygon',
    'coordinates': [
      [[ 10, 10 ], [ 80, 10 ], [ 80, 80 ], [ 10, 80 ], [ 10, 10 ]]
    ]
  };

  const polygon2 = {
    'type': 'Polygon',
    'coordinates': [
      [[ 20, 10 ], [ 30, 10 ], [ 30, 80 ], [ 20, 80 ], [ 20, 10 ]]
    ]
  };

https://codepen.io/w8r/pen/NMQZMq

outer ring added to wrong polygon in diff() result.

This is in a local build with latest master branch and then pr #58, #60, #64, #66, and #67 merged in. (Should be reproducible without #66 and #67 and maybe others--I'm just being complete.)

The key factors of the case seem to be:

• param #1 is a MultiPolygon.
• param #2 intersects param #1's first polygon. (either entirely or partially inside of the first polygon).

EDIT Feb-16: Widened the repro case above after some more testing.

The return from diff() calculates a new inner ring for the return shape that would be correct except that the outer ring is added to the first polygon of the return shape instead of the second.

var param1 = [
    [[[-89.489886, 40.482217],[-89.489714, 40.482022],[-89.489836, 40.482146],[-89.489886, 40.482217]]], // polygon #1
    [[[-89.491551, 40.483208],[-89.486778, 40.487262],[-89.487045, 40.485142],[-89.491551, 40.483208]]] // polygon #2
];
var param2 = [[[-89.48925, 40.484891],[-89.488996, 40.484309],[-89.48821, 40.484919],[-89.48925, 40.484891]]]; // A triangle that is contained by polygon #1 and has no intersection with polygon #2.
var d = diff(param1, param2);
console.log(JSON.stringify(d));

Console output from above with my added comments:

[
  [  (polygon #1)
    [[-89.491551,40.483208],[-89.487045,40.485142],[-89.486778,40.487262],[-89.491551,40.483208]]
  ],[ (polygon #2)
    [[-89.489886,40.482217],[-89.489836,40.482146],[-89.489714,40.482022],[-89.489886,40.482217]],

    (inner ring that is not contained by the outer ring. If this inner ring were under polygon #1 instead of the polygon #2, it would be correct.)
    [[-89.48925,40.484891],[-89.488996,40.484309],[-89.48821,40.484919],[-89.48925,40.484891]] 
  ]
]

The rendered output of the return shape. It's a little weird-looking because it's simplified points from a real-world set of shapes. But the big triangle is polygon #1. The tiny line at the bottom (actually a triangle) is the outer ring of polygon #2. And the dark triangle is the inner ring of the polygon #2 which you can see is not inside of the outer ring of polygon #2.

Implement unary union (dissolve)

Refactor to ES5 worth it?

Might be worth looking into simply refactoring this repo to pure ES5, that way you could eliminate the entire Rollup build process (nothing against Rollup), but this repo doesn't seem very large and I think there's more lines of code in the Rollup config then actual lines of source code.

A good example of simple ES5 Class based library is rbush (pretty sure you know this one already 😄).

Please work on the overlap problem.

Here is a very simple test case:
polygon 1: [[0,7], [7,0], [14,0], [21,7]] (trapezoid
poylgon 2: [[0,3.5], [0,0], [21,0], [21,3.5]] (box overlapping top half of trapezoid)

both polygons have an edge at y = 0 and overlap between x = 7 and x = 14.

result: [[3.5,3.5],[7,0],[14,0]]... plus bad vertices: [21,0], [14,0], and [21, 3.5] and missing good vertex [17.5, 3.5].

We wrote workarounds to remove the bad vertices ('any vertex that is outside one or the other original shapes') but it's hard to figure out how to insert the missing one.

This seems to be the only flaw in your otherwise awesomely performant algorithm... would be awesome if this bug did not exist!

Union Fails

Performing a union on the following two polygons causes an error:

Uncaught TypeError: Cannot read property 'left' of null
    at rotateLeft (martinez.js:123)
    at AVLTree.insert (martinez.js:572)
    at subdivide (martinez.js:1733)
    at boolean (martinez.js:1379)
    at Object.12.boolean.union (martinez.js:1389)

Polygons (I did not try to simplify these):

	let poly1 = [[0, 0],
		     [10.502137906098726, -8.91955472410577],
		     [19.362154173294872, -16.536565170635974],
		     [26.806688712234628, -23.184332654075142],
		     [33.06238143356417, -29.196158488907805],
		     [38.35587224792968, -34.9053439896185],
		     [42.91380106597733, -40.64519047069176],
		     [49.10713251970216, -50.62072053266144],
		     [46.96280779835334, -46.74899924661212],
		     [50.72953235570385, -53.55007163186412],
		     [54.440614648675066, -61.381708940932285],
		     [58.32269458791316, -70.57721248830114],
		     [62.602412084064326, -81.46988358845522],
		     [67.50640704777474, -94.39302355587905],
		     [68.81850151153644, -97.30806695169885],
		     [69.8621573393369, -97.95163015963242],
		     [71.06094548688412, -96.8158900656893],
		     [76.97887880292775, -92.44160559185252],
		     [77.08733590764791, -82.61594306225551],
		     [76.04410744893605, -80.24754616339085],
		     [77.94689401460623, -84.56736102628204],
		     [86.1143714390989, -73.17583405575341],
		     [92.5064384837837, -63.06061283731647],
		     [97.5579645467036, -54.03110246393672],
		     [101.70381902590161, -45.89670802857968],
		     [105.37887131942071, -38.466834624210875],
		     [111.17983390680583, -28.31159335439475],
		     [109.0179908253039, -31.55088734379581],
		     [116.19929795079966, -20.790455559126197],
		     [116.05604694159416, -24.9582712803],
		     [120.92790906633451, -18.49839152668898],
		     [127.06844659756788, -11.980653175928243],
		     [134.91252893333734, -5.214461320983322],
		     [144.89502547168587, 0],
		     [0, 0]];

	let poly2 = [[-42.061875001865225, 0],
		     [-38.333456448806956, -4.191434705875763],
		     [-35.788781183126574, -3.2898181160071496],
		     [-33.479009769666234, -11.900923266495782],
		     [-30.45530277326811, -18.141137813496414],
		     [-28.381278877922217, -16.789914833141882],
		     [-24.233743423095476, -10.47911691415063],
		     [-20.015414375728398, -17.01009233689141],
		     [-17.729009702761488, -18.56589936873845],
		     [-11.159466795267058, -11.53852312789438],
		     [-6.31966948099911, -5.434229624518701],
		     [-1.03024624278126, -3.200354520901266],
		     [6.888174436562863, 0],
		     [-42.061875001865225, 0]];

However, intersection works.

cannot be blank

cannot be blank

package.json broken

In 8b57531 you changed the main script in package.json from 'index.js' to 'dist/martinez.js'. Is there a specific reason why? Because my app requires your module and now I can't include it via browserify (it searches for 'require' and wants to include all files - it can't because they are already inclued, which browserify doesn't know).

If I change the 'main' in 'package.json' back to 'index.js', everything works fine.

Handling of unclosed coordinates.

Hello!

If I call diff() and one of the passed polygons is missing or has an incorrect ending coordinate, the function will get caught in some kind of loop and eventually Javascript heap memory will be exhausted.

const a = [[[0,0],[10,0],[10,10],[0,10],[0,0]]];
const b = [[[10,0],[10,10],[20,10],[20,0],[0,0]]]; // Bad ending coordinate.
difference(a,b);

Of course, this is my error in calling, since the b coordinates are invalid. But I suggest that this is a good case to catch with a simple check so that the function exits quickly without tying up the processor.

I'm quite happy with the library so far. Thanks so much!

Replace RB-tree with AVL

Reason - simpler code, less dependencies, performance (the one that is used now, though being absolutely brilliant, is not really fast)

• w8r/avl what's missing now is to make sure the tree is properly iterable → .next() .prev()

Splitting polygon with diff results in misattributed hole

Test case below, but essentially clipping a polygon when a hole is on top can misattribute the hole to the bottom polygon in the result of diff. I'm happy to fix this on my own with some guidance.

var subject = [
    [
        // original polygon
        [600,250],
        [1200,250],
        [1200,1300],
        [600,1300],
        [600,250]
    ], [
        // hole (above clipping polygon)
        [800,350],
        [1000,350],
        [1000,600],
        [800,600],
        [800,350]
    ]
];

var clip = [
    [
        // clip through polygon, splitting into 2
        [500,700],
        [1400,700],
        [1400,800],
        [500,800],
        [500,700]
    ]
];

var expected = [
    [
        [
            // top polygon
            [600,250],
            [1200,250],
            [1200,700],
            [600,700],
            [600,250]
        ],
        [
            // original hole
            [800,350],
            [1000,350],
            [1000,600],
            [800,600],
            [800,350]
        ]
    ],
    [
        [
            // bottom polygon
            [600,800],
            [1200,800],
            [1200,1300],
            [600,1300],
            [600,800]
        ]
    ]
];

var realResult = [
    [
        [
            [600,250],
            [1200,250],
            [1200,700],
            [600,700],
            [600,250]
        ]
    ],
    [
        [
            [600,800],
            [1200,800],
            [1200,1300],
            [600,1300],
            [600,800]
        ],
        [
            [800,350],
            [1000,350],
            [1000,600],
            [800,600],
            [800,350]
        ]
    ]
]

Proposal: loop guards.

I've now found 3 separate causes for infinite loops--2 of these I've already reported. The third, I'm narrowing down the repro still.

Of course, we can work through fixing the bugs that cause the infinite loops. And we should. But I propose that we add some simple guards to the loops that check for an excessive loop count and exit out before the JS stack is depleted. My reasoning is as follows:

• Troubleshooting bugs is easier because the function can fail BEFORE the JS execution environment crashes, and allow us to log the error and context, e.g. the params that were passed to the failing call.
• The APIs can be called within an app even if they aren't completely free of bugs. I am okay with a function failing 1 out of every 100 times I call it, if the app can recover. But currently, when run inside of a web app, a user would see our entire web page replaced with an error message as a result of the JS execution environment crashing. In a production app, this is the kind of thing that gets people woke up at 3am to come in and fix.

(This image below is currently what the end user of our web app would see after one failed call to a martinez API)

It would be a pretty reasonable response to say "we're in beta now. We're going to fix these bugs, and then there would be no need for the inelegant loop guard thing you're talking about." The thing is... W8r/Martinez is doing better RIGHT NOW than the TurfJS (JSTS-inherited) boolean functions my project is using in production. When I say "better", I mean that the cases I had that were generating weird TopologyExceptions down in the bowels of JSTS are working fine with W8R/Martinez. There is just one dealbreaking caveat... it can frigging crash the browser!

So I will probably add the loop guards in my local fork of W8R/Martinez in an attempt to get it production-usable, unless somebody gives a great reason not to (e.g. "I already did that!"). And y'all can let me know if you're interested in a PR. I'm happy to throw it up there and have the specifics of it be disagreed with--just wanted to check for interest in receiving such a PR before sending it at you.