Intersection

Standard

 

Given two line segment (defined by four points), find their intersection if there is any?

Here, we can use our knowledge of pre-calculus to solve this problem. First, let us transform the input to a linear equation of the form that we all love y = m x + b. We can do this by finding the slope m first, then plugging in a point and the computed m and solve for the y-intercept b. We do this for both line segments and then equate them together to find the intersection point (x,y). Here is my code to solve this problem:

def intersection(x0s, y0s, x0f, y0f, x1s, y1s, x1f, y1f)
  # compute slopes
  epsilon = 0.0
  if y0f - y0s == 0
    epsilon = 0.00001
  end
  m0 = (x0f - x0s) / (y0f - y0s + epsilon)
  epsilon = 0.0
  if y0f - y0s == 0
    epsilon = 0.00001
  end
  m1 = (x1f - x1s) / (y1f - y1s + epsilon)

  # return nil if lines are parallel
  return [nil, nil] if m0 == m1

  # compute offset
  b0 = y0s - (m0 * x0s)
  b1 = y1s - (m1 * x1s)

  # compute intersection point
  x = (b1 - b0) / (m0 - m1)
  y = m0 * x + b0

  # check if point is sensible
  test_x = x < [x0s, x0f, x1s, x1f].max &&  x > [x0s, x0f, x1s, x1f].min
  test_y = y < [y0s, y0f, y1s, y1f].max &&  y > [y0s, y0f, y1s, y1f].min
  unless test_x && test_y
    return [nil, nil]
  end

  [x, y]
end

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s