Wednesday, 25 January 2012

Circle-line incidence

Problems involving circles and lines can be straightforward, if handled the right way. The main reason for this is the fact that the distance from a circle to a line is just the distance from its centre to the line minus the radius. I.e. if a circle radius 100 touches a line the circle's centre must be 100 units from the line.

For a horizontal or vertical line (such as the edges of the screen) this is almost trivial, as only the x or y coordinates need be considered for each. For example to check whether a circle lies entirely inside a rectangle, the following could be used (a member function of the class used on Monday). It is written to avoid the accessors of the Rectangle class, for performance reasons

    function inRect(r:Rectangle):Boolean {
        // get x and y as are needed more than once
        var rX:Number = r.x, rY:Number = r.y;
        return (fX > rX + fR && fX < rX + r.width - fR
            && fY > rY + fR && fY < rY + r.height - fR);

Handling an general line is a little more complex, but not by much. There are a few ways to represent a general line, but in this example the endpoints are given. I.e. the line is the line through two distinct points (x1, y1) and (x2, y2).

    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;

This uses the perp dot product, a two-dimensional analogue of the cross and dot products. It takes the absolute value as the centre of the circle could be on either side of the line – the sign of that expression before the absolute value is taken indicates which side of the line the circle is on. Note than everything up to the final line could be pre-calculated and stored in a class if the test is to be performed many times on the same line.

No comments:

Post a Comment