With the recent advances in Flash 3D and panoramas, and the fact that Flash 10, now out in beta, has intrinsic support for arbitrary warping of triangles, we can look forward to a future of increased performance and the complete disappearance of those wavy lines in panos. All of that fancy 3D stuff is based on matrix transformations, but lately I’ve been working with simpler analytic-geometry concepts, some of which turn out to be quite useful. Let’s look at a few.

We’ll start with the sameSide() function, which I’ll use to implement some more interesting functions:

// sameSide.as
package
{
    import flash.geom.Point;

    // are p1 and p2 on the same side of the line through a and b?
    public function sameSide(p1:Point, p2:Point, a:Point, b:Point):Boolean
    {
        var cp1:Number = cross(b.subtract(a), p1.subtract(a));
        var cp2:Number = cross(b.subtract(a), p2.subtract(a));
        return (dot(cp1, cp2) >= 0);
    }
}       

    import flash.geom.Point;

    function cross(a:Point, b:Point):Number
    {
        // z coordinate of the cross product; x and y coordinates are zero
        return a.x * b.y - a.y * b.x;
    }

    function dot(a:Number, b:Number):Number
    {
        // z vectors
        return a * b;
    }

A little AS3 note about the foregoing: The above code is the entire sameSide.as file; it’s a bit unusual in that it does not contain a class. AS3 requires that a source file expose a single external definition, which in this case is a function rather than a class. A function defined in this way is called a package-level function. The functions cross() and dot() that appear after the closing curly brace are visible only to code within the same file, and thus any access control specifier like “internal” or “private” would be redundant.

Of course you could make sameSide() a public static method of a Class, and cross() and dot() private static methods.

Now we implement some other functions based on sameSide():

// behind.as
package
{
    import flash.geom.Point;

       /**
         * Is p2 behind me when I stand at p0 and face p1?
         *
         */
        public function behind(p0:Point, p1:Point, p2:Point):Boolean
        {
            // slope of normal to the line p0p1:
            var m:Number = (p0.x - p1.x)/(p1.y - p0.y);
            // y-intercept of normal through p0:
            var b:Number = p0.y - m * p0.x;

            return !sameSide(p1, p2, p0, new Point(0, b));
        }
}

// beyond.as
package
{
    import flash.geom.Point;

       /**
         * Is p2 beyond p1 when I stand at p0 and face p1?
         *
         */
       public function beyond(p0:Point, p1:Point, p2:Point):Boolean
        {
            // slope of normal to the line p0p1:
            var m:Number = (p0.x - p1.x)/(p1.y - p0.y);
            // y-intercept of normal through p1:
            var b:Number = p1.y - m * p1.x;

            return !sameSide(p0, p2, p1, new Point(0, b));
        }
}

Cute, eh? Nice to know if something is behind you, or beyond me.

Here’s another:

package
{
    import flash.geom.Point;

/**
* Is the point p inside the triangle abc?
*/
    public function pointInTriangle(p:Point, a:Point, b:Point, c:Point):Boolean
    {
        return sameSide(p, a, b, c) && sameSide(p, b, a, c) && sameSide(p, c, a, b);
    }
}

which is to say p is inside triangle abc if it’s on the same side of line bc as a, and on the same side of line ac as b, and on the same side of line ab as c. How obvious is that?

I have to credit my source here, because “point in triangle” was the search that led me to sameSide(): Point In Triangle Test. As it turns out, I haven’t actually used pointInTriangle() for anything yet. behind() and beyond(), though, play an important part in Geometry-Based Path Planning, the subject of a future post.

Frequent sources of inspiration on similar topics are Wolfram MathWorld and of course Wikipedia.