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)

P.S. Sorry for my bad English and many thanks in advance!

  • 1
    $\begingroup$ 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)? $\endgroup$ – user2468 Feb 25 '12 at 20:30
  • $\begingroup$ You beat me to it @JD $\endgroup$ – user21436 Feb 25 '12 at 20:31
  • $\begingroup$ 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. $\endgroup$ – user2468 Feb 25 '12 at 20:35
  • $\begingroup$ @J.D. Im working in 2D in Cartesian coordinate system. Segments are represeted by 2 end points. $\endgroup$ – c0f33.alex Feb 25 '12 at 20:37
  • $\begingroup$ Computational Geometry in C by Joseph O'Rourke link page 30 describes the segment-segment intersection. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Yevgeny Simkin Mar 10 '12 at 4:27
  • $\begingroup$ $\max(p_{1x},p_{2x})$ is the maximal number among $p_{1x}$ and $p_{2x}$ $\endgroup$ – Norbert Mar 10 '12 at 7:01
  • $\begingroup$ 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$? $\endgroup$ – Sal Oct 1 '12 at 18:49
  • $\begingroup$ Oh this is a long story. I suggest you to read about this in Cormen's Introduction to algorithms 2nd edition Chapter 33 $\endgroup$ – Norbert Oct 1 '12 at 19:41

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.