If the polygon is convex the proof is simple. Let me illustrate with a hexagon. Label one of the six vertices q and draw three segments, connecting q to the three vertices on the far side of the hexagon. Now q is connected to everything, and the shape is divided into 4 triangles. The angles of all these triangles combine to form the interior angles of the hexagon, therefore the angles of the hexagon sum to 4×180, or 720.

If the polygon is not convex, we have more work to do.
If a line can be drawn from one vertex to another, entirely inside the polygon,
the shape is split in two.
Triangulate each piece separately, and the entire shape is triangulated.
So all we need do is find an internal segment for any given polygon.
Let x be a point with interior angle > 180°. If there is no such x then the shape is convex, and any two points can be connected to cut the shape in two. Otherwise start at x and draw a ray that is almost in line with one of the two incident edges. Let this ray intersect the polygon in a point y. If y is a vertex we are done, but y is probably a point on one of the sides. Slowly pivot the ray about x and let y slide along the outside of the polygon. If the ray suddenly crashes into an inlet, let z be the new point of intersection. Now xz is a segment that cuts the shape in two. If the ray does not run into an inlet, y eventually becomes an end point, and xy cuts the shape in two. Repeat this process for each piece, and then each of those pieces, until the shape is triangulated. But how many triangles are involved? Assume the segment xy cuts the shape in two, and when each piece is fully triangulated, it has two more edges than triangles. Put the two pieces together and count edges and triangles. Let the first piece have k edges and the second piece have l edges. Since xy is not part of the original shape, it has k+l-2 edges. And it has k-2 + l-2 triangles. Thus the polygon has two more edges than triangles. By induction, an n sided polygon has n-2 triangles inside, and the interior angles sum to 180×(n-2). |