javaによる2次元座標の計算など

java

とりあえず、下記に共円チェッカーで利用しているクラスの全文を記載します。

2011/07/18 22:30 Lineのコンストラクタ内の数式が誤っていたため、修正。また、参考サイトを記載。

package hm.orz.chaos114.android.kyouenchecker;

import java.util.ArrayList;
import java.util.List;

public class GameModel {

    class Point {
        double x;
        double y;

        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }

        double getAbs() {
            return Math.sqrt(x * x + y * y);
        }

        Point difference(Point p2) {
            return new Point(x - p2.x, y - p2.y);
        }

        Point sum(Point p2) {
            return new Point(x + p2.x, y + p2.y);
        }

        @Override
        public String toString() {
            return "Point [x=" + x + ", y=" + y + "]";
        }
    }

    /**
     * Ax+By+C=0を表現するクラス。
     */
    class Line {
        Point p1;
        Point p2;
        double a;
        double b;
        double c;

        Line(Point p1, Point p2) {
            this.p1 = p1;
            this.p2 = p2;

            a = p1.y - p2.y;
            b = p2.x - p1.x;
            c = p1.x * p2.y - p2.x * p1.y;
        }

        double getY(double x) {
            double y = -1 * (a * x + c) / b;

            return y;
        }

        @Override
        public String toString() {
            return "Line [p1=" + p1 + ", p2=" + p2 + ", a=" + a + ", b=" + b
                    + ", c=" + c + "]";
        }
    }

    /**
     * 共円情報を表現するクラス。
     * 
     * @author noboru
     */
    class KyouenData {
        Point p1;
        Point p2;
        Point p3;
        Point p4;

        public KyouenData(Point p1, Point p2, Point p3, Point p4) {
            this.p1 = p1;
            this.p2 = p2;
            this.p3 = p3;
            this.p4 = p4;
        }
    }

    List<Point> points = new ArrayList<Point>();

    public void add(int x, int y) {
        Point p = new Point(x, y);

        points.add(p);
    }

    public KyouenData isKyouen() {
        if (points.size() < 4) {
            return null;
        }

        Point p1 = points.get(points.size() - 1);

        for (int i = 0; i < points.size() - 1; i++) {
            Point p2 = points.get(i);
            for (int j = i + 1; j < points.size() - 1; j++) {
                Point p3 = points.get(j);
                for (int k = j + 1; k < points.size() - 1; k++) {
                    Point p4 = points.get(k);
                    boolean kyouen = isKyouen(p1, p2, p3, p4);
                    if (kyouen) {
                        return new KyouenData(p1, p2, p3, p4);
                    }
                }
            }
        }

        return null;
    }

    public boolean isKyouen(Point p1, Point p2, Point p3, Point p4) {
        // p1,p2の垂直二等分線を求める
        Line l12 = getMidperpendicular(p1, p2);
        // p2,p3の垂直二等分線を求める
        Line l23 = getMidperpendicular(p2, p3);

        // 交点を求める
        Point intersection123 = getIntersection(l12, l23);
        if (intersection123 == null) {
            // p1,p2,p3が直線上に存在する場合
            Line l34 = getMidperpendicular(p3, p4);
            Point intersection234 = getIntersection(l23, l34);
            if (intersection234 == null) {
                // p2,p3,p4が直線状に存在する場合
                return true;
            }
        } else {
            double dist1 = getDistance(p1, intersection123);
            double dist2 = getDistance(p4, intersection123);
            if (Math.abs(dist1 - dist2) < 0.0000001) {
                return true;
            }
        }
        return false;
    }

    /**
     * 2点間の距離を求める。
     * 
     * @param p1 座標1
     * @param p2 座標2
     * @return 距離
     */
    public double getDistance(Point p1, Point p2) {
        Point dist = p1.difference(p2);

        return dist.getAbs();
    }

    /**
     * 2直線の交点を求める。
     * 
     * @param l1 直線1
     * @param l2 直線2
     * @return 交点座標（交点が存在しない場合、null）
     */
    public Point getIntersection(Line l1, Line l2) {
        double f1 = l1.p2.x - l1.p1.x;
        double g1 = l1.p2.y - l1.p1.y;
        double f2 = l2.p2.x - l2.p1.x;
        double g2 = l2.p2.y - l2.p1.y;

        double det = f2 * g1 - f1 * g2;
        if (det == 0) {
            return null;
        }

        double dx = l2.p1.x - l1.p1.x;
        double dy = l2.p1.y - l1.p1.y;
        double t1 = (f2 * dy - g2 * dx) / det;

        return new Point(l1.p1.x + f1 * t1, l1.p1.y + g1 * t1);
    }

    /**
     * 2点の垂直二等分線を求める。
     * 
     * @param p1 座標1
     * @param p2 座標2
     * @return 垂直二等分線
     */
    public Line getMidperpendicular(Point p1, Point p2) {
        Point midpoint = getMidpoint(p1, p2);
        Point dif = p1.difference(p2);
        Point gradient = new Point(dif.y, -1 * dif.x);

        Line midperpendicular = new Line(midpoint, midpoint.sum(gradient));
        return midperpendicular;
    }

    /**
     * 中点を求める。
     * 
     * @param p1 座標1
     * @param p2 座標2
     * @return 中点座標
     */
    public Point getMidpoint(Point p1, Point p2) {

        Point midpoint = new Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
        return midpoint;
    }
}


