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!

  • 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
    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