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):

- Given two points p
_{1}& p_{2}in a co-ordinate plane, is the directed segment p_{0}p_{1}clockwise, counterclockwise or colinear to directed segment p_{0}p_{2}? Where p_{0}is the*origin*of the co-ordinate plane - Given two directed segments p
_{0}p_{1}and p_{0}p_{2}, is p_{0}p_{1}clockwise, counterclockwise or colinear to p_{0}p_{2}with respect to the common end point p_{0}? - Given two line segments p
_{0}p_{1}and p_{1}p_{2}, if we traverse from p_{0}to p_{2}, did we make a left, right or no turn at p_{1}? - Do line segments p
_{1}p_{2}and p_{3}p_{4}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!).

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** p_{1} X p_{2} is defined as the determinant of the matrix comprising of x and y values of the points.

If the **cross product **is positive then p_{1} is clockwise to p_{2}. A boundary condition occurs if the cross product is **0**. In that case p_{1} and p_{2} 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})>1If the angle θ_{2}is greater than θ_{1}then we have proved that p_{1}is clockwise to p_{2}

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 p_{0}p_{1} and p_{0}p_{2}, is p_{0}p_{1} clockwise, counterclockwise or colinear to p_{0}p_{2} with respect to the common end point p_{0} we just translate the axis to use p_{0} as the origin and use the cross product as above.

// To translate the origin to the common end point p_{0}//We let p_{1}' (p prime) be the point where x_{1}' =x_{1}- x_{0}and y_{1}' =y_{1}- y_{0}//We do the above for p_{2}and calculate its prime: p_{2}' x_{2}' =x_{2}- x_{0}and y_{2}' =y_{2}- y_{0}//Then we calculate the cross product of p_{1}' x p_{2}'If it is positive then the directed segment p_{0}p_{1}is clockwise to directed segment p_{0}p_{2}

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