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

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