4
$\begingroup$

I want to find the (maximum 2) intersect points between a segment (a line that is of finite length defined by a starting and an ending points) and a rectangle. Both of them are "floating" in 2-D space without being bounded to the center (0,0) or to any of the axes.

Is there an easier way to find the intersection points except for continuing all the lines to be infinite, find the intersection points between the lines of the rectangle and the line of the segment and then check if the points are on the perimeter of the rectangle?

The rectangle is defined by 4 points.

$\endgroup$
3
$\begingroup$

In the end, that is what you will have to do.

But if for example you expect an intersection to be rare, it may be worth while to first make a simpler test if there is an intersection at all. If the line segment is given by endpoints $(x_1, y_1)$ and $(x_2, y_2)$ then a point $(x,y)$ is on the same straight line iff $u\cdot x+v\cdot y+w=0$ with $u:=y_2-y_1$, $v:=x_1-x_2$, $w:=x_1 y_2-x_2y_1$. Moreover, the two half planes defined by the line can be distinguished by whether $u\cdot x+v\cdot y+w>0$ or $u\cdot x+v\cdot y+w<0$. Thus: plug the four vertices of your rectangle into the exppression $u\cdot x+v\cdot y+w$. If all four vertices produce a negative result (or all foru produce a positive result), then trivially there is no intersection at all.

$\endgroup$
  • $\begingroup$ And how can I find the coordinates of intersection points? $\endgroup$ – kolobok Sep 9 '14 at 14:45
  • $\begingroup$ Can we make another assumption if the rectangle is axis aligned (its edges are vertical and horizontal)? $\endgroup$ – arthur.sw Sep 16 '15 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.