Polygons

[w0rk4holic]

how do i find all the interior angles of a concave polygon? here is a java applet that does the same :-
http://www.mathopenref.com/polygoninteriorangles.html

thanks

[Banfa]

Interestingly if you had bothered to read the text of that page below the Java applet it tells you exactly how you can calculate the interior angle for a regular polygon and further it links boldly at the top of the page to a page about exterior angles too.

[w0rk4holic]

Interestingly if you had bothered to read the text of that page below the Java applet it tells you exactly how you can calculate the interior angle for a regular polygon

regular polygon is a convex polygon. How do i calculate the interior angles for irregular polygons i.e concave polygons. My bad did not define concave polygons: polygons that have atleast 1 interior angle > 180 are called concave polygons here is a picture:
http://www.korthalsaltes.com/gif1/convex-concave-polygon.gif
using the angle formula for 2 line segments will give an acute angle between 2 lines. How do i figure out weather the angle interior angle i want is acute , obtuse or above 180 degrees ???
here is another picture to help explain the problem :
http://img123.imageshack.us/img123/9346/interiorangles.jpg

thanks for the reply anyways

[Banfa]

Again from the website you have already linked to, the equations given still hold true for concave polygons.

You can't calculate the angles of an irregular polygon by definition since they are irregular they can be anything you want them to be. The only reason you can calculate the angles for a regular polygon is because you have the conditional restraint that they must all be the same.

For an irregular polygon with N sides if you know N-1 of the angles you can calculate the Nth angle. The forumla for that is on the website you have already linked to.

[w0rk4holic]

thanks for the post
how do i compute the other (N-1) angles then? the formula on the site holds if i know the n-1 angles .. what if there is more than 1 reflex angle in the concave polygon? (i know the all the angles sum up to a particular number but if there are multiple reflex angles its like solving 1 equation with multiple unknowns :S)
i am using the cos inverse of the vector dot product of the 2 lines (connected sides of the polygon) which returns the correct angle between them, the problem is i cannot figure out weather the angle is inside the polygon or outside?

maybe i am being stupid but i just cant write the code to do this

thanks for the reply!

[Banfa]

It's not like solving 1 equation with multiple unknowns it is solving 1 equation with multiple unknowns.

i am using the cos inverse of the vector dot product of the 2 lines (connected sides of the polygon) which returns the correct angle between them, the problem is i cannot figure out weather the angle is inside the polygon or outside?

However this sounds like you have some additional constraints that you have not shared. What are these 2 vectors? What 2 lines, a polygon generally has more than 2 lines.

is there more to this problem than you have stated?

[w0rk4holic]

thanks for the post again!
i figured out a solution to the problem:

the problem :- find all interior angles of any polygon be it concave or convex

input :- a set of points representing the polygon with clockwise or counter clockwise winding

output :- all the interior angles of the polygon (duh!)

solution :-
algorithm :-
n = number of points in the polygon.
for i = 0 to n do
j = (i+1)%n;
k = (i+2)%n;
v1 = vector {p.x - p[j].x , p.y - p[j].y};
v2 = vector {p[k].x - p[j].x , p[k].y - p[j].y}
angle = acos ( dot ( (normalize v1), (normalize v2)) );
if (cross (v1,v2) > 0) // if the winding is CCW compare with < 0
angle = 360 - angle

cross => cross product of vectors v1 and v2
dot => dot product of vectors v1 and v2
normalize => vector with same direction as v1 but length or magnitude of 1