で、説明など。

Pointクラス

2次元座標（x座標,y座標）を表現するためのクラスです。
ベクトル（x方向成分,y方向成分）も表します。

getAbsメソッド

座標の原点からの距離を返します。
ベクトルの大きさを表します。

differenceメソッド
sumメソッド

それぞれ、保持している座標と引数の座標の和・差を返します。

Lineクラス

Ax+By+C=0を表現するクラスです。

コンストラクタ

引数として、2つの座標を受け取ります。
保持する情報は、その2点を通過する直線の式となります。
下記サイトに書いてある通りにしました。
http://bobobobo.wordpress.com/2008/01/07/solving-linear-equations-ax-by-c-0/

getYメソッド

引数としてx座標を受け、保持している直線上のy座標を返します。

KyouenDataクラス

呼び出し元に共円となった4点を返したいがために定義したクラスです。
Listでもよかった気がします。

isKyouenメソッド

4点が登録されていない場合、判定を行いません。
最後に登録した点を基準とします。
それ以外の既存の3点を順に選んでゆき、それら4点が共円かどうかを判定します。
実際の判定処理は次のisKyouen(Point, Point, Point, Point)で行います。

isKyouen(Point, Point, Point, Point)メソッド

実際の共円判定を行います。
引数の4点が円周上に存在する場合、trueを返します。
以下、手順です。

  • 点1、点2の垂直二等分線を求めます。以降、線12とします。
  • 同じく、点2、点3の垂直二等分線を求めます。以降、線23とします。
  • 線12、線23の交点を求めます。（＝点1、2、3を通る円の中心）
    • 線12、線23が平行な場合、nullが返却されます。（＝点1,2,3が直線上に存在する）
      • 点3、点4の垂直二等分線を求めます。以降、線34とします。
      • 線23、線34の交点を求め、取得できない（＝平行）な場合、点1,2,3,4が直線上に並んでいることになるため、trueを返します。
    • 線12、線23が平行でない場合、交点が返却されます。以降、中点123とします。
      • 点1と、中点123の距離を距離1とします。
      • 点4と、中点123の距離を距離2とします。
      • 距離1、距離2の差の絶対値が、10^-7以下の場合は同一とみなし、trueを返します。（10^-7なのは、特に理由はありません）

getDistanceメソッド

引数の2ベクトルの差を求めます。
そのベクトルの大きさを返します。

getIntersectionメソッド

引数の2直線の交点を求めます。
下記のURLの計算を実行しました。
http://www.h4.dion.ne.jp/~zero1341/t/03.htm
あまり、意味がわかってないです。

getMidperpendicularメソッド

引数の点1、点2の中点を求めます。中点12とします。
点1、点2のベクトルの差を求めます。ベクトル12とします。
ベクトル12のy成分に-1を掛け、x,yを逆にしたベクトルをベクトル21とします。
中点12を通り、(中点12にベクトル21を足した点)を通る線を返します。

getMidpointメソッド

引数の2点のx,y座標の、それぞれの和を2で割った値を設定したPointを返します。



と、いった形でチェックしています。
計算が誤っている場合など、コメント下さい。