3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I modified the question's title to be more reflective of what it asks. If this doesn't really reflect your intent, feel free to click the "edit" link below your question and revert it to the original version. $\endgroup$ – Michael Seifert Apr 13 '17 at 21:15
  • $\begingroup$ It's not possible to detect self-intersecting polygons using only angles. For example, consider an 8-sided U-shaped polygon whose angles are all $90\circ$ or $270\circ$. You can make it self-intersecting without changing any angles by moving the bottom two vertices upwards. $\endgroup$ – Rahul Apr 13 '17 at 21:42
  • $\begingroup$ That's where the concept of internal angles shows up. By doing the modification you suggest, then all the 270° angles change to 90°. Thus, the sum of interior angles is no more $6\pi$, but $4\pi$. $\endgroup$ – GeoArt Apr 13 '17 at 21:48
1
$\begingroup$

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.$

$\endgroup$
  • $\begingroup$ While this will weed out some self-intersecting polygons, I don't think this (or any other algorithm that considers only angles and not edge lengths) will be able to detect all self-intersections. Basically, this algorithm only works on polygons that self-intersect an odd number of times, not on those that have an even number of self-intersections. $\endgroup$ – Jaap Scherphuis Apr 13 '17 at 11:28
  • $\begingroup$ @JaapScherphuis That's true. I was thinking only about what the OP asked, not what they needed. I did not delete the answer (yet) because the fact you mentioned may be useful to the OP. $\endgroup$ – David K Apr 13 '17 at 20:41
  • $\begingroup$ Actually, I was able to solve both problems using part of @DavidK's idea. I calculate each angle using dot and cross product following a direction. If the cross product is negative, I change that angle by $2\pi−\theta$. Once I have all the angles, I calculate the sum. If that sum is larger than $(n−2)\pi$ then I apply the redefinition above to the whole set of angles; if not, then I just let them as they are. That's how I get the interior angles. Again, if the sum is less than $(n−2)\pi$ the polygon is self-intersecting. $\endgroup$ – GeoArt Apr 14 '17 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.