Tricks of the Windows Game Programming Gurus:Vector Rasterization and 2D Transformations

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

#### Computing the Intersection of Two Lines Using the Point Slope Form

Off the top of my head, I like both the Point Slope form and the general form. As a good example of algebra, let’s work through the intersection of two lines, p0 and p1, using each type of representation. This should warm you up a little for the really gnarly math that’s ahead in later chapters <BG>. Let’s do the general Point Slope version first (see Figure 8.10).

Figure 8.10 Computing the intersection of two lines.

Referring to Figure 8.10:

    Let the first line segment p0 be (x0,y0) to (x1,y1)

    Let the second line segment p1 be (x2,y2) to (x3,y3)

Here, p0 and p1 can have any orientation:

    Eq.1 – Point Slope form of p0:

    m0 = (y1 – y0)/(x1 – x0)

and,

    (x – x0) = m0*(y – y0)

    Eq.2 – Point Slope form of p1:

    m1 = (y3 – y2)/(x3 – x2)

and,

    (x – x2) = m1*(y – y2)

Now you have two equations in two unknowns:

    Eq.1: (x – x0) = m0*(y – y0)

    Eq.2: (x – x2) = m1*(y – y2)

There are two primary ways to solve for (x,y): substitution or matrix operations. Let’s try substitution first. The idea here is to find one variable in terms of the other and then plug it into the other equation. Let’s try finding x in terms of y for Equation 1 and then plug it into Equation 2:

Equation 1—x in terms of y:

    (x – x0) = m0*(y – y0)

    x = m0*(y-y0) + x0

That was easy. Now let’s plug it into Equation 2 for x.

Equation 2 is

    (x – x2) = m1*(y – y2)

In Equation 1, x = m0*(y-y0) + x0. Let’s plug that into x:

    (m0*(y-y0) + x0 – x2) = m1*(y – y2)

Simplifying for y:

    m0*y – m0*y0 + x0 – x2 = m1*y – m1*y2

Collect terms:

    m0*y - m1*y = – m1*y2 – (– m0*y0 + x0 – x2)

Pull out y and multiply all signs:

    y*(m0 – m1) = m0*y0 – m1*y2 + x2 – x0

And finally, divide both sides by (m0 – m1):

    y = (m0*y0 – m1*y2 + x2 – x0)/(m0 – m1)

At this point you could plug this back into Equation 1 and solve for x, or you could rewrite Equation 2 in terms of x and plug that into y of Equation 1. The results will be the same and are shown here.

Equation 3:

    x = (-m0/(m1 – m0))*x2 + m0*(y2 – y0) + x0

Equation 4:

    y = (m0*y0 – m1*y2 + x2 – x0)/(m0 – m1)

Now, there are some things here that you must consider. First, are there any situations where the previous equations will have problems? Yes! In advanced mathematics, infinity isn’t a problem to work with, but in computer graphics, it is! In Equations 3 and 4, the term (m1 – m0) and (m0 – m1) could be 0.0 if the slope of the two lines is the same—in other words, when the lines are parallel.

In this case, they can’t possibly intersect and you get a 0.0 in the denominators, driving the quotients of both Equation 3 and 4 to infinity. Of course, this means that at infinity the lines touch, but because you’re only working with screens that have a resolution of 1024×768 or so, it’s not something you need to consider <BG>.

The bottom line is that this tells you that the intersection equations only work for lines that intersect! If they can’t possibly intersect, the math will fail. This is easy to test. Simply check m0 and m1 before doing the math. If m0 == m1, there isn’t an intersection. Anyway, let’s move on…

If you take a look at Equations 3 and 4 and count up the operations, you’re doing about four divides, four multiplies, and eight additions (subtractions count as additions). If you count computing the slopes m0 and m1, that adds four more additions and two divisions. Not too bad.

#### Computing the Intersection of Two Lines Using the General Form

The general form of any linear equation is

    a*x + b*y = c

Or, if you like the canonical form:

    a*x + b*y + c = 0

In reality, both the Point Slope form and Y-Intercept form can be put into the general form. For example, if you look at the Y-Intercept form:

    y = m*x+b

    m*x – 1*y = b

Or a = m, b = -1, and c = b (the intercept). But what if you don’t have the intercept? How can you find the values of (a,b,c) if you only have the coordinates (x0,y1) and (x2,y2)? Well, let’s see if the Point Slope form can help out…

    (y – y0) = m*(x – x0)

Multiplying by m:

    y – y0 = m*x – m*x0

Collecting x and y on the LHS (left-hand side):

Math The (-1) and the associated multiplies aren’t necessary. They just make the extraction of (a,b,c) easier to see.

    -m*x + y = y0 + m*x0

Multiplying by –1:

    m*x + (-1)*y = (-m)*x0 + (-1)*y0

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.