polygon triangulation reflex vertex

Question

Hi i am trying to perform polygon triangulation. I understood the ear clipping method for a simple Polygon ( Concave or Convex ). i am stuck at finding whether a vertex is reflex or not . what i have read at multiple places is about clock-wise and counter clockwise orientations which i am unable to understand . in short what are those orientations referring to and please give me some hint on checking whether the vertex is reflex or not . here is the link of an article i am following:

and here is formula they have used:

  // Input
    VECTOR a, b, c; // the parts of our triangle.
    // if (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y) > 0
    // we are counter-clockwise

whats the point here i am unable to comprehend.

Answer 1

Your input polygon is in most cases a list of consecutive vertices, they represent your polygon in counter clockwise order. That means when walking along the boundary of the polygon (if without holes) the interior of it should be to the left of every edge traversed. If one wants to know if a single vertex is convex or reflex (convex meaning internal angle smaller than 180°, reflex otherwise) then there are several methods. The most commonly used is to apply the determinate. The determinate gives us as result greater zero if the vertices form a left turn, which means that three consecutive vertices a,b, and c form a convex angle at b; and less than zero otherwise. Now the formula: (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y) > 0 does exactly that. It transforms the three vertices into two direction vectors: b-a and c-b then the determinate of this is already the given formula and tells us if a left or right turn occurs on b.

Edit, due to the question in the comment:

Let us choose a=(2 1), b=(5 4), and c=(3 6). Thus, the orientation as shown on the right picture is given by s=b-a=(3 3) and t=c-b=(-2 2). Now det(s t) gives us s.x*t.y - t.x*s.y = 3*2 - (-2)*3 = 12 > 0. Therefore, if we stand at point a and we walk to b, we have to take a left turn to get to c.