🔒 Locked

Computational Geometry Problem

Started by PhilVaz Oct 17, 2003 at 11:15 PM 4 replies 1.1k views

Original Post

Oct 17, 2003 at 11:15 PM

I need a function to compute the angle formed by 3 points in 2D space. How does one calculate the interior angles of a simple polygon using only the X,Y vertices of the polygon...for example:

The vertices are 0,1,2,3,4,5,6 and each have an X,Y coordinate. Is there a way to calculate (for example) the interior angle at vertex 0 (a convex) knowing the X,Y coordinates of adjacent vertices 1, 0, and 6 ?

Same deal, how would I calculate (for example) the interior angle at vertex 5 (a reflex) knowing the X,Y coordinates of adjacent vertices 4, 5, and 6 ? For a short report of what this is for, you can check Implementation of the Hertel-Mehlhorn Algorithm I actually need all the interior angles of a simple polygon in order to remove "inessential diagonals" created during a triangulation. Its a classic "Computational Geometry" problem, but not sure how to calculate the angles. VazGames.com Phil Porvaznik

Atheist

Oct 17, 2003 at 11:31 PM

use the dot product. It gives you x*y = cos(a)*|x|*|y| where x and y are vectors between your points and a is the angle you´re looking for.
Only problem you get by that is that your angle will always be <= 180°, so you´ll have tom do case branching if your angle is above that. And more importantly you´ll have to identify the cases where this is true (not nessecary in your 1st example). To check this you can take the cross product of two (index-wise) oriented vectors and check the sign of the (imaginized) z-coordinate.

PhilVaz

Oct 18, 2003 at 2:13 AM

<< It gives you x*y = cos(a)*|x|*|y| >>

Thanks, I'm confused which x and y you mean though. Do I need to use all three x and y, for example if the vertex where I want the angle is at x0,y0 I have the three vertices x1,y1 and x0,y0 and x2,y2 with 1 and 2 being the adjacent ones. Still not sure which x and y I'm plugging in. I am taking Linear Systems at the moment so some of this makes sense.

Is there another way to do this using ATAN2 function?

Or how would I write a function for the angle in terms of x1,y1,x0,y0,x2,y2 ?

Phil P

[edited by - PhilVaz on October 18, 2003 3:14:37 AM]

oliii

Oct 18, 2003 at 6:16 AM

Vector E = V1 - V0;
Vector F = V6 - V0;

float El = E.Magnitude();
float Fl = F.Magnitude();
float inv_l = 1.0f / (El * Fl);

float cos_angle = E.Dot(F) * inv_l;

float angle = acos(cos_angle);

float sign = E.x * F.y - E.y * F.x;

if (sign < 0.0f)
angle *= -1.0f;

PhilVaz

Oct 18, 2003 at 7:36 AM

Thanks Oliii. I''ll try this....seems familiar. I should really read my Linear Systems book.

Phil P

oliii

Oct 18, 2003 at 4:21 PM

untested though

You really ought to test it with known angles, like two vectors at 45 degrees, 90 degrees, 135 degrees, 180 degrees, ect... and see if the results correspond.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.