About

Star shaped polygons have the property that there exists some point, called the kernel, within the polygon such that a line segment from the kernel to any point on the boundary of the polygon is completely contained within the polygon. If the kernel of a star shaped polygon is known, the shape can be triangulated in a fairly straightforward fashion. A demonstration of how to trangulate a star shaped polygon with known kernel in linear time can be found here . This is a demonstration of how to triangulate a star shaped polygon in linear time without knowledge of the kernel.

What's Going On

To begin select "Add points" on the left to create a star shaped polygon or "Generate random points" to have one automatically generated

First, click to add the kernel (this won't be used in the triangulation). It will be shown in red. Then, click to add points. The points will be automatically connected to form a star shape polygon around the kernel. The points may not be connected in the order that you add them. When you are satisfied with your polygon, click begin.

We start with our star shaped polygon

A random vertex of the polygon is selected. In this implementation, the random vertex is always the point with the maximum x coordinate. From this point, the visibility polygon is calculated. By definition, this visibility polygon is star-shaped, with a kernel at the selected point.

However, this subpolygon contains Steiner points (shown in blue), which aren't part of the original polygon.

So we compute the extended visibility polygon by sweeping the Steiner points away from the visibility polygon and towards vertices of the original polygon.

But now the subpolygon (i.e. the extended visibility polygon) is no longer star shaped.

So we construct a subpolygon of the extended visibility polygon which has no Steiner points.

This leaves us with several subpolygons:

In green

Star-shaped subpolygon whose kernel is known (and is a vertex).

In red

Good subpolygon weakly externally visible (WEV) across cut edge.

In purple

Subpolygons visible from a vertex

In orange

Subpolygon WEV from edge present in original polygon

These subpolygons can now be triangulated individually, each in linear time.

The star shaped subpolygon can be trivially triangulated by connected its kernel to every vertex.

The other subpolygons can be triangulated in linear time using the 3 coins algorirthm because they are WEV.

Once all the subpolygons are triangulated, the entire polygon is triangulated.

Our star shaped polygon has been triangulated in linear time without knowing where the kernel is.