Is there an algorithm that can decide whether a polygon is self-intersecting using only its vertex coordinates?

Question

I'm trying to determine whether a polygon is self-intersecting or not by calculating the sum of the interior angles; i.e. if the sum is less than $(n-2)\pi$, then it is self-intersecting. The information that I have is the ordered set of vectors locating the vertices on the plane. I can calculate the angle between sides using dot and cross product, but my algorithm doesn't distinguish between internal and external angles. Also, I need the algorithm to work regardless of the polygon's regularity and convexity.

Any suggestions will be much appreciated.

Answer 1

Update: As noted in a comment, this algorithm does not reliably test self-intersection. Consider any convex polygon and replace one edge by a sequence of edges that crosses another edge and then crosses back again. What you can determine from angles is the number of "turns" the path makes before reconnecting, but not the number of self-intersections.

---

I'll assume that your vectors are from vertex $1$ to vertex $2,$ then from vertex $2$ to vertex $3,$ and so forth, until finally the last vector is from vertex $n$ to vertex $1.$

I would prefer to work with the exterior angles. If you must work with interior angles, you may have to make some modifications to the following procedure.

As you work your way around the polygon, always use the "first" side of each pair of consecutive vectors as the first vector of the cross product. The cross product has a direction as well as a magnitude. For some pairs of vectors, this direction may be opposite from the direction found for other pairs of vectors.

Treat the first pair of vectors, and all others whose cross products are in the same direction, as adjacent side at vertices with positive exterior angles. Treat all others as negative exterior angles.

The sum of all angles may then be positive or negative. For example, the sum of angles of a non-convex non-self-intersecting polygon will be positive if your first vertex is one of the "convex" vertices, but negative if the first vertex was "concave." The magnitude will be the same no matter which vertex you start with, however. So take the absolute value of the sum of angles.

The result will be a multiple of $2\pi$ if your calculations are exact. With inexact numeric calculations it will be approximately a multiple of $2\pi.$ You can consider the polygon self-intersecting to make more than one "turn" if this result is greater than $3\pi.$