Sai Panyam.NET

In Part 1 we discussed the base technique for determining relative orientation. We used that to answer the first two questions: To find relative orientation of two points and two directed segments with a common end point. In Part 2 we answer the next two questions:

• Given two line segments p₀p₁ and p₁p₂, if we traverse from p₀ to p₂, did we make a left, right or no turn at p₁?
• Do line segments p₁p₂ and p₃p₄ intersect?

We build on what we learned in Part 1, the cross product.

Download the demo application here

Determining whether consecutive segments turn left or right

Given two line segments p₀p₁ and p₁p₂ we simply check whether the directed segment p₀p₂ is clockwise or counterclockwise relative to directed segment p₀p₁. This is similar to the solution to question 2 in Part 1. If the cross product is negative, then p₀p₂ is counterclockwise to p₀p₁. Hence we should turn left when we reach p₁ to reach p₂ while traversing p₀, p₁ and p₂. If the cross product is 0 (boundary condition) then it means all the three points are collinear (on the same line). The image below shows the three possible scenarios

Using the cross product to determine how p0p1 and p1p2 turn at p1

Determining whether two line segments intersect

Two line segments intersect if and only if either or both of the following conditions are true:

• Each line segment straddles the other line segment.
• An end point of one line segment is on the other line segment

A line segment p₁p₂ straddles another line if p₁ and p₂ are on opposite sides of the line. A boundary condition occurs when one of the end points is on the other line.

Algorithm

Calculate the orientation (using cross product!) d_i for each point of one segment w.r.t the end points of the other segment. For line segments p₁p₂ and p₃p₄ we will get d₁, d₂, d₃ and d₄.

if none of the d_i are collinear (i.e. d_i !=0) we check if d₁ and d₂ and d₃ and d₄ have opposite orientations (if one is clockwise,other should be counterclockwise). If this condition is true then we know that the line segments straddle each other and hence intersect. If it is false we can straight away say they don’t intersect.

If any d_i is collinear (boundary condition) and the corresponding p_i is on the other line segment, the lines intersect.

Shows the different cases that we encounter visually

bool Intersects(p1, p2, p3, p4)
{
    d1 = CrossProduct (p1p3, p1p2)
    d2 = CrossProduct (p1p4, p1p2)
    d3 = CrossProduct (p3p1, p3p4)
    d4 = CrossProduct (p3p2, p3p4)

    if( ((d1 > 0 and d2<0) or (d2 > 0 and d1<0)) and  ((d3 > 0 and d4<0) or (d4 > 0 and d3<0)))
    {
      then return true
    }
    else if (d1 = 0 and PointOnLine (p3, p4, p1))
    {
       then return true
    }
    else if (d2 = 0 and PointOnLine (p3, p4, p2))
    {
       then return true
    }
    else if (d3 = 0 and PointOnLine (p1, p2, p3))
    {
       then return true
    }
    else if (d4 = 0 and PointOnLine (p1, p2, p4))
    {
       then return true
    }
    else
    {
       return false
    }
}

bool PointOnLine (pi, pj, pk)
{
    if ( Min (xi, xj)<= xk <= Max (xi, xj) and Min (yi, yj)<= yk <= Max (yi, yj) )
    {
        return true
    }
    else
    {
        return false
    }
}

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 p₁ & p₂ in a co-ordinate plane, is the directed segment p₀p₁ clockwise, counterclockwise or collinear to directed segment p₀p₂? Where p₀ is the origin of the co-ordinate plane
2. Given two directed segments p₀p₁ and p₀p₂, is p₀p₁ clockwise, counterclockwise or collinear to p₀p₂ with respect to the common end point p₀?
3. Given two line segments p₀p₁ and p₁p₂, if we traverse from p₀ to p₂, did we make a left, right or no turn at p₁?
4. Do line segments p₁p₂ and p₃p₄ 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!).

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

Two vectors are collinear if they are pointing in the same or opposite direction. In the picture all vectors that lie along the diagonal will be collinear 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₁ X p₂ is defined as the determinant of the matrix comprising of x and y values of the points.

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

If the cross product is positive then p₁ is clockwise to p₂. A boundary condition occurs if the cross product is 0. In that case p₁ and p₂ are collinear.

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 p₀p₁ and p₀p₂, is p₀p₁ clockwise, counterclockwise or collinear to p₀p₂ with respect to the common end point p₀ we just translate the axis to use p₀ 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.