Question

For the convex hull algorithm we have to be able to test whether a point r lies left or right of the directed line through two points p and q. Let = (px, Py), q , and r-(Tx,rv). a. Show that the sign of the determinant 1 rx iy determines whether r lies left or right of the line.

Answer 1

We make use of the cross-product of two vectors. Let there be two points A = (ax , ay) and B = (bx , by). Then we draw two lines from origin O (0,0) to point A and B respectively to get two vectors. Let us define the cross-product A X B = ax*by - ay*bx.

If A X B is positive then origin O (0,0) lies to the left of directed line passing through A and B (that is angle AOB is in counter-clockwise direction) while if A X B is negative then origin O (0,0) lies to the right of directed line passing through A and B ( that is angle AOB is in clockwise direction )

Now, to test whether point r lies to the left or right of the directed line through two points p and q , we do the following :-

We find the cross product (P-R) and (Q-R) where P-R = (px-rx , py-qy) and Q - R = ( qx-rx , qy-ry )

If (P-R) x (Q-R) is positive then r lies to left of the directed line passing through p and q else r lies to the right of the directed line passing through p and q.

(P-R) X (Q-R) = (px - rx) * (qy-ry) - (py-ry)*(qx-rx)

= px*(qy - ry) - rx*qy + rx*ry - py(qx - rx) + ry*qx - ry*rx

= px*(qy - ry) - rx*qy - py(qx - rx) + ry*qx

Now, we expand the Determinant D = ry*qx - rx*qy - px*(ry - qy) + py*(rx - qx)

Rearranging the terms , we get D = - rx*qy + ry*qx + px*(qy - ry) - py*(qx - rx)

We notice that D and (P-R) X (Q-R) are basically the same. Hence, if D is positive then r lies to the left of directed line passing through p and q else if D is negative the r lies to the right of the directed line passing through p and q.