Awesome work @mfogel for tracking it down to something so small!

For me it doesn't work. Maybe it's the recent changes that are breaking it?

Hmm yeah I've also checked this out and still get an error on http://localhost:5000/demo/#overlap_two. Although if I reduce the remove all the decimal points in the overlap_two input file I don't get an error, so perhaps it's related to the precision somehow. I've managed to trim it to 6 decimal places before it crashes.

That said that wouldn't explain what's happening with the heap overflow reported here so I wonder if that's a separate bug

Should also report that @mfogel fix does appear to work for the original single polygons he reported, but not the multipolygon (which is probably related to #56 and our poor handling of multi-geometries)

My take is overlapping multipolygons should be treated as a separate issue. I think that'll be a more involved change - at very least I think it could require adding some more information to the SweepEvent object.

When clipping is a multipolygon with overlapping/adjacent polygons and you are computing diff or xor, then I don't think inResult can be computed from just event.otherInOut. Consider the case when doing a diff where a clipping edge is within the subject (so normally it would be included in the result set) but it is also within another clipping polygon. Because it's within another clipping polygon, that edge should not be part of the result set, but it's currently included.

For union and intersection I think it's enough to know if an edge is within any polygon of the other 'type' (ie - is a given clipping edge within any subject polygon? is a given subject edge within any clipping polygon?) I might be missing something, but I think the current tracking and passing down of inOut and otherInOut doesn't hold all this information.

In any case, I think it would make sense to take a stab on that separately from this bug fix.

@mfogel Mike, thanks for the fix, which certainly did help another issue I had.

But I did some testing with this PR. I also have PR#60 hand-merged in. I found that my local branch with #58 and #60 introduced a failure for the following case:

const polygon1 = [[[-84.9122110067411, 41.191530524433],
  [-84.9101733650649, 41.1906948480718],[-84.9103778843761, 41.1904346737203],
  [-84.9103708435675, 41.1903709706296],[-84.9122110067411, 41.191530524433]]];
const polygon2 = [[[-84.90797269230876, 41.190394],
  [-84.9103708435675, 41.1903709706296],[-84.91037338889753, 41.190394],
  [-84.90797269230876, 41.190394]]];
intersection(polygon1, polygon2);

The error it shows is:

TypeError: Cannot read property 'balanceFactor' of null
    at AVLTree.remove (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:672:11)
    at subdivide (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:1809:19)
    at boolean (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:1403:22)
    at boolean.intersection (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:1428:10)

I'm happy to help with running more tests, providing info, etc. Of course, I'll look for my own bug fix as well. I'm very motivated to use w8r/martinez on a project and it depends on working through the remaining bugs.

A curious thing is that the removal of any of the interior points in the ring will cause the test above to pass. I simplified the polygons as much as I could.

There are a lot of decimal points there, what happens if you trim the decimals down to say 5 places @erikh2000 ?

@erikh2000 not sure exactly what's going but I think that error is occurring when the algorithm is processing a right-hand node - that's when it tries to remove elements from the AVL tree. It may be that the comparison methods that the AVL tree is using are returning inconsistent results. Or it could be that a node was altered after being inserted into the tree. That is a lot of decimal places, but the shapes I'm working with are similar (from OSM). One thing you could try is replace EPSILON here with Number.EPSILON... a shot in the dark.

I've ran across a handful of errors like this that I haven't tracked down and haven't reported here. I need the functionality this package intends to offer though... so I forked the project last week and am working full time on a replacement. If you're interested, you can follow the progress on the branch here. I was budgeting two weeks to get it out the door, but that was a week ago and I'm not halfway done yet :/

another problem with this AVL tree is that it mutates the nodes on removal. And I could not fix that, it's how it was designed. I have a splay-tree of a pretty much same performance to replace it, maybe this one will do it.

@rowanwins Good hunch. I truncated down to 7 decimal places. (The actual precision I need for centimeter-level measurements of geocoords with a little extra to avoid cumulative rounding errors) The test passes with that. Cool.

Maybe you could generally truncate params in martinez-polygon-clipping and get good reliability with AVLTree. But I think the precision people want varies a lot. There will be some people that are surveying things with lasers, etc. and want even sub-centimeter accuracy on geo coords. And probably some folks that want to use the library for non-geo-coord based calcs. Of course, if you don't enforce boundaries for latitude and longitude, people can multiply their "in" params, and divide their "out" results to get it to work. I checked GeoJSON RFC 7946 and found it is agnostic on precision requirements other than they they recommend not to use more than is needed and consider 6 digits to be a practical choice for many people.

And I say all that realizing that when you said trim down to "5 places" you were probably just giving an example for troubleshooting purposes. I am just hoping that this library doesn't end up insisting on too coarse of precision.

@w8r When you say "mutates" do you mean it changes the stored value? Maybe I will add some unit tests in my project to verify I'm getting the same coords back or at least within an acceptable tolerance.

@erikh2000 mutates means that on remove it actually switches 2 nodes, updating the key and balance of the one that is left in the tree

I was budgeting two weeks to get it out the door, but that was a week ago and I'm not halfway done yet :/

Lol welcome to the challenge that has been martinez - everytime you think you're making progress you find something else 😖

Folks, I just got approval from my company to make open source contributions to this project. Now, you may not want them from me, and that would not hurt my feelings. But I am happy to create some PRs for you oriented towards test cases and bug fixes. It's my Day Job Mission this week (and possibly next) to get intersection(), union(), and difference() ready to use in our production code. This may be accomplished in the form of a local fork that we build from, or wrapping the calls in clever ways, but it's my aim to share back to the project if you want it.

Gday @erikh2000 - that is good news, don't worry too much about your skill level, I'm not as smart as @mfogel or @w8r but hopefully we can still make some sensible contributions, at the very least we can provide some simple test cases :)

