1
$\begingroup$

I have two line segments $[(x_1, y_1),(x_2, y_2)] $ and $[(x_3, y_3),(x_4, y_4)] $ and I want to know if they intersect.

My current algorithm tries the following:

  • the line $[(x_1, y_1),(x_2, y_2)] $ is determined by $\boxed{f(x,y) = \frac{y - y_1}{x - x_1} - \frac{y_2 - y_1}{x_2 - x_1} = 0}$.
  • I reasoned that if $y = mx+b$ is my line, I want a point such that $y > mx+b$ and one such that $y < mx+b$.
  • I want to check if that $f(x,y)$ has opposite signs if I set it on $(x_3,y_3)$ and $(x_4, y_4)$. So the criterion I check right now is: $$ \frac{f(x_3,y_3)}{|f(x_3,y_3)|}\; \frac{f(x_4,y_4)}{|f(x_4,y_4)|} = -1 $$ Unfortunately in my visualization, I still see line segments intersecting.

Is there something wrong with my algorithm? What is a correct way to check that two line segments intersect?

$\endgroup$
  • 1
    $\begingroup$ The correct way appears in textbooks and online lecture notes. For example, see these lecture notes: compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/… $\endgroup$ – Yuval Filmus Jun 24 '14 at 15:11
  • $\begingroup$ @YuvalFilmus yes but which textbook and which online lecture notes? does this go by a standard name in computer science? $$ . $$ The next question I was going to ask is what happens in the limit of large number of segments. OK, I found one here stackoverflow.com/questions/563198/… $\endgroup$ – john mangual Jun 24 '14 at 15:18
  • 2
    $\begingroup$ btw, the problem with your approach is that you're replacing one of your line segments with the (infinite) line it lies on; even if the other line segment intersects this line, that doesn't imply that it intersects the original line segment. $\endgroup$ – Aky Jun 25 '14 at 12:47
  • $\begingroup$ Are you sure the point $(x_1, y_1)$ is on your first line as defined in the first box? It sorts of feel uncertain, if you can see what I mean. I am also uncomfortable with vertical lines, parallel to the $y$ axis. On the other hand, it is a great technique for building apparent paradoxes. There are undoubtedly many nices ways of solving this, but you should first make sure that all you write is meaningful, or identify cases when it is not. The appropriate cute answer, if any, may depend on what you are currently learning. The pedestrian answer: solve the equation for $x$ and check bounds. $\endgroup$ – babou Jun 25 '14 at 15:36
  • $\begingroup$ @babou In my cases, the 4 points are random and uncorrelated so degenerate cases occur with probability zero. $\endgroup$ – john mangual Jun 25 '14 at 15:43
4
$\begingroup$

You need to know about the orientation test.

For any three points, compute the determinant

$$\Delta_{123}=\left| \begin{array}{ccc} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{array} \right|.$$

This is twice the signed area of the triangle $123$. When it is $0$, it tells you that the three points are aligned. Otherwise, it tells you on what side of the line joining two points the third lies.

In your case, there is an intersection if $1$ and $2$ are on either sides of $34$, while $3$ and $4$ are on either sides of $12$: $$(\Delta_{134}>0)\ne(\Delta_{234}>0)\land(\Delta_{123}>0)\ne(\Delta_{124}>0).$$

It is up to you to decide what to do in cases of perfect alignments.

As an extra goodie, the $\Delta$'s can be used to compute the coordinates of the intersection. (Let $P$ be the intersection point, interpolated along the segment $P_1P_2$: $P=(1-t).P_1+t.P_2$; it is easy to show that $(1-t)\Delta_{134}+t\Delta_{234}=0$ and to find the value of $t$.)

$\endgroup$
  • $\begingroup$ Nice technique. But I did not understand the last paragraph. possibly a problem of notation. $\endgroup$ – babou Jun 26 '14 at 23:09
3
$\begingroup$

The vector equation:

$$P_1 + \alpha * (P_2 - P_1) = P_3 + \beta * (P_4 - P_3)$$

where $P_1 = (x_1, y_1)$ etc., should have a solution in the unit square:

$$0 \le \alpha \le 1, 0 \le \beta \le 1$$

then these two segments $(P_1, P_2)$ and $(P_3, P_4)$ do intersect. However, there are many corner cases here (for example, $P_1 = P_2$ etc.). Also, you can get wrong answers because of the limited precision of your data representation in computer.

$\endgroup$

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.