How to check if line segment intersects a rectangle?

algorithm language-agnostic geometry computational-geometry
omega picture omega · Apr 25, 2013 · Viewed 44.7k times · Source

If you have 2 points, (x1, y1) and (x2, y2), which represent two opposite corners of a rectangle, and 2 other points, (x3,y3) and (x4,y4), which represent 2 endpoints of a line segment, how can you check if the line segment intersects the rectangle?

(The line segment is just the segment contained between the given endpoints. It is not an infinite length line defined by those two points.)

Answer

templatetypedef picture templatetypedef · Apr 25, 2013

One very simple option would be to use a standard algorithm for checking whether two line segments intersect to check whether the line segments intersects any of the four line segments that make up the corners of the box. It's computationally very efficient to check if two line segments intersect, so I would expect that this could run very quickly.

Hope this helps!

Related questions

Choose the closest k points from given n points

You are given a set U of n points on the plane and you can compute distance between any pair of points in constant time. Choose a subset of U called C such that C has exactly k points in …

Read More
Equation for testing if a point is inside a circle

If you have a circle with center (center_x, center_y) and radius radius, how do you test if a given point with coordinates (x, y) is inside the circle?

Read More
How to find two most distant points?

This is a question that I was asked on a job interview some time ago. And I still can't figure out sensible answer. Question is: you are given set of points (x,y). Find 2 most distant points. Distant from each …

Read More