line-line intersection

/* lines_intersect:  AUTHOR: Mukesh Prasad
*
*   This function computes whether two line segments,
*   respectively joining the input points (x1,y1) -- (x2,y2)
*   and the input points (x3,y3) -- (x4,y4) intersect.
*   If the lines intersect, the output variables x, y are
*   set to coordinates of the point of intersection.
*
*   All values are in integers.  The returned value is rounded
*   to the nearest integer point.
*
*   If non-integral grid points are relevant, the function
*   can easily be transformed by substituting floating point
*   calculations instead of integer calculations.
*
*   Entry
*        x1, y1,  x2, y2   Coordinates of endpoints of one segment.
*        x3, y3,  x4, y4   Coordinates of endpoints of other segment.
*
*   Exit
*        x, y              Coordinates of intersection point.
*
*   The value returned by the function is one of:
*
*        DONT_INTERSECT    0
*        DO_INTERSECT      1
*        COLLINEAR         2
*
* Error conditions:
*
*     Depending upon the possible ranges, and particularly on 16-bit
*     computers, care should be taken to protect from overflow.
*
*     In the following code, 'long' values have been used for this
*     purpose, instead of 'int'.
*
*/

package  {
    import flash.geom.Point;
    public class xlines {
        static public const DONT_INTERSECT:int = 0;
        static public const DO_INTERSECT:int = 1;
        static public const COLLINEAR:int = 2;
        static public function lines_intersect( x1:Number, y1:Number,   /* First line segment */
                                                x2:Number, y2:Number,
                                                x3:Number, y3:Number,   /* Second line segment */
                                                x4:Number, y4:Number,
                                                out:Point   /* Output value: */
                                                ):int {     /* point of intersection */
            /* Coefficients of line eqns. */
            var a1:Number, a2:Number, b1:Number, b2:Number, c1:Number, c2:Number;
            /* 'Sign' values */
            var r1:Number, r2:Number, r3:Number, r4:Number;
            /* Intermediate values */
            var denom:Number, offset:Number, num:Number;

            /* Compute a1, b1, c1, where line joining points 1 and 2
             * is "a1 x  +  b1 y  +  c1  =  0".
             */

            a1 = y2 - y1;
            b1 = x1 - x2;
            c1 = x2 * y1 - x1 * y2;

            /* Compute r3 and r4.
             */


            r3 = a1 * x3 + b1 * y3 + c1;
            r4 = a1 * x4 + b1 * y4 + c1;

            /* Check signs of r3 and r4.  If both point 3 and point 4 lie on
             * same side of line 1, the line segments do not intersect.
             */

            if ( r3 != 0 &&
                 r4 != 0 &&
                 SAME_SIGNS( r3, r4 ))
                return ( DONT_INTERSECT );

            /* Compute a2, b2, c2 */

            a2 = y4 - y3;
            b2 = x3 - x4;
            c2 = x4 * y3 - x3 * y4;

            /* Compute r1 and r2 */

            r1 = a2 * x1 + b2 * y1 + c2;
            r2 = a2 * x2 + b2 * y2 + c2;

            /* Check signs of r1 and r2.  If both point 1 and point 2 lie
             * on same side of second line segment, the line segments do
             * not intersect.
             */

            if ( r1 != 0 &&
                 r2 != 0 &&
                 SAME_SIGNS( r1, r2 ))
                return ( DONT_INTERSECT );

            /* Line segments intersect: compute intersection point.
             */

            denom = a1 * b2 - a2 * b1;
            if ( denom == 0 )
                return ( COLLINEAR );
            offset = denom < 0 ? - denom / 2 : denom / 2;

            /* The denom/2 is to get rounding instead of truncating.  It
             * is added or subtracted to the numerator, depending upon the
             * sign of the numerator.
             */

            num = b1 * c2 - b2 * c1;
            out.x = ( num < 0 ? num - offset : num + offset ) / denom;

            num = a2 * c1 - a1 * c2;
            out.y = ( num < 0 ? num - offset : num + offset ) / denom;

            return ( DO_INTERSECT );
        } /* lines_intersect */

        static private function SAME_SIGNS(x:Number, y:Number):Boolean {
            return (x < 0 ? -1 : 1) == (y < 0 ? -1 : 1);
        }
    }
}