Lines

One problem that's been touched on in previous posts is how to deal with straight lines. In particular how to represent them efficiently and accurately. Making the wrong choice is not that disastrous but it can cause problems in some situations.


The simplest way to represent a line is using a linear equation, like this

y = mx + c

The variables y and x are related by the formula so y can be calculated for any value of x, so points can be plotted or calculated. But it has one serious limitation: it does not deal with vertical lines, such as the line through (0, 0) and (0, 1). This would have infinite slope, but m cannot be infinite.


It also has a more subtle problem; like the inverse trigonometric functions it becomes less accurate as it approaches certain limits. For example as a line becomes increasingly vertical and m approaches infinity small errors in x are amplified when calculating y. The errors are amplified the other way for nearly horizontal lines.


A better way is to supply a point on the line and a vector along it. The vector can be normalised as it's only its direction that's important. The advantage of vectors (formally Euclidian vectors) is that they are independent of the coordinate system, so don't have the same problems of failing in certain directions.


Alternately just two points on the line can be given. This is the approach used last week, as it makes the function especially straightforward. It's worth giving this function again to illustrate it.


    function hitLine(x1:Number, y1:Number,
        x2:Number, y2:Number):Boolean {
        // calculate the unit vector along the line
        var dX:Number = x1 - x2;
        var dY:Number = y1 - y2;
        var len:Number = Math.sqrt(dX * dX + dY * dY);
        var recip:Number = 1 / len;
        dX *= recip;
        dY *= recip;
        // perp dot product:
        return Math.abs((fX - x1) * dY - (fY - y1) * dx) < fR;
    }

The function, a member function of a circle class, takes two points as input and from them generates a normal vector along the line, (dx, dy). As noted then this could be pre-calculated for a known line, which suggests the best way to represent a line is a point on it and a vector along it. This vector is so useful in such calculations that calculating and normalising it is almost always worthwhile.