# determine if 2 line segments are intersecting

currently I write a program where finding out whether 2 line segments intersect is an essential part of the algorithm. Could anyone tell me if there's a way to determine if two segments are intersecting (i.e. whether the intersection point of 2 lines lies on each line between the points of each segment) without computing the exact coordinates of the intersection point. (computing it would cause unnecessary overhead on runtime)

• What space are working over? $\mathbb{R}^2$? Is it 2D or 3D? What is your coordinate system? Cartesian? How do you represent your segments? By two end points or (unit vector direction + base point + parameter)? – user2468 Feb 25 '12 at 20:30
• You beat me to it @JD – user21436 Feb 25 '12 at 20:31
• There are two widely used textbooks on computational geometry: Computational Geometry by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, and Computational Geometry in C by Joseph O'Rourke. There is also the book series Graphics Gems. Check them out. I'm 100% sure you will find simple and efficient routines for segment-segment intersection. It boils down to checking the orientation (via signed area calculations) of points. – user2468 Feb 25 '12 at 20:35
• @J.D. Im working in 2D in Cartesian coordinate system. Segments are represeted by 2 end points. – c0f33.alex Feb 25 '12 at 20:37
• Computational Geometry in C by Joseph O'Rourke link page 30 describes the segment-segment intersection. – user2468 Feb 25 '12 at 20:47

Two segments $p_1p_2$ and $p_3p_4$ are intersect iff

1) Their rectangles intersects, which can be written as

$\max(p_{1x},p_{2x})\geq \min(p_{3x},p_{4x})$ and

$\max(p_{3x},p_{4x})\geq \min(p_{1x},p_{2x})$ and

$\max(p_{1y},p_{2y})\geq \min(p_{3y},p_{4y})$ and

$\max(p_{3y},p_{4y})\geq \min(p_{1y},p_{2y})$.

2) $\langle[p_3-p_1,p_2-p_1],[p_4-p_1,p_2-p_1]\rangle\leq 0$

3) $\langle[p_1-p_3,p_4-p_3],[p_2-p_3,p_4-p_3]\rangle\leq 0$

see Introduction to Algorithms T. Cormen section 35 Computational geometry.

• sorry, I realize this probably a really stupid question, but what do you mean by max(p1x,p2x)? Am I finding the greater of the two values? (and the lesser for min)? or is there some other computation going on there? – Dr.Dredel Mar 10 '12 at 4:27
• $\max(p_{1x},p_{2x})$ is the maximal number among $p_{1x}$ and $p_{2x}$ – Norbert Mar 10 '12 at 7:01
• Yet another dumb question on my part, but what does it mean when $\langle[p_1-p_3,p_4-p_3],[p_2-p_3,p_4-p_3]\rangle\leq 0$ and $\langle[p_1-p_3,p_4-p_3],[p_2-p_3,p_4-p_3]\rangle\leq 0$? – Sal Oct 1 '12 at 18:49
• Oh this is a long story. I suggest you to read about this in Cormen's Introduction to algorithms 2nd edition Chapter 33 – Norbert Oct 1 '12 at 19:41