Unify fails when polygons are wound in opposite directions

[yowzadave]

If two polygons are constructed, the first in a CCW direction and the second in a CW direction, the resulting union is not correct:

const polygon1 = new Polygon();
polygon1.addFace([point(0, 0), point(10, 0), point(10, 10), point(0, 10)]);

const polygon2 = new Polygon();
polygon2.addFace([point(8, 2), point(8, 8), point(20, 8), point(20, 2)]);

const result = unify(polygon1, polygon2);
// result is not the expected shape

[alexbol99]

Hi, @yowzadave ,

Indeed, unify algorithm relies on polygon orientation. Two polygons should have same orientation, it is easy to check this and revert orientation if need. Maybe I have to clearly reflect this fact in documentation. See also https://github.com/alexbol99/flatten-js/issues/50

[yowzadave]

@alexbol99 thanks for the explanation! What about individual faces within a polygon? I.e., should all faces within a polygon be oriented in the same direction before performing a boolean operation?

[alexbol99]

Hi, David, Flatten-js support multi-polygons, comprised from a number of faces, some of them may be external, some internal. Internal faces represent holes - cut-off areas inside a polygon, and their orientation should be opposite to the outer polygon they belong. unify (and other boolean operations) assume that both polygons have same meaning of orientation, for example, in both polygons outer faces oriented counterclockwise, and inner faces oriented clockwise. Best regards, Alex

[alexbol99]

Hi, David,

You asked if there is any way to detect if face in polygon is external or internal. (I can't see you response here, I don't know why) Usually user set up orientation when he create polygon, then it is possible to use face.orientation() method. If polygon has external source it may be more complicated, because in general we need to check inclusion between faces. Flatten-js does not provide generic method for this. Do you want to describe you use case and maybe send some data sample? I will try to help.

Best, Alex

[yowzadave]

Thanks--I'm taking user data to build a polygon, so I can't rely on it always being constructed in a counter-clockwise or clockwise direction; therefore I need to check the orientation of both polygons before performing the union to ensure that they are oriented uniformly.

I noticed that at times when doing a unify the order of the faces can be switched, so knowing the orientation of the polygon as a whole is not as simple as checking the orientation of first face. One approach that occurred to me is to check all of the faces; the one with the largest area should be an exterior face. I just wondered if there was a simpler approach.

[alexbol99]

I have a method polygon.splitToIslands() which returns an array of polygons, where each polygon is ordered by inclusion of faces: the first face is an outer (we call it "island") and the others are internal (we call them "holes). You can use it before and after unify , because unify indeed does not keep an order of faces. I can also add a method that rearrange faces in polygon in the way that island always precede holes, if it may help Best, Alex

[alexbol99]

Closed, question is answered