CODEWITHSUNDEEP
algorithmgeometrypolygon
lucasbls1
lucasbls1

Reputation: 83

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

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.

Upvotes: 6

Views: 4497

Answers (6)

Niyaz
Niyaz

Reputation: 54793

This is a question related to geometry, not exactly progamming related.

If you have the vertices, you can just find the internal angles by trigonometry, similar to how you find the angles of a triangle.

Using three adjacent vertices, imagine a triangle and them find the internal angles.

For example, look at the polygon:

Polygon

We can construct a triangle as:

Construct internal triangle

Upvotes: -1

sdailey
sdailey

Reputation: 2030

Finding the interior angle of the last two vectors (as an example), we need to implement this equation for the last two vectors of the polygon:

angleRadians = Math.acos((vx1 * vx2 + vy1 * vy2) / ( Math.sqrt( vx1*vx1 + vy1*vy1 ) * Math.sqrt( vx2*vx2 + vy2*vy2 ) ));

this is using the Dot product of the vectors. If you have questions on this, here's a tutorial

But that does not take into account the 'winding direction', first you must get the cross product and, if the cross product is positive, it was a left turn, if negative--a right turn (for which we will compensate by subtracting (ext) angle from 360.

I've included my JS code here, as a gist: https://gist.github.com/3741816.

:D

Upvotes: 0

Svante
Svante

Reputation: 51501

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.

Upvotes: 4

G S
G S

Reputation: 36838

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

Upvotes: 2

MSN
MSN

Reputation: 54604

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.

Upvotes: 0

David Koelle
David Koelle

Reputation: 20824

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.

Upvotes: 0

Related Questions