Determine if a 2d polygon can be drawn with a single triangle fan

c++, computational-geometry, geometry, math

Solution

A polygon can be drawn as a triangle fan if the angle from the anchor to each vertex moves in the same direction. The easiest way to test this is to check the dot products of the cross products of the successive vertices.

It will look something like this:

vector lastCross = cross_product( vector(vertex[0] - center), vector(vertex[numVerts - 1] - center) );

canBeFan = true;
for (n = 1; canBeFan && n < numVerts; ++n) {
    vector testCross = cross_product( vector(vertex[n] - center), vector(vertex[n - 1] - center) );
    if (0.0 >= dot_product(testCross, lastCross) ) {
        canBeFan = false;
    }
}

Problem

At first, I thought this problem would be equivalent to determining if a polygon is convex, however it seems that a non-convex polygon could still be drawn by one triangle fan. Consider this shape, a non-convex polygon. One could easily imagine some region of centerpoints that would allow this polygon to be drawn with a triangle fan (although there would be other centerpoints that would not). Given a fixed centerpoint, I want to be able to determine if the set of 2d points defining the polygon allow for it to be drawn with a single triangle fan. It seems like the key is making sure nothing "gets in the way" of a line drawn from the centerpoint to any of the vertices, that means other edge lines of vertices. However, it is important to make this as computationally inexpensive as possible, and I'm not sure if there's a nice math shortcut to doing this. Ultimately, I'm going to have the vertices of polygons moving, and I'll need to determine the "boundary" a vertex is allowed to move, given the rest are fixed (and perhaps later even allowing the simultaneous reactive movement of the direct 2 neighbors as well), to keep the polygon capable of being drawn in a single triangle fan. But that's the future, hopefully the test over the full polygon can be broken into a subset of calculations to test the bounds of a single vertex's movement with the assumption of an already convex polygon.

Original source