Home > Archives > May 2009

May 2009

[ActionScript]２直線の交点を求める

2009-05-13 (Wed)
ActionScript , Flash/Flex

先日作ったライブラリを利用すると以下のようなことができます。

画面内でマウスをクリック＆ドラッグしてください。線分同士の交点を表示します。

直線や線分の交点を計算する - wonderfl build flash online

そんなに大したことはしてませんが、あえてLineクラスの特徴をあげるとするならば線分、半直線、直線に対応していることか。多くの場合は線分同士の交点を求めればいいのであまり使わないけど。

Lineクラスは以下のように使用します。

//Lineインスタンスを２つ作成
var line1:Line = new Line(new Point(x1, y1), new Point(x2, y2), Line.TYPE_SEGMENT); //Line.TYPE_SEGMENTは線分
var line2:Line = new Line(new Point(x3, y3), new Point(x4, y4), Line.TYPE_HALF); //Line.TYPE_HALFは半直線

//交点の座標を取得
var p:Point = line1.getIntersectionPoint(line2);

交点がない場合は null が返ります。

Lineクラス内では交点を求める以外にもいくつかのチェックなどしていますが、実際に交点を求めるところのアルゴリズムだけを抜き出すと以下のようになります。

// a1,a2を通る直線とb1,b2を通る直線をあらわすベクトル作成（a1, a2, b1, b2は全てPointオブジェクト）
Point a = a2 - a1;
Point b = b2 - b1;

//crossは２つのベクトルの外積を計算するメソッド
return a1 + a * cross(b, b1-a1) / cross(b, a);

参考にしたのはここ。平面幾何におけるベクトル演算 » 直線と線分

Lineクラスのソースコードは以下。

Line.as

package
{
    import flash.geom.Point;

    public class Line
    {
        /* ２点を通る直線（終端はない） */
        public static const TYPE_STRAIGHT:String = "straight";
        /* p1からp2の方向に延びる半直線 */
        public static const TYPE_HALF:String = "half";
        /* p1, p2間の線分 */
        public static const TYPE_SEGMENT:String = "segment";

        public var p1:Point;
        public var p2:Point;
        public var type:String;

        public function Line(p1:Point, p2:Point, type:String=TYPE_STRAIGHT)
        {
            this.p1 = p1;
            this.p2 = p2;
            this.type = type;
        }

        /**
         * 2つのLineインスタンスの交点を表わすPointインスタンスを取得する
         * 交点がない場合はnullを返す
         * @param line
         * @return 
         * 
         */
        public function getIntersectionPoint(line:Line):Point{
            var vector1:Point = this.getVector();
            var vector2:Point = line.getVector();

            if(cross(vector1, vector2) == 0.0){
                //2直線が並行の場合はnullを返す
                return null;
            }

            // 交点を this.p1 + s * vector1 としたとき
            var s:Number = cross(vector2, line.p1.subtract(this.p1)) / cross(vector2, vector1);
            // 交点を line.p1 + t * vector2 としたとき
            var t:Number = cross(vector1, this.p1.subtract(line.p1)) / cross(vector1, vector2);

            if(this.validateIntersect(s) && line.validateIntersect(t)){
                vector1.x *= s;
                vector1.y *= s;
                return this.p1.add(vector1);
            }else{
                return null;
            }
        }

        public function getVector():Point{
            return p2.subtract(p1);
        }

        /**
         * 交点までのベクトルを p1 + n * (p2 - p1) であらわしたとき、
         * nが適切な値の範囲内かどうかを判定する。
         * 
         * 直線の場合：nはどの値でもよい
         * 半直線の場合：nは0以上である必要がある
         * 線分の場合：nは0以上1以下である必要がある
         * @param n
         * @return 
         * 
         */
        private function validateIntersect(n:Number):Boolean{
            if(this.type === TYPE_HALF){
                return (0 <= n);
            }else if(this.type === TYPE_SEGMENT){
                return ((0 <= n) && (n <= 1));
            }else{
                return true;
            }
        }

        /**
         * 2つの2次元ベクトルの外積を返す
         * @param vector1 2次ベクトルを表わすPointインスタンス
         * @param vector2 2次ベクトルを表わすPointインスタンス
         * @return 
         * 
         */
        private function cross(vector1:Point, vector2:Point):Number{
            return (vector1.x * vector2.y - vector1.y * vector2.x);
        }

        public function toString():String{
            var str:String = "";
            if(type === TYPE_STRAIGHT){
                str += "---> ";
            }
            str += "(" + p1.x + ", " + p1.y + ") ---> (" + p2.x + ", " + p2.y + ")";
            if(type === TYPE_STRAIGHT || type === TYPE_HALF){
                str += " --->";
            }

            return str;
        }
    }
}