For the convex hull algorithm we have to be able to test whether a point r lies

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 p = (px, py), q = (qx,qy), and r = (rx,ry).

a) Show that the sign of the determinant

1 pxpy

D= 1qxqy

1 rxry

determines whether r lies left or right of the line.

b) Show that |D| in fact is twice the area of the triangle determined by p, q, and r.

c) Why is this an attractive way to implement the basic test in algorithm CONVEXHULL? Give an argument for both integer and floating point coordinates.

Question From: Computational Geometry Algorithms and Applications, Page 15, Exercise 1.4

Explanation / Answer

1. According to the given points,

We can use the following formula for (PQ,PR) vector points where R(RX, RY) is the point whose position we have to find out. If result is 0, its on the line, +1 for one side, -1 on another side.

Position= sign(( Q.RX - P.RX) * (RY - PRY) - (Q.RY -P.RY) * (RX- P.RX)

After calculating the formula above , we get the result 0, so the point R is on the line.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects