4
$\begingroup$

I'm not a math guy, so I'm looking for concrete formulas without a lot of symbols or jargon, if possible.

I have two line segments, and need to determine if they intersect (true or false). The closest I've found is this: given coordinates of beginning and end of two intersecting line segments how do I find coordinates of their intersection? where the original poster provides a solution for the projected intersection, and from there I can compare the intersection to the x,y endpoints of one of the lines to see if it is within a line segment.

(a) is there an easier way to do this overall? I suspect I could just create a y=mx+b equation for both and solve for a common x,y value, but I'm working with screen coordinates in powerpoint and I'm not sure what to do about the b parameter since the lines are on different parts of the screen and I don't have a true 'zero' point. Also, coordinates are measured from the upper left corner, which just adds to my confusion when thinking about a traditional line formula.

(b) if I were to use the equation in the referenced post, is there an easier way to check the projected intersect against the lines, other than just comparing to see if the point is within the x and y range of one of the lines?

Thanks!

|cite|improve this question
$\endgroup$
  • $\begingroup$ I assume you're working in $\mathbb{R}^2$? $\endgroup$ – Zen Jun 3 '13 at 22:58
4
$\begingroup$

Here is another approach: somewhat similar to Zen's, but more complicated.

The segments $AB$ and $CD$ intersect if and only if both of the following are true:

  1. $A$ and $B$ lie on different sides of the line through $C$ and $D$
  2. $C$ and $D$ lie on different sides of the line through $A$ and $B$

These two conditions can be tested for using the notion of a scalar cross product (formulas below).

  1. is true if and only if the scalar cross products $\vec{CA}\times \vec{CD}$ and $\vec{CB}\times \vec{CD}$ have opposite signs.
  2. is true if and only if the scalar cross products $\vec{AC}\times \vec{AB}$ and $\vec{AD}\times \vec{AB}$ have opposite signs.

Formulas for scalar cross products (in which you will see a pattern): $$ \begin{split} \vec{CA}\times \vec{CD} &= (x_A-x_C)(y_D-y_C)-(y_A-y_C)(x_D-x_C) \\ \vec{CB}\times \vec{CD} &= (x_B-x_C)(y_D-y_C)-(y_B-y_C)(x_D-x_C) \\ \vec{AC}\times \vec{AB} &= (x_C-x_A)(y_B-y_A)-(y_C-y_A)(x_B-x_A) \\ \vec{AD}\times \vec{AB} &= (x_D-x_A)(y_B-y_A)-(y_D-y_A)(x_B-x_A) \\ \end{split} $$ Conclusion: the line segments intersect if and only if both of the following numbers are negative: $$\big((x_A-x_C)(y_D-y_C)-(y_A-y_C)(x_D-x_C)\big)\big((x_B-x_C)(y_D-y_C)-(y_B-y_C)(x_D-x_C)\big)$$ $$\big((x_C-x_A)(y_B-y_A)-(y_C-y_A)(x_B-x_A)\big) \big((x_D-x_A)(y_B-y_A)-(y_D-y_A)(x_B-x_A)\big)$$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I tried plugging this in to my code as an alternative, but I'm only getting two lines that don't cross (I'm sure I'm assigning numbers wrong somehow). I'll try to post some graphics tonight of what the output looks like, that may help with any troubleshooting. $\endgroup$ – Keith Jun 13 '13 at 18:25
  • $\begingroup$ @Keith Sorry I somehow missed your comment. Please give an example of line segments that get misdiagnosed. Plugging the ones you posted under Zen's answer gives two negative numbers. $\endgroup$ – ˈjuː.zɚ79365 Jun 25 '13 at 1:18
0
$\begingroup$

Given two lines in $\mathbb{R}^2$, they will intersect at a single point iff their slopes are not equal.

The problem is trickier if you only have segments to work with. Suppose you have a segment [AB] with endpoints $A(x_A,y_A)$ and $B(x_B,y_B)$, and a segment [CD] with endpoints $C(x_C,y_C)$ and $D(x_D,x_D)$ If the segments intersected, then A and B will be on opposite sides of the segment CD (one will be above and one will be below).

First check if there is any overlap (any points in common between) in the intervals $[x_A, x_B]$ and $[x_C,x_D]$ - if so, proceed, if not , they do not intersect.

Assume A and C are (intuitively speaking) are both on the right side of the graph and B and D are both on the left side. Compute $(y_A-y_C)(y_B-y_D)$ with A, C, B, D in that order. If the result is positive, they have not intersected. If it is negative, they have intersected.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Something is wrong here Zen because the $x$-values don't appear in your answer anywhere! $AB$ and $CD$ could be far away from each other in the $x$-dimension. $\endgroup$ – Douglas B. Staple Jun 3 '13 at 23:43
  • 1
    $\begingroup$ Thank you - I can't believe I missed that case! $\endgroup$ – Zen Jun 4 '13 at 0:04
  • $\begingroup$ @Zen thank you for your assistance. 100% of my lines will have some X-axis overlap, so I'm safe there. I've implemented the formula and while it eliminates most of my lines that have overlaps (I'm plotting them all), I am still getting one overlap line showing up. Any suggestions on the best method for me to troubleshoot why that line is getting by me? $\endgroup$ – Keith Jun 4 '13 at 23:10
  • $\begingroup$ @Keith Can you give the data for line segments that get incorrectly classified? $\endgroup$ – ˈjuː.zɚ79365 Jun 12 '13 at 13:35
  • $\begingroup$ Yes, in this case the "centerline" (against which all other line segments are compared) is (448,382) to (297, 353). v1>v2 so yA is the 382 number and yB is the 353 number. The line that crosses is (402, 336) to (317, 373). 336 is not greater than 373 so yC = 373 and yD = 336. (yA - yC) * (yB - yD) = 143 (all values rounded, my real numbers have fractional components) $\endgroup$ – Keith Jun 13 '13 at 17:54
-1
$\begingroup$

What do you consider jargon? Have you had at least some basic linear algebra?
If you have two infinitely long lines in 2-d,they always intersect unless they're parallel.
That is to say, some values of s and t exist that.
a+(b-a)t == c+(d-c)s
Where your line points are a & b and c & d as 2d vectors.
This is the same as saying:
a-c+(b-a)t == (d-c)s
Which is a simple set of two linear equations.
If both s and t are between 0 and 1, then that means the two intersect, if not, then the intersection is on the extension of the line.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ thank you. I had the basics many many years ago, and while I've got a logical mind, I'm trying to implement the equations in programming, and so the gap for me is resolving anything that isn't a direct equation. So for example, I can program to calculate t (or s), but calculating two unknown variables at the same time is something I haven't learned yet. $\endgroup$ – Keith Jun 4 '13 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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