CODEWITHSUNDEEP
mathgeometry
am_karthick
am_karthick

Reputation: 110

How to find the orientation of three points in a two dimensional space given coordinates of those points?

Actually I found this formula, but I dont know how it works.

Let p,q and r be the three points,

k=(q.y - p.y)*(r.x - q.x)-(q.x - p.x) * (r.y - q.y);

if(k==0): They are all colinear
if(k>0) : They are all clockwise
if(k<0) : They are counter clockwise

I will be pleased if someone explains how it works.

Upvotes: 8

Views: 12964

Answers (3)

dmytroy
dmytroy

Reputation: 2397

Let's have three points:

statement1

Consider that we will traverse them in order P -> Q -> R. We must find if our traversal is clockwise, counterclockwise or if all three points are on the same line.

It is well known fact that cross product of vectors can be used to calculate their orientation in 3D space (https://math.stackexchange.com/questions/285346/why-does-cross-product-tell-us-about-clockwise-or-anti-clockwise-rotation). We can use this property to calculate traversal in 2D space by extending our points and corresponding vectors to 3D case. So, let's define vectors that correspond to chosen above direction and extend them to 3D case:

Then we calculate cross product of these vectors:

Depending on the value of Z-coordinate, original points were traversed counter-clockwise (if it is negative), clockwise (if it is positive) or they are on the same line (if value is 0).

You can also recall right-hand rule (https://en.wikipedia.org/wiki/Right-hand_rule#Cross_products) that is usually taught in elementary school during Physics course to determine vectors orientation.

Let's check!

Test case #1: Consider that we have points P = (0, 0), Q = (1, 0), R = (1, 1). Draw them on piece of paper draw arrows P->Q and Q->R. You will see that we traverse these points counter-clockwise.

Substituting into equation from above, we have:

((0 - 0) * (1 - 1) - (1 - 0) * (1 - 0)) = -2 < 0,

so the points are oriented counter-clockwise.

Test case #2: Let's test with P = (0, 0), Q = (1, 0), R = (1, -1). Obviously, we traverse these points clockwise.

Substituting into equation from above, we have:

((0 - 0) * (1 - 1) - (1 - 0) * (-1 - 0)) = 2 > 0,

so the points are oriented clockwise.

Test case #3: Finally, let's test with P = (0, 0), Q = (1, 0), R = (2, 0). Points are on the same line y = 0.

Substituting into equation from above, we have:

((0 - 0) * (2 - 1) - (1 - 0) * (0 - 0)) = 0 == 0,

so the points are on the same line.

Hope this helps!

Upvotes: 8

asif naeem
asif naeem

Reputation: 1

This is found from the angle between two straight lines. (m1-m2)/1+m1*m2. Let a,b,c,d four points and and we want to know c and d are on same side of ab line or on opposite side. If the angle between ab, ac and angle between ab,ad are of opposite signs then they are on opposite side otherwise they are on same side. Using the above equation we can reach at the formula you found.

Upvotes: 0

MBo
MBo

Reputation: 80232

This formula is used to calculate cross product of vectors q-p and q-r. You can see in Geometric Meaning section that cross product value C = A x B = |A|*|B|*Sin(Theta), where Theta is angle between these vectors (point-to-point directions). Sin(Theta) = 0 for parallel vectors, positive when Theta < 180, negative otherwise.

Example:

clockwise triplet ABC: cross product of AB and AC vectors is >0

anticlockwise triplet ACD: cross product of AC and AD is negative.

enter image description here

Upvotes: 15

Related Questions