some issues related to winding order, PointInTriangle Test, signed area

[Fribur]

Unity uses a clockwise winding order for determining front-facing polygons, and earcut always spat out counter clockwise indices for clockwise polygones. Spending days chasing the issue in earcut, I feel I traced it down to a couple of things I feel where not quite right(?). Things are working now as expected for me. Could you have a look into this?

(1) David Eberly's algorithm for finding a bridge between hole and outer polygon, first if test in do-loop: when testing outer polygone p clockwise, then first bridge candidate to hole h has py < hy and next py > hy , otherwise py > hy and next py < hy will never happen, because LinkedList is always constructed such that outer polygon is clockwise. Consequently I changed test from this:
if (hy <= p.y && hy >= p.next.y && p.next.y != p.y)
to this:
if (hy >= p.y && hy <= p.next.y && p.next.y != p.y)

(2) pointInTriangle function: DOT product test (=method 3 here) needs to work regardless of triangle winding, see here. Changing the function to this will deliver that:
function pointInTriangle(ax, ay, bx, by, cx, cy, px, py) { var side1 = (cx - px) * (ay - py) - (ax - px) * (cy - py); var side2 = (ax - px) * (by - py) - (bx - px) * (ay - py); var side3 = (bx - px) * (cy - py) - (cx - px) * (by - py); return (side1 > 0 && side2 > 0 && side3 > 0) || (side1 < 0 && side2 < 0 && side3 < 0); //first test works for CCW-triangles, second for CW-triangles }

(3) area function returned exactly opposite of what is expected: the following proposed change should result in expected behavior (CCW triangle = positive area, CW triangle = negative area, see here)
function area(p, q, r) { return (q.x - p.x) * (r.y - q.y) - (r.x - q.x) * (q.y - p.y);}

[Fribur]

Mourner, I believe my proposed changes are the fix to issue #44, which was classified as "enhancement": #44 (comment)

I find a couple of other projects reporting this is a bug, most fixes reverse the final output array (which is a bit inelegant in my mind)

Instead of reversing the final output triangle array, my proposed changes above simply result in preserving the order of the input polygons: CCW polygons result in CCW triangle output list, and CW polygons in CW triangles. Should also be performance neutral. Would you like me to issue a pull request to avoid any ambiguity about the proposed changes?

[prevuelta]

I'd love these updates in a PR so I could fork :)

[andreasplesch]

Since I would like to use just the maintained version which seems not concerned about winding order, I was looking for a quick way to check if the output winding order changed.

I think it may suffice to just check if there are any consecutive indices in the output. This would mean that some edge was preserved in the same order, and assuming that all output triangles have consistent winding order which always seemed to be case would then also mean that the complete output has preserved order.

If there are no consecutive indices, I think it means that the winding order was flipped which can then be accounted for by reversing. The reversing and checking will take some time, so not advised if performance is critical. But in my use case triangulation does not need to happen very often.

It should be only necessary to check the first output triangle and that may worth testing as an optimization when flipping is expected.

Sofar in my experiments this seems to work. Let me share this here in case earclippers find that useful or problematic.

      let _triangulation = //currentPolygon.length == 3 ?
      //   [0, 1, 2] :
        EARCUT( [].concat(..._polygon), null, 2 );
      // check if winding order changed
      // If there is any consecutive edge, winding order should not have changed
      // assumes that each output triangle shares some edge with input polygon
      const flipped = !_triangulation.some( (v, i, a) => {
        //at last index check 2 easy edges, can skip check for edge from last to first point since there must be other edges
        return i % 3 == 2 && ( v == a[i-1]+1 || a[i-1] == a[i-2]+1 ) 
      } );
      if (flipped) {
        _triangulation = _triangulation.reverse();
      }