Find the number of internal angles of a polygon, bigger than 180º

Question

How can I find the number of internal angles of a polygon, bigger than 180º, having only the vertices of the polygon?

For each vertex I want always the internal angle, not the external.

Thanks from Brazil.

Answer 1

I'm assuming this is an irregular polygon, since it would be really difficult for a regular polygon to have an internal angle greater than 180 degrees.

For each vertex, you would also need to know the two neighboring vertices. You can then turn this into a trigonometry problem, where you find the angle from the main vertex to, say, the left vertex, and add it to the angle from the main vertex to the right vertex.

For example,

tan(angle_to_left) = (v.y-left.x)/(v.y-left.y)
tan(angle_to_right) = (v.y-right.x)/(v.y-right.y)

Then add the angles together.

Finally, for all angles that are greater than 180, increment a counter. After going through all of the vertices, your counter will tell you how many internal angles are greater than 180.

Answer 2

1. Find the convex hull of the vertices.
2. Identify the vertices that do not lie on the convex hull. These are your candidate vertices with >180 external angles.
3. For each such vertex investigate further about the angle (Can't think of any way right now but you can extend this).

Answer 3

The problem with tangent is when x==0. If you only know the vertices of the polygon, you don't know enough unless it's a triangle since they could have any sort of connectivity.

Assuming you know the connectivity, you will then need to calculate the winding order (i.e., in what direction do the points go around the polygon?). With the winding order, you can then take the cross product of every point with its neighboring points and take the inverse sine of magnitude of that to get the angle.

Answer 4

You can determine the angle of two vectors simply by taking the scalar product (dot product). A useful property is that if the vectors are orthogonal, their scalar product is zero; if their angle is obtuse, the product is negative, otherwise positive. So, the steps to take are:

• find the first edge from V0 to V1 (as a vector, you get this by subtracting the coordinates), then rotate it by 90 degrees to the left (this is just transforming (x y) to (-y x))
• find the second edge from V1 to V2 (not rotated)
• take the scalar product (this is just (x1 * x2) + (y1 * y2))
• if the scalar product is negative, it is a right turn, otherwise a left turn
• next edge...
• if you go through the vertices counter-clockwise, count the number of right turns, otherwise the number of left turns
• for the last vertex, you have to return to the first (i.e. use the edges Vn to V0 and V0 to V1)

edit: You can find whether the vertices are ordered counter-clockwise or clockwise by using the following formula to calculate the polygon's area:

     1  n-1
A = --- SUM( x(i)*y(i+1) - x(i+1)*y(i) )
     2  i=0

where n is the number of vertices. x(n) and y(n) are the same as x(0) and y(0) (to close the polygon).

If it is positive, then the vertices are ordered counter-clockwise, otherwise clockwise.

edit: When you simplify the steps of rotation and scalar product, you arrive at the formula for the two-dimensional cross product, x1*y2 - x2*y1. This simplifies the first steps above:

• find the first edge from V0 to V1 (as a vector, by subtracting the coordinates)
• dito for the second edge from V1 to V2
• take the cross product ((x1 * y2) - (x2 * y1))
• if the cross product is positive, it is a left turn

Sorry for the convoluted first approach.