Re the decimal precision there is a big area in computer maths around floating point precision - google it and you can read weird maths stuff for hours! Apparently computers sometimes struggle with maths when lots of decimal places are involved (probably a really bad explanation sorry but Im still grappling with it myself). One the ways around this is to introduce epsilon values which kind of serve as a tolerance threshold (I think), you'll see epsilon values scattered in a few places throughout the martinez lib. In a similar library they've tackled the floatpoint/epsilon issue this way, I'm not sure if there is anything in that worth considering....

Inline with the above I have a couple of suggestions, perhaps for @w8r

1. Could we expose a global setting for the epsilon?
2. Is there a good way to detect that we've entered the death spiral of floating point loop and throw an error and tell people to truncate their data?

@erikh2000 this is very much appreciated. This is how this project started actually, by an approval and funding to work on that algorithm for 2 weeks.

• Could we expose a global setting for the epsilon?
• Is there a good way to detect that we've entered the death spiral of floating point loop and throw an error and tell people to truncate their data?

Yes we should. and for the second one there should be a simple test case that would allow us to undertand whether we can avoid that.

I have another failing test case that is interesting because it only uses integers. I basically moved the decimal point 6 places to the right, but still ended up with an exception in AVLTree. As I was simplifying points from the original more complex polygon params, I noticed the exception would change. I saw all of these exceptions:

TypeError: Cannot read property 'right' of null
    at rotateRight (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:166:15)
    at AVLTree.insert (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:576:47)
    at subdivide (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:1801:32)
    at boolean (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:1431:22)
    at boolean.diff (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:1446:10)

TypeError: Cannot read property 'balanceFactor' of null
    at AVLTree.remove (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:680:11)
    at subdivide (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:1840:19)
    at boolean (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:1431:22)
    at boolean.diff (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:1446:10)

TypeError: Cannot read property 'left' of null
    at rotateLeft (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:135:19)
    at AVLTree.insert (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:584:47)
    at subdivide (/Users/erik.hermansen/gitrepos/martinez/dist/martinez.js:1801:32)

The final exception above is what the test case below produces. This is running against master branch with PR #58 and PR #60 merged.

var param1 = [[[[-84912294, 41192297],[-84908826, 41191241],[-84909297, 41191248],[-84912294, 41192297]]],[[[-84911824, 4119319],[-84909003, 41190473],[-84908828, 41191583],[-84911824, 4119319]]]];
var param2 = [[[-84912294, 41192297],[-84908826, 41191241],[-84909430, 41191262],[-84912294, 41192297]]];
diff(param1, param2);

