Rather than willy-nilly looping through all the input geometries, we should use what we know about each ring (is it a hole? what shape is it's parent?) to build a graph of rings and required operations. This should greatly reduce repetitive looping

Wrapping up a couple of big priorities that I've partially started on and hope to tackle a bit more during the holiday break

• Determine likely operations up front using bbox tests and simple logic
  • Ex: In intersect mode, Subject Boundary + Clip Boundary require intersection. Subject Boundary + Clip Hole require subtraction. We know this from the beginning and can calculate ahead
  • Bbox checks let us avoid work, which is 👍🚀
• Convert arrays to Ring and Vector up front. Only convert back to arrays during output.
• Change input format to use formalized objects
  • Following GeoJSON style means that the algorithm has to have intrinsic knowledge (that is unspecified!) and has to sort out whether you passed it a multipolygon with 3 rings or a polygon with one ring and 2 holes
  • Instead I want to implement a Polygon(ring, [holes]) class that can be used to generate proper input structures.
• Internalize pointInPolygon, isClockwise and other utility methods to make GH dependencyless

I think all in all this will help clean up and narrow down the focus, which will make it easier to reason about better degeneracy handling and let us kill failing degenerate cases.

In each image, JSTS result is on top, greiner-hormann on bottom

currently union executes a union-all - every outer hull is checked against every other, even if two came from the subject, for example.

This causes really poor union performance (in the tens of ops/sec on the Huge.json test case, vs the ~480 ops/sec that intersect and subtract get on the same case).

A union-all method is currently required, as it used internally in union and intersect for dealing with holes, so I'm proposing that union-all should be a separate implementation from union. It need not be made public.

Any clipping operation on two equal shapes will result in an undefined result.

Almost have this fixed, using geosquare/geojson-equality

unioning this case: http://bl.ocks.org/d/e4a5c39ebe8b6d0ef7c6

results in: http://bl.ocks.org/d/5ea632d78f68cbdf5b20

This is because holes are subtracted after the full outer-hull union is built. in this case, the necessary information to clip the hole into 2 holes no longer exists. Holes need to be be sliced up before the outer hulls are unioned.

Trying to solve #4, I found this issue;

Clipping these rings:

  [
    [
      [0, 0],
      [0, 3],
      [6, 3],
      [6, 0],
      [0, 0]
    ]
  ]

  [
    [
      [6, 0],
      [6, 3],
      [8, 3],
      [8, 0],
      [6, 0]
    ]
  ]

Results in:

[[[6,0],[6,3],[6,0]]]

So the first point is doubled when the result should be a linestring

Also, In the following comparison:

  [
    [
      [0, 0],
      [0, 3],
      [6, 3],
      [6, 0],
      [0, 0]
    ]
  ]

  [
    [
      [6, 0],
      [7, 2],
      [6, 3],
      [8, 3],
      [8, 0],
      [6, 0]
    ]
  ]

Which should result in 2 points (one at [6, 0], another at [6, 3]) resuts in the entire first polygon being returned. This is because for some reason during the flagging process, one of the intersections is being removed from the candidate list

The repo lacks a consistent coding style. It's also generally very useful to lint code because it often uncovers potential bugs.

http://eslint.org/ is awesome. Here's a sample config: https://github.com/mapbox/earcut/blob/master/.eslintrc

at a minimum, this could use bbox tests to to greatly reduce unnecessary operations

This is more of a discussion suggestion than a request. Polygon clipping and boolean operations is an incredibly important task in computational geometry, and it can be valuable in applications beyond Turf and geo. So I'd love to see this algorithm implementation become general-purpose and free of dependencies and assumptions about its use. This means:

1. Make it usable outside of Turf, e.g. just for geometric intersections/unions.
2. Not care about MultiPolygon/Polygon/etc distinctions — make the API more specific and add geo/Turf-related handling in a wrapper (separate from this repo)
3. Get rid of Turf dependencies — things like clockwise and point-in-poly detection are just a few lines of code so there's not much win from reusing geo-specific Turf modules.

cc @morganherlocker

"touching" intersections should result in a line where the two polygons touch. currently impossible

Trying out your kill-jsts branch of turf-intersect, and it's getting the version of this module before the extra logs were removed in 7816929. Any chance you could tag a new release?

this is the situation Im trying to stimulate:
https://cloud.githubusercontent.com/assets/236678/18207503/b61342e2-712b-11e6-881c-bb1970ab24bb.PNG
the data:

[
    [
        [
            [
                [0, 0],
                [0, 4],
                [4, 4],
                [4, 0],
                [0, 0]
            ]
        ]
    ],
    [
        [
            [
                [2, -2],
                [2, 5],
                [3, -2],
                [3, 5],
                [2, -2]
            ]
        ]
    ]
]

the code:

var subtract = require('gh-clipping-algorithm').subtract;
var json = require('./clippingtest.json');

console.log(JSON.stringify(subtract(json[0], json[1]),null,"  "));

output:
[[[[2.857142857142857,4],[2.142857142857143,4],[2,4],[0,4],[0,0],[2,0],[2.2857142857142856,0],[2.857142857142857,4]]],[[[3,4],[4,4],[4,0],[3,0],[3,4]]]]

The output is invalid..

I've run into some cases where corners disappear or lines bridge gaps, but they're not easily reproduced with visual tools.

It's occurred several times in my testing, but can't always get it to reoccur even when following the same steps, which leads me to believe numeric precision is causing the issues.

the subtracted clip should merge with the existing hole, but instead is added as a new hole.

Outside poly is a Multipolygon, inside is a Polygon

needs some cleanup / prep / docs

I ran into a case where https://github.com/tcql/greiner-hormann/blob/master/lib/union.js#L70 threw an error because unionRings ended up trying to push holes to the (nonexistent) holes parameter.

Also, if I'm understanding this right, could the line above actually result in a recursive case? I.e., you have two holes, but unioning them could result in "holes of holes", which themselves would need to be unioned with the original rings... ugh

removes the need to manually check array depth to determine result type

Because clipping with GH means decomposing to pairwise clip calls, there's a lot of looping and array modification in some of the operations. This can result in very slow operations when you have complex inputs, such as very large multipolygons.

I think we could optimize this a lot by doing some checks before looping over and clipping shapes multiple times. For instance, I think we could detect whether two shapes are touching in advance, and maybe even keep an internal index of shape relationships internally so consecutive internal GH calls won't have to do lots of useless legwork.