0
$\begingroup$

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.

4 Answers 4

1

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)$.

0

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.

0

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

  • 3
    The question is about line _segments_.2012-02-19
  • 0
    I don't see how that changes much2012-02-23
  • 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.2012-02-24
  • 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.2012-06-25
0

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.