All examples By author By category About

nitaku

Concavity

Test if a polygon is convex or concave, regardless of its orientation (points given in clockwise or counterclockwise order). Also, highlight which vertices determine a concavity. Hollow polygons are concave, while filled ones are convex.

Polygons in the first line have a counterclockwise orientation, while the ones in the second line have a clockwise orientation.

First, an implementation of this algorithm computes the orientation of the polygon. The result determine the polygon's color, blue for CCW, orange for CW.

Then, a variation of another algorithm computes the orientation of the inner angle for each triplet of vertices. This is shown as the vertex color, again, either blue (CCW) or orange (CW).

Finally, each vertex with an orientation that's different from the one of the polygon is highlighted (represented as hollow). If there is already one of such vertices, then the polygon is concave (also represented as hollow).

In order for this method to work, polygons must be noncomplex (i.e. without self-intersections), their vertices must be at least three, must not be coincident and must not be colinear. I am convinced that there are better ways to obtain the same result, if you happen to know one, please comment on this example Gist page.