SegmentCross

/**
 * Copyright medadotter ( http://wonderfl.net/user/medadotter )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/mYqd
 */

package
{
    import flash.display.Sprite;
    import flash.events.MouseEvent;
    
    /**
     * ...
     * @author DT
     */
    [SWF(width="465",height="465")]
    public class SegmentCross extends Sprite
    {
        
        public function SegmentCross()
        {
            stage.addEventListener(MouseEvent.CLICK, testCross);
        
        }
        
        private function testCross(event:MouseEvent):void {
            
            var seg1:Segment = makeSegment();
            var seg2:Segment = makeSegment();
            graphics.clear();
            if (Segment.intersect(seg1, seg2)) {
                graphics.lineStyle(0, 0xff0000);
            }
            else {
                graphics.lineStyle(0);
            }
            
            seg1.draw(graphics);
            seg2.draw(graphics);
        }

        
        private function makeSegment():Segment {
            var begin:Point = new Point(Math.random() * stage.stageWidth,
                                        Math.random() * stage.stageHeight);
            var end:Point   = new Point(Math.random() * stage.stageWidth,
                                        Math.random() * stage.stageHeight);
            var segment:Segment = new Segment(begin, end);
            return segment;
        }
        
    
    }


}
import flash.display.Graphics;

class Point
{
    private var _x:int;
    private var _y:int;
    
    public function Point(x:int = 0, y:int = 0)
    {
        this.x = x;
        this.y = y;
    }
    
    /** 
     * ccw:counter clockwise 反時計回り（ただしX軸からY軸への方向を反時計回りのデフォルトとしている）。
     * 三点が同一直線上にない場合：
     *         反時計回り：+1
     *         時計回り  ：-1
     * 三点が同一直線上にある場合：
     *         aがbとcの間にあれば：-1
     *         bがcとaの間にあれば：+1
     *         cがaとbの間にあれば：0
     * 参考：sedgwickの本。
     */
    static public function ccwSed(a:Point, b:Point, c:Point):int {
        var ab:Point = new Point(b.x - a.x, b.y - a.y);
        var ac:Point = new Point(c.x - a.x, c.y - a.y);
        //傾きの比較ないしは外積。
        if (ab.x * ac.y > ab.y * ac.x) return +1;
        if (ab.x * ac.y < ab.y * ac.x) return -1;
        //以下、三点は同一直線上にある。
        if ((ab.x * ac.x < 0) || (ab.y * ac.y < 0)) return -1;//abとacは逆方向。
        if ((ab.x * ab.x + ab.y * ab.y) < (ac.x * ac.x + ac.y * ac.y)) return -1;//abとacが同方向でabよりacの方が短い。
        return 0;
    }
    
    /**
     * 上記のccwSedを幾何演算で可読的に書き直したもの。
     * 参考：http://www.prefield.com/algorithm/geometry/ccw.html
     */
    static public function ccw(a:Point, b:Point, c:Point):int {
        var ab:Point = new Point(b.x - a.x, b.y - a.y);
        var ac:Point = new Point(c.x - a.x, c.y - a.y);
        //外積。crossをキャッシュするのは僅かな効率のために可読性を犠牲にする。
        if (cross(ab,ac) > 0) return +1;
        if (cross(ab,ac) < 0) return -1;
        //以下、三点は同一直線上にある。
        if (dot(ab,ac) < 0) return -1;//abとacは逆方向。
        if (ab.normSQ < ac.normSQ) return -1;//abとacが同方向でabよりacの方が短い。
        return 0;
    }
    
    static public function dot(lhs:Point, rhs:Point):int {
        return lhs.x * rhs.x + lhs.y * rhs.y;
    }
    
    static public function cross(lhs:Point, rhs:Point):int {
        return lhs.x * rhs.y - lhs.y * rhs.x;        
    }
    
    public function normSQ():int {
        return x * x + y * y;
    }
    
    public function draw(graphics:Graphics):void {
        graphics.drawCircle(x, y, 1);
    }
    
    public function get x():int {
        return _x;
    }
    
    public function set x(value:int):void {
        _x = value;
    }
    
    public function get y():int {
        return _y;
    }
    
    public function set y(value:int):void {
        _y = value;
    }
}

class Segment
{
    private var _begin:Point;
    private var _end:Point;
    
    public function Segment(begin:Point, end:Point)
    {
        this.begin = begin;
        this.end = end;
    }
    
    public function draw(graphics:Graphics):void {
        graphics.drawCircle(begin.x, begin.y, 4);
        graphics.moveTo(begin.x, begin.y);
        graphics.lineTo(end.x, end.y);
    }
    
    /**
     * 二線分のそれぞれに対して、一方の線分の両端点がもう一方の線分の異なる側にあれば（Point.ccwによって判定）両線文は交差する。
     * @param    seg1
     * @param    seg2
     * @return  Boolean 交差していればtrue、していなければfalse
     */
    static public function intersect(seg1:Segment, seg2:Segment):Boolean {
        return ((Point.ccw(seg1.begin, seg1.end, seg2.begin)
                *Point.ccw(seg1.begin, seg1.end, seg2.end)) <= 0)
            && ((Point.ccw(seg2.begin, seg2.end, seg1.begin)
                *Point.ccw(seg2.begin, seg2.end, seg1.end)) <= 0);
    }
    
    public function get begin():Point {
        return _begin;
    }
    
    public function set begin(value:Point):void {
        _begin = value;
    }
    
    public function get end():Point {
        return _end;
    }
    
    public function set end(value:Point):void {
        _end = value;
    }
}