How Do You Determine if a Line Segment Intersects a Square in 2D Geometry?

  • Context: Graduate 
  • Thread starter Thread starter eniven
  • Start date Start date
  • Tags Tags
    Programming
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
5 replies · 3K views
eniven
Messages
3
Reaction score
0
I am trying to determine whether or not any part of a line segment is located within a square box.

I have the coordinates of the line segment end points and the corners of the square box.

This problem is easy for the case where one or both end points are located in the box, but I don't know what to do when the line crosses the box but both end points are located outside the box.

This problem is in 2D.

Anyone have any thoughts? Thanks in advance.

Edited to add: This is not homework. I'm working on a PhD in a petroleum engineering related field. I am actually trying to determine the fractal dimension of fractures in rock (in 2D) and for this part I am using the box counting method. So, I'm trying to figure out if the line (the fracture) is located in the box.
 
Last edited:
Mathematics news on Phys.org
There is an equation that defines the line segment, right?

There are equations that define the four line segments that define the square, right?

If the line segent is partially inside the square, it must intersect at least one of the four line segments that make up the square, right?

If it intersects none of them, it doesn't cross the square.
 
I'm not sure if I got the question right, but if you're asking if any part of a line segment is in a box, then you should be able to connect the endpoints of the line and see if it crosses the sides of the box (if it does, then part of the line segment is in the box).
 
Thanks guys! I feel like a bit of a doofus for not thinking of that! :redface:
 
Another way to do it is this: Every straight line determines a specific inequality. That is, if the line is given by ax+ by+ c= 0 then every point on one side of the line satisfies ax+ by+ c> 0 and every point on the other side satisfies ax+ by+ c< 0. Given a single point inside the box, you can determine what inequalities every point inside the box must satisfy and use that to determine whether the endpoints of the line segment are inside the box or not. That should be simpler than solving equations to determine where or if the given line segment intersects a side.
 
HallsofIvy said:
Another way to do it is this: Every straight line determines a specific inequality. That is, if the line is given by ax+ by+ c= 0 then every point on one side of the line satisfies ax+ by+ c> 0 and every point on the other side satisfies ax+ by+ c< 0. Given a single point inside the box, you can determine what inequalities every point inside the box must satisfy and use that to determine whether the endpoints of the line segment are inside the box or not. That should be simpler than solving equations to determine where or if the given line segment intersects a side.

Hmm, that's clever, but what about the case where neither end point of the line are inside the square yet the line crosses the square?