Intersection/union of two valid polygons can create invalid result.

[OliverColeman]

Got some more for you :)

https://codesandbox.io/s/wild-snow-0801g?file=/src/index.ts

EDIT: updated the link for one that includes multiple failing pairs of polygons.

[alexbol99]

Wow, Oliver,
you did a great job!
I will check all of your examples.

But the fact that function isValid() gives false does not mean that polygon is illegal.
It depends on what do we want to do with such polygon.

The method isValid() checks that all faces are simple, i.e they do not have self-intersections.
If polygon is self-intersected, we still may display it, perform transformations or measure distance.
What make problem are boolean operations and inclusion checks, because they rely on the orientation of the polygon, which is undefined in case of self-intersection.

So if we want to use the result in boolean operations, we have to clean up self-intersected polygons. flatten-js library does not have a method to fix self-intersected polygons, but it may be added if someone will ask.

But again, I will check all your examples if they give legal results, and add them to the test set.

Maybe I will change the name of the method to isSimple() to avoid misunderstanding.

Thank you for contribution to this project

Best regards,
Alex.

[OliverColeman]

Hi Alex :)

Is my assumption that a boolean operation between simple polygons should result in a simple polygon incorrect?

In my case I do care about the resulting polygons being valid because:

• I have multiple stages in my algorithm that perform boolean operations, feeding the result of one boolean op into another boolean op.
• The polygons are intended to enclose an area, so I do care about which areas are contained vs not contained (micro-self-intersections are probably not a big deal, but also not ideal).

I would be very interested in a feature to fix non-simple polygons! I looked around but struggled to find an algorithm for doing this...

[alexbol99]

Hi Oliver,

Strictly speaking, you are right, boolean operation with valid polygon should give valid result.
In the real life the operation may give degenerated polygons with zero area or edges that go one upon another.
Polygons with circular arcs (which you don't use) can easily give self-intersections due to numeric errors.
I simply know this from my 20-years experience with such polygons in our CAM system.

As for current implementation of self-intersection check in flatten-js library I admit that it is too loose.
Real self-intersection point is where polygon changes its orientation.
It means this polygon should not be considered as self-intersected because it does not change orientation:

(We can't know it from the picture, but from the way it was constructed)

So from this discussion I see 3 action items:

• Give more strict self-intersection check
• Provide method to fix self-intersected polygons
• Provide method to detect degenerated polygons (such polygons impossible to fix, just exclude them from the further processing)

It will take some time, but I can do this.

Best regards,
Alex

[OliverColeman]

I understand re numerical errors etc. After having tried a few polygon manipulation libraries I'm getting the strong impression that they are very hard to engineer well. Flatten-js is by far the best and most stable so kudos to you!

It sounds like for most practical intents and purposes these "invalid" polygons will not be an issue. I can certainly update my code to ignore degenerate polygons, thanks for the tip :)