3
$\begingroup$

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
    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)?2012-02-25
  • 0
    You beat me to it @JD2012-02-25
  • 0
    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.2012-02-25
  • 0
    @J.D. Im working in 2D in Cartesian coordinate system. Segments are represeted by 2 end points.2012-02-25
  • 0
    *Computational Geometry in C by Joseph O'Rourke* [link](http://maven.smith.edu/~orourke/books/compgeom.html) page 30 describes the segment-segment intersection.2012-02-25

1 Answers 1

5

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.

  • 0
    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?2012-03-10
  • 0
    $\max(p_{1x},p_{2x})$ is the maximal number among $p_{1x}$ and $p_{2x}$2012-03-10
  • 0
    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$?2012-10-01
  • 0
    Oh this is a long story. I suggest you to read about this in Cormen's Introduction to algorithms 2nd edition Chapter 332012-10-01