These coordinates:
https://gist.github.com/jliebrand/d27791efbe8f3ac05c802220c3bc6409

cause an eternal loop when you try to union them.

  _prevNotCoincident () {
    // iterating backwards from next to prev
    let next = this
    let prev = this.prev
    while (prev && next.coincidents === prev.coincidents) {
      next = prev
      prev = prev.prev
    }
    return prev
  }

That while loop just spins forever

Version 0.7

This error seems to happen randomly when doing quick clippings with difference.

TypeError: Cannot read property 'left' of null
at Tree.prev (webpack://polygon-clipping/./node_modules/splaytree/index.js?:537:11)
at SweepLine.process (webpack://polygon-clipping/./src/sweep-line.js?:52:32)
at doIt (webpack://polygon-clipping/./src/index.js?:73:31)
at Object.difference (webpack://polygon-clipping/./main.js?:47:28)

Mike, I was surprised that squaring EPSILON and (a-b) is much faster than calling Math.abs(). So I changed my floating point comparison code in my project to match how you are doing it.

It does look like you can get an optimization by reusing your EPSILON_SQ value on line 19 instead of squaring again here.

Finally, I don't understand this block...

// check if they're both 0
    if (-Number.EPSILON < a && a < Number.EPSILON) {
      if (-Number.EPSILON < b && b < Number.EPSILON) {
        continue
      }
    }

Did you find it was a necessary special case? In my benchmarks, the comparison for passing a=0, b=0 was actually slower with this code in place. Of course, all my timing is just in one browser/environment. So maybe that is a fluke.

Performing a union on these five shapes results in the following error being thrown:

Error: Unable to pop() SweepEvent #12051 [-71.0390933353125, 41.484475] from queue. Please file a bug report.
    at Operation.run (webpack://polygon-clipping/./src/operation.js?:87:17)
    at Object.union (webpack://polygon-clipping/./src/index.js?:18:30)

Not a big deal, but when using this with webpack/babel, the following doesn't work:

import polygonClipping from 'polygon-clipping';

You are forced to used the require syntax in order for the module to be found.

Right now, each segment has the following structure:

class Segment {
  coincidents = [this, ...]  // list of segments that *exactly* overlap this segment, including itself
  ringIn = <ring>            // the input ring this segment came from
  flowL2R = <boolean>        // the direction, clockwise or counter-clockwise, this segment faced in its input ring
  ...
}

This is somewhat wasteful because nearly all input segments have only one coincident - themselves. So Segment.coincidents is nearly always just a one-element array. So one possible performance improvement would be to leave Segment.coincidents undefined until at least one coincident segment is identified, and at that point initialize it to an array of two segments: [this, otherSeg].

Even better would be:

First, by addressing #30, hopefully the need to carry around the boolean flowL2R goes away.

Then the following structure would be possible:

class Segment {
    ringsIn = [<ring>, ...] // list of input rings this segment represents
    ...
}

This drops the coincidents array altogether. Essentially when two segments realize they're coincident, instead of just marking themselves as such, one would 'die' and give its input ringIn to the surviving segment. The dieing segment could either be marked 'dead' with a tombstone or it could be proactively removed from the datastructures (the sorted tree of segments and the sweep event priority queue).

And from here, since 99% of input segments only represent one ring, we could employe the the following more complicated, but likely more performant structure:

class Segment {
  ringIn = <ring>                    // only defined when the segment represents just one ring
  ringsIn = [<ring1>, <ring2>, ... ] // only defined when the segment represents two or more rings
  ...
}

Performing a union() on these shapes results in the following error being thrown:

Error: Unable to find segment #203 [-91.4137213, 29.5316244] -> [-91.41360941065206, 29.53135] in SweepLine tree. Please submit a bug report.
    at SweepLine.process (webpack://polygon-clipping/./src/sweep-line.js?:58:24)
    at Operation.run (webpack://polygon-clipping/./src/operation.js?:89:35)
    at Object.union (webpack://polygon-clipping/./src/index.js?:18:30)
    at Object.doIt (/Users/mfogel/attm/geojson-clipping/src/lib.js:111:46)

Latest fixes have definitely improved matters, but here's another set of coordinates that cause "Cannot read property 'left' of null":

https://gist.github.com/jliebrand/165f97f0812fe495ee013e00b715110d

Remove clean() method from the module.exports b/c:

• it functionally duplicates the other exports. Everything you can do with clean() you can do with the other exports.
• it complicates the API docs

In it's place, let's allow the other methods to be called with only one argument, which should do the same thing as what clean() did.

I've come across cases where the queue behaves badly, such that the algorithm ends up in an eternal loop. Notice this screenshot:

Notice in the console, how the queue size is 7,154 elements, but even after calling pop(), it is still the same length... Causing the while loop to spin forever...

According to some of the discussion in martinez, it might be a good idea to swap out AVL for Spay tree.

Hi @mfogel

When updating this module in turf in line with #50 I've now got some tests which fail which previously passed.

I'm basically just trying to union a massive feature collection (here it is).

Nothing fancy, just

const args = fc.features.map(f => f.geometry.coordinates)
pc.union(...args))

Hunting back through the repo history I can see it worked with v7, however it breaks in v8 throwing a splaytree error. And in v9.2 it spins infinitely...

Will see if I can narrow down the test case at all

Cheers

There's a bug in the registering of coincident segments.

If a given segment is coincident (ie has the exact same two endpoints) with segments from several other input polygons, instead of registering all those segments coincident, the registry can be split, resulting in not all segments being aware of all their coincident segments.

Failing test case and fix coming.

see gist for polygons in question:
https://gist.github.com/jomel/45d2c23bc7d3b83143af18fb8ce1312a

when trying to run intersection()
I get :

Error: Unable to complete output ring starting at [0.523657, 51.281218]. Last matching segment found ends at  [0.5239850000000017, 51.281651].
    at Function.factory (webpack://polygon-clipping/./src/geom-out.js?:52:21)
    at doIt (webpack://polygon-clipping/./src/index.js?:81:34)
    at intersection (webpack://polygon-clipping/./main.js?:30:28)
...

I don't see anything odd about my geometries...

The following coordinates cause an error to be thrown (unable to complete output ring)

https://gist.github.com/jliebrand/d59d08d3a571ccec7d7f55db47aecf0e

haven't had time to simplify this

There's a nice starter page up at http://polygon-clipping.js.org/

Let's expand that to include:

• docs
• demo
• real-time comparison with other similar packages.

A user should be able to click 'go' and the browser will run each competing package through all the tests. Both speed and accuracy will be reported.

This is one of the failing cases pulled from #22

Here's a minimized failing test case:

const polygonClipping = require('./dist/polygon-clipping.js')
const p1 = [ [  [270, 30], [275.340617860256, 33.9640010221343], [279, 30], [279, 39], [270, 30] ] ]
const p2 = [ [ [275, 34], [273.262781887207, 32.5300428496046], [278.222781887207, 35.9530428496046], [275, 34] ] ]

polygonClipping.difference(p1, p2)
TypeError: Cannot read property 'left' of null
    at Tree.prev (webpack://polygon-clipping/./node_modules/splaytree/index.js?:537:11)
    at SweepLine.process (webpack://polygon-clipping/./src/sweep-line.js?:51:32)
    at doIt (webpack://polygon-clipping/./src/index.js?:74:31)
    at Object.difference (webpack://polygon-clipping/./main.js?:47:28)

What's going on here is that one of the segments is nearly vertical downward-facing. Because of rounding errors, that segment is being split into two segments: one vertical and one-nearly vertical. The vertical one is being created with left and right sweep events swapped from how they should be.

Probably easier to understand with diagrams. Here's the intersection that causes the problem, as it looks in the failing test case. Left sweep events are on the tails of the arrows, right sweep events are on the heads.

The intersection between the two segments is detected by the algorithm, splitting both segments resulting in this situation. Rounding errors have caused one of the segments to go fully vertical.

However, vertical segments by convention always have their left event on the bottom and right event on top, so the later stages of the algorithm are expecting this situation:

Note that ordering of sweep events in the sweep line priority queue depends on, in part, the left-ness and right-ness of the sweep events. So changing whether a sweep event is right or left can cause problems for that queue.

Currently there exists: difference(subjectGeom, clippingGeom)

This can be expanded to support multiple clippings:

difference(subjectGeom, clipGeom1, clipGeom2, ...)

Functionally this will be the same as difference(subjectGeom, union(clipGeom1, clipGeom2, ...)) just all done in one pass. It'll be more efficient, and will give difference the same function signature as the other operations.

If the intersection of self-overlapping multipolygons is computed, some segments that are internal to the multipolygon can be included in the result.

This is probably a far fetched request, but here i go..

I would like to port the code to Swift but i found it a bit weird that the classes Ring, Poly and Multipoly are declared in both geom-in and geom-out, would it be possible to combine them together somehow, rename them or perhaps remove them alltogether ( can't find similar classes in the martinez repo )?

Hi @mfogel

There seems to be a bit of a bug with tracking holes at the moment,

const f1 = {
    type: 'Feature',
    properties: {},
    geometry: {
        type: 'MultiPolygon',
        coordinates: [
            [
                [
                    [-74.007991, 40.712882],
                    [-74.002844, 40.710215],
                    [-73.995466, 40.714509],
                    [-74.002983, 40.716637],
                    [-74.003519, 40.71568],
                    [-74.005797, 40.715789],
                    [-74.007991, 40.712882]
                ]
            ],
            [
                [
                    [-74.005369, 40.716355],
                    [-74.003402, 40.716756],
                    [-74.004774, 40.717144],
                    [-74.005369, 40.716355],
                ],
                [
                    [-74.003605, 40.713988],
                    [-74.002854, 40.714769],
                    [-74.001266, 40.714167],
                    [-74.001609, 40.713289],
                    [-74.003605, 40.713988]
                ]
            ]
        ]
    }
}

const f2 = {
    type: 'Feature',
    properties: {},
    geometry: {
        type: 'Polygon',
        coordinates: [
            [
                [-74.005558, 40.713403],
                [-74.005558, 40.712573],
                [-74.003949, 40.712573],
                [-74.003949, 40.713517],
                [-74.005558, 40.713403]
            ]
        ]
    }
}

difference(f1.geometry.coordinates, f2.geometry.coordinates)

The output removes the hole from the the first feature

    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "type": "MultiPolygon",
        "coordinates": [[[[-74.007991,40.712882],[-74.002844,40.710215],[-73.995466,40.714509],[-74.002983,40.716637],[-74.003519,40.71568],[-74.005797,40.715789],[-74.007991,40.712882]],[[-74.005558,40.712573],[-74.005558,40.713403],[-74.003949,40.713517],[-74.003949,40.712573],[-74.005558,40.712573]]],[[[-74.005369,40.716355],[-74.003402,40.716756],[-74.004774,40.717144],[-74.005369,40.716355]]]]
      }
    }

I seem to recall tackling something similar with the original martinez repo although the way you monitor holes is a bit different.

I'll try and do some digging this week and report back.
Cheers
Rowan

Self-crossing rings are ambiguous because they could be interpreted using either the non-zero rule or the even-odd rule. As such, the algorithm throws an exception, by design, when given a self-crossing ring. This behavior is covered by the test suite.

Right now, checking for the self-crossing rings is done by a separate loop over the output segments before the algorithm attempts to glue them together into output shapes.

It may be possible to eliminate this loop by doing this check right when a segment is split by another segment, and at that point if the two segments are from the same ring, and they do cross (not just touch) then throw the error there.

Performing a union on these two shapes results in a series of recursive calls that goes too deep (infinitely deep? TBD)

First few lines of the error backtrace

(node:42015) UnhandledPromiseRejectionWarning: RangeError: Maximum call stack size exceeded
    at Segment.ringsAfter (webpack://polygon-clipping/./src/segment.js?:368:31)
    at Segment._ringsBefore (webpack://polygon-clipping/./src/segment.js?:364:50)
    at Segment.ringsBefore (webpack://polygon-clipping/./src/segment.js?:357:77)
    at Segment._ringsAfter (webpack://polygon-clipping/./src/segment.js?:376:24)
    at Segment.ringsAfter (webpack://polygon-clipping/./src/segment.js?:370:77)
    at Segment._ringsBefore (webpack://polygon-clipping/./src/segment.js?:364:50)
    at Segment.ringsBefore (webpack://polygon-clipping/./src/segment.js?:357:77)
    at Segment._ringsAfter (webpack://polygon-clipping/./src/segment.js?:376:24)
    at Segment.ringsAfter (webpack://polygon-clipping/./src/segment.js?:370:77)
    ...

Hi, when clipping multiple times I get this error. It seems to be triggered when I clip in a very similar or exactly the same spot, but this is mostly speculation.

Error: SweepEvent comparison failed at [0,600]... equal but not identical?
at Heap.compareBefore [as _isBefore] (./node_modules/polygon-clipping/src/sweep-event.js:28:11)
at Heap_remove (./node_modules/qheap/lib/qheap.js:91:18)
at doIt (./node_modules/polygon-clipping/src/index.js:38:47)
at Object.difference (./node_modules/polygon-clipping/main.js:17:10)

Version: 0.6

Just want to state, great work, my current use case is to create destructable ground with matterjs using this library to make the holes.

For certain input values, there appears to be an infinite loop causing a max stack size to be reached.

I'll add a test case and a PR to show the issue (raising this issue first so that i can refer to it in code)

The following input polygon results in a crash with a SweepEvent comparison failed at [-130.73939947890625,54.91877729166476]... equal but not identical? error being thrown:

[[
   [-130.73862770644791, 54.92404227517194],
   [-130.73939947890625, 54.91877729166476],
   [-130.73939947890625, 54.918777291664775],
   [-130.73862770644791, 54.92404227517194]
]]

What's going on is that:

• the points are each being identified as different by the floating point lib (even the middle two points: [-130.73939947890625, 54.91877729166476] and [-130.73939947890625, 54.918777291664775])
• but these line segments are being identified as parallel, which causes the sweep line algorithm to barf as it tries to sort them (hence the sweep event comparison error)
  • [ -130.73939947890625, 54.91877729166476 ] -> [ -130.73939947890625, 54.918777291664775 ]
  • [ -130.73939947890625, 54.91877729166476 ] -> [ -130.73862770644791, 54.92404227517194 ]

Right now, when input points are consumed a check is being done to (silently!) drop repeated points. It should be safe to also (silently!) drop colinear points.

If a ring is shortened to two or fewer points because of the above checks, it should be dropped altogether.

This is a performance optimization primarily intended to reduce memory usage, but as mentioned in #5 a side benefit of this work is I expect it will speed up compute time in most cases.

Before running the algorithm over the input polygons:

• compute a bounding box for each input polygon
• compare the bounding boxes of each input to determine what areas the algorithm needs to run over:
  • intersection: the area overlapped by all bounding boxes
  • union & xor: area overlapped by any two or more bounding boxes
  • difference: area overlapped by bounding boxes of the subject and at least one clipping
• compute a bounding box around the above computed area the algorithm should run over. Call this the 'operational bounding box'
• compare each input polygon with the operational bounding box to form two multipolygons: that which is inside the operational bounding box and that which is outside
  • don't use the algorithm to do this - this can be done by a simple O(n) traversal of each input
• run the algorithm over the portions of the input polygons inside the operational bounding box
• depending on the operation, the result of running the algorithm in the above step may need to be joined to the portion of the input polygons that was not inside the operational bounding box
  • union & xor: join
  • intersection: don't join - drop
  • difference: join for subject, drop for clippings

Gday @mfogel

Nice work on this so far. Is there anything in particular you'd like help with to mature this repo?

• I might submit a benchmark test tonight to compare this against @w8r 's version of martinez? I think this is a good starting point to.
• Are you happy with the test suite?
• If the above are looking good would you like me to put together a demo page perhaps?

Cheers
Rowan

Here's the relevant data structure as it exists now:

class SweepEvent {
  // a pointObject is a simple object of form {'x': <number>, 'y': <number>}
  // it is shared with normally one, but possibly more, other SweepEvents
  point: pointObject,

  // other stuff...
}

Here's the structure I think it would be worth testing:

class SweepEvent {
  // flattened point object. No more sharing of these coordinates between SweepEvents with
  // the same points - the raw numbers would just be repeated.
  x: <number>,
  y: <number>,

  // other stuff...
}

In addition, those point objects {'x': <number>, 'y': <number>} are passed to many helper methods/functions. Those could all be changed to just accept two separate arguments: x: <number> and y: <number>.

This could slightly increase memory usage (or decrease it? unsure how much overhead the small point objects introduce in JS) but would theoretically decrease the number of steps of dereferencing pointers to get at the values.

Add support for self-intersecting rings that touch each themselves, but don't cross.

Rings of this form are guaranteed not to be ambiguous with respect to the even-odd rule and the non-zero rule.

Examples of rings that just touch each other, but don't cross:

• Bow tie that intersects itself but doesn't cross
• ring-within-ring that intersects itself but doesn't cross

Examples of self-intersecting rings that cross themselves:

• Bow tie that crosses itself
• ring-within-ring that crosses itself
• ring-within-ring that loops twice

The performing a union() on the following polygons results in the library crashing with a "Unable to pop() SweepEvent ... from queue" error.

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "properties": null,
      "geometry": {
        "type": "Polygon",
        "coordinates": [
          [
            [-85.635, 34.546],
            [-85.64162299941661, 34.546027776790396],
            [-85.64157326850268, 34.53498609425157],
            [-85.635, 34.546]
          ]
        ]
      }
    },
    {
      "type": "Feature",
      "properties": null,
      "geometry": {
        "type": "Polygon",
        "coordinates": [
          [
            [-85.644, 34.55],
            [-85.64162299941658, 34.54602777678346],
            [-85.64157326850268, 34.53498609425157],
            [-85.643, 34.54],
            [-85.635, 34.546],
            [-85.644, 34.55]
          ]
        ]
      }
    }
  ]
}

One of those polygons is a bit ugly in that it has a self-crossing ring, but polygon-clipping should be able to handle that just fine.

The es module should be set to package.module, the UMD to package.main

Once this is done, the source code can be adjusted to use es6 imports/exports.

The following geometry causes an exception to be thrown: Error: Unable to complete output ring starting at [-118.472282, 34.027219]. Last matching segment found ends at [-118.467722, 34.025468]. Pulled over from #48.

polygonClipping.union(
  [
    [
      [-118.46571, 34.025348],
      [-118.465871, 34.025308],
      [-118.465936, 34.025348],
      [-118.467899, 34.025348],
      [-118.468194, 34.025197],
      [-118.468983, 34.025174],
      [-118.469245, 34.025348],
      [-118.46571, 34.025348]
    ]
  ],
  [
    [
      [-118.464605, 34.02561],
      [-118.465871, 34.025308],
      [-118.466413, 34.02565],
      [-118.467722, 34.025468],
      [-118.468194, 34.025197],
      [-118.468983, 34.025174],
      [-118.469433, 34.025494],
      [-118.470297, 34.025512],
      [-118.472282, 34.027219],
      [-118.464605, 34.02561]
    ]
  ]
);

Hi @mfogel

So I've encountered a new issue when union-ing a single polygon.

The polygon crosses over itself and should result in a single hole.

However it is resulting in two holes, the second of which is not required.

Grrr don't you hate edge cases :)

As the output rings are compiled from a list of SweepEvents in src/geom-out.js, parallel segments are simplified in two ways:

• intermediate points on a straight line are removed (180 degree angle)
• straight out-and-backs are removed (0 degree angle)

However, if a polygon is extremely thin, this processing can remove every point in the ring. In this case the compiled output ring comes out as just [undefined].

Note that because of floating point rounding, it's possible for earlier steps of the algorithm to consider a ring not to be infinitely thin, but then when it comes to calculating the angles here at the end, the angles are all within Number.EPSILON of 0 or 180 - so the ring appears here as infinitely thin.

The fix: drop the rings that are this thin from the output shapes.

Running a difference on the following shapes results in the following error:

TypeError: Cannot read property 'slice' of null
    at Segment.split (webpack://polygon-clipping/./src/segment.js?:303:67)
    at SweepLine._possibleSplit (webpack://polygon-clipping/./src/sweep-line.js?:164:29)
    at SweepLine.process (webpack://polygon-clipping/./src/sweep-line.js?:73:43)
    at Operation.run (webpack://polygon-clipping/./src/operation.js?:89:35)
    at Object.difference (webpack://polygon-clipping/./src/index.js?:42:30)

Terminology: the 'clipping' is subtracted from the 'subject'

Subject:

{
  "type": "Feature",
  "properties": null,
  "geometry": {
    "type": "Polygon",
    "coordinates": [
      [
        [-68.5921849, -52.100483],
        [-67.4995446, -46.473987],
        [-67.5005764, -46.4742709],
        [-68.5921849, -52.100483]
      ]
    ]
  }
}

Clipping:

{
  "type": "Feature",
  "properties": null,
  "geometry": {
    "type": "MultiPolygon",
    "coordinates": [
      [
        [
          [-67.499904, -46.473721],
          [-67.5001, -46.473991531791334],
          [-67.5001, -46.474139818433805],
          [-67.499904, -46.473721]
        ]
      ],
      [
        [
          [-67.4999, -46.473936585925195],
          [-67.5005764, -46.4742709],
          [-67.4999, -46.47408478838923],
          [-67.4999, -46.473936585925195]
        ]
      ]
    ]
  }
}

First, thank you for you lib !

I generated a polygon using bbox clip on OSM Land polygon (http://openstreetmapdata.com/data/land-polygons). I try to generate a polygonClipping.union using the MultiPolygon generated. Error throws

Error: SweepEvent comparison failed at [-15.188987939241656, 11]... equal but not identical?

I simplified the polygons to reproduce the bug:

// The problem comes from this polygon
const p1 = [[[-15.17583125361432, 11], [-15.182247200000006, 10.996678799999998], [-15.186977083599459, 11], [-15.188987939241656, 11], [-15.210785900000019, 10.987789800000002], [-15.25473119999998, 10.999922499999997], [-15.25484460019419, 11], [-15.17583125361432, 11]]];

// p2 : any polygon intersecting p1 or not
const p2 = [[[-15.017809399999976, 10.944376500000018], [-15.012765219284972, 10.95029830701516], [-15.013805400000024, 10.942978100000005], [-15.017809399999976, 10.944376500000018]]];

polygonClipping.union(p1,p2);

The problem comes from this strange polygon (2 areas linked by a line !!!)

We're still seeing errors in production with maximum call stack size reached.

Here's an example set of coords that cause it:
https://gist.github.com/jliebrand/5b00599bee190e28d26ead782c35e988

The README claims output rings 'will not be self-intersecting', however, as this test case demonstrates, sometimes they are.

Either the claims in the README need to be relaxed or the compiling of the output rings needs to be changed so self-intersecting rings like these can't be generated.

https://gist.github.com/rowanwins/91bd29363de84255835645ebaa75a546

Similar input to #54 although I've narrowed it down to 4 features this time.

No error is ever thrown.

Hi, i've been looking into the Martinez algorithm lately and i was wondering why the 2009 paper / implementation was choosen as there is a newer 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?

Update: I see the original repo links to the new paper, but the link text describes the old paper. A little confusing, but I also noticed you've included the old paper, so i guess your work is based on this?

Update 2: Author from original source confirmed it's based on the 2013 paper, so i guess it applies for this repo as well.

Using this set of polygons:

const set = [
	[
		[
			[541.0184069121032,-143.03237832156836],
			[538.8976288020026,-123.35535843900269],
			[537.8321066666686,-122.80116457495023],
			[536.8855437278494,-123.35069884911623],
			[538.8870716306947,-141.92129053535714],
			[540.0894577777653,-143.74533713285928]
		]
	],
	[
		[
			[540.7750579535648,-143.21914611949745],
			[540.0894577777653,-143.74533713285928],
			[539.662835668487,-144.64976710575652],
			[539.7288124662978,-144.67804017205043],
			[540.3113546885238,-144.90328991644918],
			[540.6719999999914,-143.97058687725803]
		]
	],
	[
		[
			[557.6320465703087,-141.3264757967004],
			[540.8116376490731,-142.95242750964428],
			[540.6719999999914,-143.97058687725803],
			[541.2045466710015,-144.9237692724459],
			[557.0433079860503,-143.3927089271412],
			[558.1482666666561,-142.28123640691047]
		]
	],
	[
		[
			[532.7840286412132,-156.0428207910487],
			[541.2045466710015,-144.9237692724459],
			[540.6719999999914,-143.97058687725803],
			[539.8748041328679,-143.3668661227355],
			[531.3858333791956,-154.5763074915546],
			[531.7154133333242,-155.79750159024843]
		]
	],
	[
		[
			[538.8870716306947,-141.92129053535714],
			[513.8619652247359,-127.83939169834923],
			[511.28554246236985,-128.25021939873648],
			[511.7826658464412,-128.96424912185236],
			[539.5990569575308,-144.61683414118076],
			[539.662835668487,-144.64976710575652],
			[540.0894577777653,-143.74533713285928]
		]
	]
];

calling:

polygonClipping.union(set[0], set[1], set[2], set[3], set[4]);

fails with:

Error: Unable to complete output ring starting at [539.8561832464202, -143.39145446694468].
Last matching segment found ends at  [539.8561832464202, -143.39145446694462].

The polygons look like:

Hey @mfogel

Been looking at the performance of this lib and one of the things I noticed is that is spends a lot of time in the startup before it even gets to the algorithm.

I was wondering if we could reduce the number of loops in the startup., eg currently it loops through all the points twice, once for pointsAsObjects and then again for new geomIn.MultiPoly. I'm thinking we could combine the loops here relatively simply, but at the same time we'd get a fairly good performance gain.

What do you think?

Reproduce case: https://repl.it/repls/TangibleHoneydewFiber

As far as I can make out, the input geometry should be valid, but it clearly barfs on some aspect of it... Still trying find which of the polygons is causing the problem...

I've been seeing some crashing bugs caused by specific inputs to union with version 0.8.0.

For example:

var coords1 = [
  [
    [
      [-118.49128246307373, 34.019483292435396],
      [-118.49096059799194, 34.019203176094535],
      [-118.49094450473785, 34.01912758898703],
      [-118.48823547363281, 34.016802140968366],
      [-118.487548828125, 34.017371278141994],
      [-118.487548828125, 34.01735794217727],
      [-118.48639011383057, 34.01833169712249],
      [-118.48449110984802, 34.019892349558305],
      [-118.487548828125, 34.022524496063156],
      [-118.487548828125, 34.02252330890177],
      [-118.48758637905121, 34.02255561892879],
      [-118.48968923091888, 34.02087941406322],
      [-118.490429520607, 34.020261388532035],
      [-118.49038660526276, 34.02022581858034],
      [-118.49128246307373, 34.019483292435396]
    ]
  ]
];

var coords2 = [
  [
    [-118.48639011383057, 34.01833169712249],
    [-118.48823547363281, 34.016802140968366],
    [-118.49094450473785, 34.01912758898703],
    [-118.49096059799194, 34.019203176094535],
    [-118.49128246307373, 34.019483292435396],
    [-118.49038660526276, 34.02022581858034],
    [-118.490429520607, 34.020261388532035],
    [-118.48968923091888, 34.02087941406322],
    [-118.48758637905121, 34.02255561892879],
    [-118.48449110984802, 34.019892349558305],
    [-118.48639011383057, 34.01833169712249]
  ]
];

var results = polygonClipping.union(coords1, coords2);

This seems to cause an infinite loop.

I thought the issue could be related to overly-precise coordinates, but I also see issues sometimes with rounded coordinates. For example, this input causes a SweepEvent comparison failed error:

var coords = [
  [
    [-118.46571, 34.025348],
    [-118.465871, 34.025308],
    [-118.465936, 34.025348],
    [-118.467899, 34.025348],
    [-118.468194, 34.025197],
    [-118.468983, 34.025174],
    [-118.469245, 34.025348],
    [-118.46571, 34.025348]
  ]
];

polygonClipping.union(
  JSON.parse(JSON.stringify(coords)),
  JSON.parse(JSON.stringify(coords))
); // or `polygonClipping.union(coords, coords)`

Hello,

I found another eternal loop here.

polygon-clipping: v0.9.2

const points1 = [
  [
    [945.767995, 1863.133381], 
    [946.1825, 1861.049523], 
    [947.362911, 1859.282913], 
    [949.129521, 1858.102502], 
    [951.213379, 1857.687997], 
    [953.297237, 1858.102502], 
    [955.063847, 1859.282913], 
    [955.1629889876718, 1859.4312896037573], 
    [955.311363, 1859.53043], 
    [955.4105033962428, 1859.678804012328], 
    [955.55888, 1859.777946], 
    [955.7075946082703, 1860.0005131517094], 
    [955.930159, 1860.149226], 
    [955.9797279146642, 1860.2234110853356], 
    [956.053913, 1860.27298], 
    [957.234324, 1862.039589], 
    [957.648829, 1864.123448], 
    [957.234324, 1866.207306], 
    [956.053913, 1867.973915], 
    [954.287304, 1869.154326], 
    [952.203446, 1869.568831], 
    [950.119587, 1869.154326], 
    [948.352978, 1867.973915], 
    [948.3034098580295, 1867.8997310710815], 
    [948.229223, 1867.850161], 
    [948.0805095727447, 1867.62759555324], 
    [947.857944, 1867.478882], 
    [947.7588018605959, 1867.3305052948585], 
    [947.610428, 1867.231365], 
    [947.5112877051412, 1867.082991139404], 
    [947.362911, 1866.983849], 
    [946.1825, 1865.217239], 
    [945.767995, 1863.133381], 
  ]
];

const points2 = [
  [
    [956.906279, 1863.380898], 
    [956.491774, 1865.464756],
    [955.311363, 1867.231365],
    [953.544754, 1868.411776],
    [951.460895, 1868.826281],
    [949.377037, 1868.411776],
    [947.610428, 1867.231365],
    [946.430017, 1865.464756],
    [946.015512, 1863.380898],
    [946.430017, 1861.297039],
    [947.610428, 1859.53043],
    [949.377037, 1858.350019],
    [951.460895, 1857.935514], 
    [953.544754, 1858.350019],
    [955.311363, 1859.53043], 
    [956.491774, 1861.297039], 
  ]
];

console.log('start');
polygonClipping.union(points1, points2); // eternal loop
console.log('end');

This line checks that the array length is 2 and fails if there is a third z coordinate https://github.com/mfogel/polygon-clipping/blob/master/src/clean-input.js#L27

Happy to submit a PR to allow a length of 2 or 3 on this line, but I'm not familiar enough with code yet to know if that will cause other problems? The z values are not needed in my case, just sometimes present in data my users upload. Just wanted to raise this here in case it is a quick fix.

Also thanks for putting this library together, super helpful!

If a polygon has an internal segment that is infinitely thin, polygon-clipping can crash. For example, performing a union on the following shapes results in a SweepEvent comparison failed at [-1, 0]... equal but not identical?

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "type": "Polygon",
        "coordinates": [
          [[-2, -1], [-1, 0], [1, 0], [2, -1], [2, 1], [1, 0], [-1, 0], [-2, 1]]
        ]
      }
    },
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "type": "Polygon",
        "coordinates": [[[-3, -3], [3, -3], [3, 3], [-3, 3], [-3, -3]]]
      }
    }
  ]
}

The polygon above polygon causing the problem looks like this:

What's going on here is that the algorithm doesn't know how to sort the two segments from the same ring that both go from [-1, 0] to [1, 0].

Error: Self-intersecting, crossing input ring found at [1159.7391304347825, 863.0434782608695]

I am not sure if this is a bug or an issue with my input, I am assuming its an issue with my input. How would I fix this normally with js? Otherwise if it is a bug I can give more information.

Thanx a lot for you lib
Please can you give a small example of using it without node.js
We have "snake" track and we need to calculate interselections and show it.
is anyone hase the same task ?