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.

To find if two line segments intersect I am this code

The problem is this code:

// if abs(angle)==1 then the lines are parallell,  
// so no intersection is possible  
if(abs(deg)==1) return null;

At that point we know that the lines are parallel, but we don't know if they overlap and where.

If I have a line segment 5,5 to 10,10 and another line segment 7,7 to 12,12 then I'd like to determine that the line segment 7,7 to 10,10 is the overlap.

share|improve this question

4 Answers 4

One way would be to determine the coordinate of the intersection of the line which supports the segment with the $x$-axis, for example. If the two endpoints of the segment are $(a,b)$ and $(c,d)$, then $(x,0)$ is colinear to these if and only if

$$ \frac{x-a}{c-a}=\frac{0-b}{d-b} $$

From here, it is easy to get $x$ as a simple function of $a,b,c,d$. If you have two parallel segments, you can tell if they have the same support line if you get the same $x$ in the formula above.

If the two segments are on the same support line, then you can say if they intersect by looking at their projections on the $x$-axis.

For example, in your case, the segments are obvious on the same line $(x=0)$. And they intersect, because $[5,10]$ and $[7,12]$ intersect.

share|improve this answer

If two lines are parallel they will either overlap nowhere or everywhere

share|improve this answer
3  
The question is about line segments. –  alex.jordan Feb 19 '12 at 21:22
    
I don't see how that changes much –  Awk34 Feb 23 '12 at 23:58
1  
Line segments that are parallel might partially overlap. On the $x$-axis, consider the intervals $[0,2]$ and $[1,3]$. They neither overlap nowhere nor everywhere. –  alex.jordan Feb 24 '12 at 0:38
1  
I thought the same when I looked at it...but this is not about intersections of two parallel lines. It is about finding where two bits of the same line overlap. –  fretty Jun 25 '12 at 10:41

This method will work for all lines in any dimension.

Parametrize your line using the vector equation of a line:

$\textbf{r} = t\textbf{s} + \textbf{c}$

Then the $t$ values of the two line segments (assuming they do intersect) will correspond to certain intervals. The overlap will correspond to the $t$ values of the intersection of these intervals.

For your example the line is parametrized by:

$\textbf{r} = t\binom{1}{1}$

The first line segment corresponds to $t$ values in the interval $[5,10]$ and the second to $[7,12]$. Thus the overlap corresponds to points with $t$ value in $[7,10]$, i.e. the line segment joining $(7,7)$ to $(10,10)$.

share|improve this answer

I assume everything takes place in ${\mathbb R}^2$. Let the two segments be $\sigma_1:=[{\bf a},{\bf b}]$, and $\sigma_2:=[{\bf p},{\bf q}]$ and denote by $g_i$ the line spanned by $\sigma_i$. The common points of $g_1$ and $g_2$ are obtained by solving the system $$(1-s){\bf a}+ s{\bf b}=(1-t) {\bf p}+ t{\bf q}\ ,$$ resp. $$\eqalign{(b_1-a_1)s+ (q_1-p_1)t&=p_1-a_1\cr (b_2-a_2)s+ (q_2-p_2)t&=p_2-a_2\cr}\qquad(*)$$ for $s$ and $t$.

If the determinant $$\Delta:=({\bf b}-{\bf a})\wedge({\bf q}-{\bf p})=(b_1-a_1)(q_2-p_2)-(b_2-a_2)(q_1-p_1)$$ is nonzero then $g_1$ and $g_2$ intersect in exactly one point, and the system $(*)$ has exactly one solution $(s_*,t_*)$. If both $s_*$ and $t_*$ are in the interval $[0,1]$ then the point $${\bf z}:=(1-s_*){\bf a}+ s_*{\bf b}=(1-t_*) {\bf p}+ t_*{\bf q}$$ is the unique point common to the two segments $\sigma_1$ and $\sigma_2$.

If $\Delta=0$ then the two lines $g_1$ and $g_2$ are disjointly parallel or coincide. This means that the system $(*)$ has no solutions or infinitely many solutions $(s,t)$. The truth will come to the fore using Gaussian elimination. The second (more interesting) case obtains when the second equation $(*)$ is in fact a multiple of the first equation.

At this point we know that in fact $g_1=g_2$, and we have to test whether a certain equation of the form $$\ell:\quad b s+ q t=p$$ has solutions $(s,t)\in[0,1]^2=:Q$. This involves intersecting $\ell$ with the square $Q$ which in itself is an interesting thing to program.

share|improve this answer

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.