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

Question

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.

Answer 1

The property you're looking for is "star-shaped". Star-shaped polygons are are defined by having a point from which the entire polygon is visible.

To test that a polygon is star-shaped, you can construct the region from which the whole polygon will be visible. That region would be a convex set, so you can intersect it with a halfplane in O(log(n)).

That means you can intersect the halfplanes formed by the edges and check that the resulting visibility region is nonempty in O(n log n).

Answer 2

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;
    }
}

Answer 3

It looks like all potential centerpoints will need to be on the interior side of every edge of your polygon. So, treat all your edges as half-spaces, and determine if their intersection is empty or not.

As @jpalecek says, the term for this is star-shaped. If your polygon is star-shaped, there will be a convex polygon (interior to the original) whose points can view all edges of the original -- and, conversely, if no such sub-polygon exists, the original is not star-shaped, and you cannot draw it with a triangle fan.

Determining this sub-polygon is basically a dual application of the convex hull problem; it can be computed in O(n log n).