I realize that @mfogel is working on a replacement to AVLTree, so this is probably moot. But it underscores that we can't work around the AVLTree bugs by reducing precision.

Hi @erikh2000

I've replaced avl locally with splaytree as suggested by @w8r (a simple change in subdivide_segments.js to the require statement). I've tested your diff case above with no decimals and it appears to be ok, although the map isn't showing it very well on the demo.

What is the problem with the map? Zoom limit?

Yep, but it was late so I didn't really investigate

Makes sense that map wouldn't display for the integer coords from the last test case. The image I pasted in actually had the decimal points at the original six places of precision.

Great news about your success with splaytree.

FYI I've released that fork of martinez I mentioned earlier as polygon-clipping This bug is fixed there, along with every other one in martinez that I know about. Also implemented over there are unary union/intersection/xor, as mentioned in #34

If you find anything that appears to be broken in polygon-clipping - please file an issue I will get on it and fix it up! Cheers.

@mfogel this is really cool! Did you by any chance run the benchmarks we had for that? The code looks definitely cleaner than what we have here, what's your plan? Care to merge back if the benchmarks are ok? Cause for me unary union is a more important step ahead than the tweaking we are trying to do here.

@w8r I haven't run benchmarks yet, I pulled that code out early on with plans to reinstate it but haven't yet. For my use case performance isn't all that important, as this is in a data pipeline where there are other bottlenecks that are causing bigger problems. My gut is that for the basic union-of-two-complicated-polygons performance has probably degraded compared to what's implemented here in martinez - just because there's more classes and function calls in my implementation, for the sake of clarity, but at the detriment of performance. There may some easy wins in optimization though - I haven't done any profiling at all.

You're welcome to merge back as much or as little as you like. It's really pretty much a full rewrite at this point (done incrementally starting from what exists here in martinez) so it may be difficult to merge back isolated parts. Actually, if you were going to merge back anything, it might best to start with the end-to-end portion of the testsuite, which is available here and here. I wrote it for Jest but it shouldn't be too hard to adapt it to work with tap.

Good, classes and function calls shouldn't be much of a problem, as long as the main idea of the paper was not lost. Reading your code I found a comment saying that you had to avoid the AVL-tree problem, did you try replacing it with the splay-tree that I wrote, as we tried doing here? It has exactly the same API but doesn't suffer from that problem.

Why did you have to go with a complete rewrite, any points in the code that were badly designed or difficult to get around?

Thanks for sharing it back, also how did you approach the unary union? Just by treating the input differently? I cannot see it clearly from the API

The main idea of the paper isn't lost - the algorithm still does one pass over the endpoints of the line segments. So I think that the overall running time shouldn't have changed O((n+k)*log(n)) according to the paper, as I understand.

I haven't tried using the splay-tree, by the time I saw the comments about that here I had already adjusted use of AVL tree to avoid the problem I ran into. Using it might allow some simplification of the code in sweep-line.js

I didn't intend to go for a complete rewrite here. I basically ended up doing it just trying to get a handle on everything going on in the algorithm. And trying to unit test each part individually as much as possible. I would have rather just fixed small parts here and there to get it working in my pipeline as I need, but I wasn't able to do that.

The unary union - once all the tests were passing for the two-argument case (including overlapping multipolygons - which is the hard part) unary union/intersection/xor did not require as much additional logic as you might think. Basically just the logic here was expanded, and I added the additional properties needed on the Segment object to support that logic.

@mfogel, I cloned your repo and gave it a try. Some of the cases that were failing in w8r/martinez are succeeding in yours. (Nice!) Some others are failing. One error I see is SweepEvent comparison failed at [${a.point}]... equal but not identical?. I can provide test cases or other details if it helps. But I don't want to throw a lot of text at people not ready to look at it. Also, I'm not sure if it makes sense to post them here--maybe better to post them in issues on your repo.

Let me know if you want the information, and if so, a good way to give it to you.

@erikh2000 failing test cases - awesome. Probably best to open up a new issue over at the repo. Or if you prefer, you can email me the test cases and details, my email addr should be listed on my profile page (let me know if it doesn't show up there).

Any updates on this? This would definitely be a great fix to have on my end. Let me know if there's anything I can do to help!