1

Im trying to figure out the details of this algorithm posted here Extension to crossed polygons(Scroll down).

The algorithm states that the sum of angles of any polygon can be found by the formula 180(n-2k) where n is the number of vertices and k a positive whole number of 360 revolutions found by walking around the perimeter of the polygon.

I do not know how to find k for a crossed square. Could someone explain how to find this maybe with a diagram? Thank you for your time.

Crossed Square It says for simple polygons k should be one so i assume for complex k should be higher.

If you can get the java applets to work this link might be of help. I cant get them to work however so please if you can relay your findings back to me.

For more complex shapes the answer is not clear. For example a "spring" shape composed from two crossed square linked together. There are two possible sums depending on where you start walking the polygon. Unless you specify that going clockwise is a positive angle and counter clockwise a negative angle instead of having angles be relative and signs arbitrary.

enter image description here

Ultimately my end goal is to use this formula to test if a polygon is convex or not. Combining it with another formula i get 180n - 180(n-2k) == 360 means that its convex. Is this formula flawed in any way?

Lead Vaxeral
  • 13
  • What do you mean by a crossed square? A shape like a bow-tie or a butterfly? If so, I think $k=0$. – bubba May 30 '21 at 04:40
  • But that doesn’t seem right. $k$ is supposed to be positive, and $360k$ is supposed to be the sum of the exterior angles, which is 540. Puzzled. – bubba May 30 '21 at 04:57
  • @bubba This is a crossed square of four points. https://i.stack.imgur.com/ORCVC.png – Lead Vaxeral May 30 '21 at 10:18
  • Yeah im just as confused as you are @bubba. Ive considered multiple ways of calculating k none seem satisfactory. None of the ways line up with what the wiki is saying. – Lead Vaxeral May 30 '21 at 21:32
  • I think the Wikipedia statements are wrong. Or, at best, expressed in a very confusing way. – bubba May 30 '21 at 21:38
  • @bubba I think ill try and contact the author of the article i linked and see if he has some answers. – Lead Vaxeral May 30 '21 at 22:31
  • @bubba it turns out your first statement is correct. http://mysite.mweb.co.za/residents/profmd/stars.pdf (Second page) When you walk the perimeter angles can cancel out and therefor k can be zero. I'm not sure about the 360k equaling the exterior angles though. Maybe the angles keep their sign when summing them. – Lead Vaxeral May 31 '21 at 00:48

1 Answers1

0

The Wikipedia article is flawed. It says that the sum of exterior angles is $360k$, but this is only true if you sum signed angles. Also, it says that $k$ is necessarily positive, but this is not true, as the crossed square example shows.

If you’re writing code, I don’t think computing $k$ is a very good way to test convexity. It requires computation of angles, so it involves trig functions, which might cause performance problems.

Another easy way to test convexity is as follows: At each vertex, compute the 2D cross product of the incoming and outgoing edge vectors. So, if the incoming vector is $\mathbf u = (a, b)$ and the out-going vector is $\mathbf v = (c,d)$, you compute $p = ad - bc$. The sign of this quantity $p$ tells you whether there’s a left turn or a right turn at the vertex. The polygon is convex if and only if $p$ has the same sign at each vertex. So, you cycle through the vertices, computing $p$ at each one. If you find two vertices with opposite signs, you quit and conclude that the polygon is not convex. Otherwise, if the signs are all the same sign, the polygon is convex. This approach is fast because it doesn't require computing any angles, so no trig functions to slow you down.

bubba
  • 43,483
  • 3
  • 61
  • 122
  • and ths should work for self intersecting polygons as well? Ah well it wont work for crossed star polygons. – Lead Vaxeral May 31 '21 at 08:26
  • Convexity is a property of a set. When we talk about polygons, we’re really talking about the set of points that are “inside” some polyline boundary. If you have a self-intersecting boundary, it’s not clear which points are “inside”, so it’s hard to talk about convexity. There might be some other definition of convexity that works, though. – bubba May 31 '21 at 22:17