Algorithms in Computational Geometry – Part 2

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 p0p1 and p1p2, if we traverse from p0 to p2, did we make a left, right or no turn at p1?
  • Do line segments p1p2 and p3p4 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 p0p1 and p1p2 we simply check whether the directed segment p0p2 is clockwise or counterclockwise relative to directed segment p0p1. This is similar to the solution to question 2 in Part 1. If the cross product is negative, then p0p2 is counterclockwise to p0p1. Hence we should turn left when we reach p1 to reach p2 while traversing p0, p1 and p2. 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

Consecutive Segments Cross Product

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 p1p2 straddles another line if p1 and p2 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!) di for each point of one segment w.r.t the end points of the other segment. For line segments p1p2 and p3p4 we will get d1, d2, d3 and d4.

if none of the di are collinear (i.e. di !=0) we check if d1 and d2 and d3 and d4 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 di is collinear (boundary condition) and the corresponding pi is on the other line segment, the lines intersect.

Intersect cases

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
    }
}
Posted in Technology Tagged with: , , , ,
%d bloggers like this: