Introduction

To figure this out, I created a little program that would roll line segments out behind mouse movement, putting a timer on the first node so it would disappear and make the line look as if it was trying to keep up with the mouse (you'll need to see the demo to understand what I mean here!). Each segment would need to be checked to see if there are any overlaps with other segments. If there are overlaps, then the points would be truncated and the resulting circle/ellipse/polygon (depending on overlap) would be drawn in its final state.

Here are a couple of screenies to give you an idea of what I'm talking about:

...this is just a line, consisting of segments, following the mouse.

...now the two lines are about to intersect.

...and here they finally do intersect, thus removing all excess segment pieces and making the first and last segment share a start/end point at the intersection. (Note that these screenies weren't taken in succession, so they aren't an actual step visual, but the representation is all I'm trying to get across here.)

Also, in order to check the process of things, I made a little step-by-step function so I could watch each segment, it's values, and whether or not there was a collision visually AND algorithmically.

...this shows the "algorithm debugger" in action.

The Math Involved

Here is an example of two crossing lines:

Here I'm just showing the starting and ending points of each line so you can see where we'll be going with this. X1 = Start X of Line 1. V2 = Ending Y of Line 2. Remember, though, that what you call the variables is irrelevant as long as you're consistent. Most people will use X1,X2,Y1,Y2 for the first line and U1,U2,V1,V2 for the second line when writing equations.

Here's is the intersect point:

I know, it's not exactly brain surgery...yet! :)

Let's take this whole process step-by-step so you can see how it works.

STEP 1: Finding the slope and the y-intercept of each line.

This is part of what most of you already know as the "Slope-Intercept" equation, which y = mx + b. Well, we already know the y and x values of each point, but what about the m (slope) and b (y-intercept)? That we'll need to figure out in order to determine intersection.

This image shows both our Lines with values that I just made up for the respective starting and ending X,Y/U,V coordinates. Let's start with line 1 (yellow).

In order to determine the m (slope) of this line, we use the following equation:

m = (y2-y1)/(x2-x1)

Plugging in our known values (from the image), we have this:

m = (319 - 303)/(427 - 412)
m = 16/15
m = 1.06667

And to find the b (y-intercept) value for this line, we'll use this equation:

b = y1 - m * x1
b = 303 - (1.06667 * 412)
b = 303 - 439.192
b = -136.468

For line 2, we do the same thing:

m = (322 - 298)/(408-431)
m = 24/-23
m = -1.04348

b = 298 - (-1.04348 * 431)

b = 298 - (-449.533)

b = 747.739

To make things a little easier, I'll name the m and b values according to their respective lines. So, now we have:

m1 = 1.06667
b1 = -136.468

...and..

m2 = -1.04348
b2 = 747.739

What's the code look like for this? Well, it's a tad bit different because the one thing we want to avoid is dividing by zero. Thus, I do things just a little different for safety. Here is the code I use (you will want to note that I use Line1_ and Line2_ instead of X,Y,V,U here because it makes source code easier to read. X,Y,V,U I use for standard equations, not code. In code I tend to be more descriptive):

STEP 2: Find the X-Intercept and Y-Intercept points of the TWO lines.

Don't confuse this with trying to the find the y-intercept of a single line. This is where we see if the lines intersect, and we need to find out where they intersect.

To check for an X-Intercept, we have the following equation:

xi = -(b1 - b2)/(m1-m2)
xi = -(-136.468 - 747.739) / (1.06667 - (-1.04348))
xi = -(-884.207)/(2.11015)
xi = 419.02566

And for the Y-Intercept point, we have the following:

yi = b1 + m1 * xi
yi = -136.468 + (1.06667 * 419.0256)
yi = -136.468 + 446.96203
yi = 310.494

And the code for grabbing those goes like this:

STEP 3: Check all intersect points against X,Y's/U,V's to see if we've got a hit.

All we have to do here is verify that ALL of the following are true:

(X1 - xi) * (xi - X2) >= 0
(Y1 - yi) * (yi - Y2) >= 0
(U1 - xi) * (xi - U2) >= 0
(V1 - yi) * (yi - V2) >= 0

If all of those are true, then we have an intersection.

A little cut-n-paste demo

Here is a small piece of code that you can use to play around a bit with different values. Just change the values at the top to various numbers and you'll see if there's an intersection or not:

One thing to note is that this method does NOT handle straight lines. So, if you put in a straight line you will get an incorrect assessment.

The full demo doesn't allow for straight lines. How I handle this in the demo is to verify that the starting and ending X points are not the same, and the same goes for Y.

For example, let's say that we have a line with the following four points:

X1 = 420
Y1 = 300
X2 = 420
Y2 = 319

As you can see, both the starting X and ending X (X1 and X2) are equal to 420. So we have a line that goes straight up and down. This won't work in the equations presented here. Here's how I get passed that:

That's it. It's so slightly off that it's not really noticable, but it saves the algorithm from blowing up :)

And now, for a full version of this source with comments and the little debugger thingy I mentioned at the top of this article, Click Here.

To discuss this article, click here.

All the best,

-Krylar