Algorithms in Computational Geometry – Part 1

Computational Geometry (CG) deals with algorithms for solving geometric problems. It is used in computer graphics, robotics, computer aided design,statistics among others. A typical CG problem takes as input a set of geometric objects like a set of points, a set of line segments etc. The output is most commonly finding certain attributes of the geometric objects. For e.g. we are interested in answering the following questions in two dimensions (in a plane):

  1. Given two points p1 & p2 in a co-ordinate plane, is the directed segment p0p1 clockwise, counterclockwise or colinear to directed segment p0p2? Where p0 is the origin of the co-ordinate plane
  2. Given two directed segments p0p1 and p0p2, is p0p1 clockwise, counterclockwise or colinear to p0p2 with respect to the common end point p0?
  3. Given two line segments p0p1 and p1p2, if we traverse from p0 to p2, did we make a left, right or no turn at p1?
  4. Do line segments p1p2 and p3p4 intersect?

Download the demo application here

Before we proceed any further a few definitions. Clockwise and Counterclockwise are intuitively easy to understand. They have the usual colloquial meaning. There is one thing to note though. A co-ordinate plane is not a watch face! Here we are determining the relative orientations of one segment w.r.t the other. Instead of trying to explain it in words, I will show you a picture (should replace a thousand words!).

Orientation

The darkly shaded orientation region contains vectors counterclockwise relative to p. The lightly shaded region contains vectors clockwise to p

Two vectors are colinear if they are pointing in the same or opposite direction. In the picture all vectors that lie along the diagonal will be colinear to p.

With definitions out of the way, let us proceed to answer the initial queries that we posed. A brute force method of computing whether two line segments intersect, would be to find the line equations of the form y=mx + c where m is the slope and c the y-intercept and then compute the point of intersection, and verify whether this point lies on both lines. This involves a lot of expensive computational resources. Further this involves division which is sensitive to round-off errors depending upon the precision of the division operation. For e.g. almost parallel line segments will give incorrect results.

The algorithms given here will only use additions, multiplications, subtractions and comparisons ! No trigonometry also !
We do this by computing the cross product. This is a fundamental technique that is at the base of most CG algorithms. Let me say that again. Cross Product is a most fundamental and important technique for solving CG problems. A cross product p1 X p2 is defined as the determinant of the matrix comprising of x and y values of the points.

Determinant

Determinant of the above matrix will be equal to (x1y2-x2y1)

If the cross product is positive then p1 is clockwise to p2. A boundary condition occurs if the cross product is 0. In that case p1 and p2 are colinear.

Proof: We use trigonometric function tan on the angle formed by the point (x,y), origin (0,0) and (x,0) for both the points. If the ratio of one tangent to other determines orientation depending upon whether the value is greater than 1 or not.

//Clockwise:
x1y2-x2y1>0

//So
x1y2>x2y1

//alternatively
(x1y2)/(x2y1)>1

//rearranging the terms
(y2/x2)/(y1/x1)>1

//Notice that tan θ is the ratio of opposite side by adjacent side
//in a right-angled triangle
//so the numerator of the above fraction is tan θ2 and
//denominator tan θ1

(tan θ2)/(tan θ1)>1

If the angle θ2 is greater than θ1
then we have proved that p1 is clockwise to p2

The above technique of using cross product makes for an easy and efficient way to answer Question 1.
To answer Question 2 just involves an extra pre-processing step before doing the cross product. To determine whether two directed segments p0p1 and p0p2, is p0p1 clockwise, counterclockwise or colinear to p0p2 with respect to the common end point p0 we just translate the axis to use p0 as the origin and use the cross product as above.

// To translate the origin to the common end point p0
//We let p1' (p prime) be the point where 

x1' =x1 - x0 and
y1' =y1 - y0

//We do the above for  p2 and calculate its prime: p2' 

x2' =x2 - x0 and
y2' =y2 - y0

//Then we calculate the cross product of p1' x p2' 

If it is positive then the directed segment p0p1 is clockwise to
directed segment p0p2

In Part 2 we will answer questions 3 & 4 using the techniques and principles learned here.

Posted in Technology Tagged with: , , , ,
%d bloggers like this: