Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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)? –  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

1 Answer 1

up vote 2 down vote accepted

Two segments $p_1p_2$ and $p_3p_4$ are intersects 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.

share|improve this answer
    
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}$ –  no identity 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$? –  skizeey 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 –  no identity Oct 1 '12 at 19:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.