【Java】三角形内外点判定_Ver1

今回の問題は、点Pが三角形ABCの内か外かを判定する問題です。

この問題を解くには、ベクトルの知識が必要です。まず一つ目の定義は以下です。

三角形ABCのそれぞれの辺をAB、BC、CAとした時、
以下が成り立つ。
→AB × →AP > 0
→BC × →BP > 0
→CA × →CP > 0

三角形ACBのそれぞれの辺をAC、CB、BAとした時、
以下が成り立つ。
→AC × →AP < 0
→CB × →CP < 0
→BA × →BP < 0

二つ目の定義は以下です。

→a = (ax, ay), →b = (bx, by)とした時、
→a × →b = (ax × by - ay × bx) 
が成り立ちます。

上記二つの定義を用いて実装していきます。コードは以下です。

import static java.lang.System.out;
import static java.lang.Double.parseDouble;
import java.util.Scanner;
import volume0.BaseExe;

public class APointInATriangle extends BaseExe {

    public static void main(String[] args) {
        new APointInATriangle().exeSysIn();
    }

    @Override
    protected void execute(Scanner scan) {
        String inData;
        while (scan.hasNextLine() && !"".equals(inData = scan.nextLine())) {
            Point[] points = getPoints(inData.split(" "));
            Point[] vect = getVects(points);
            double[] vectProducts = getProducts(vect);
            if (judgeInner(vectProducts)) {
                out.println("YES");
            } else {
                out.println("NO");
            }
        }
    }

    private boolean judgeInner(double[] vectProducts) {
        return (judgeIsClockWise(vectProducts) || judgeIsNotClockWise(vectProducts));
    }

    private boolean judgeIsClockWise(double[] vectProducts) {
        return (0.0 < vectProducts[0] && 0.0 < vectProducts[1] && 0.0 < vectProducts[2]);
    }

    private boolean judgeIsNotClockWise(double[] vectProducts) {
        return (0.0 > vectProducts[0] && 0.0 > vectProducts[1] && 0.0 > vectProducts[2]);
    }

    private Point[] getPoints(String[] inDataList) {
        Point[] points = new Point[4];
        for (int index = 0; index < 4; index++) {
            points[index] = new Point(parseDouble(inDataList[index * 2]),
                    parseDouble(inDataList[index * 2 + 1]));
        }
        return points;
    }

    private Point[] getVects(Point[] points) {
        Point[] vect = new Point[6];
        vect[0] = getXY(points[0], points[1]);
        vect[1] = getXY(points[1], points[2]);
        vect[2] = getXY(points[2], points[0]);
        vect[3] = getXY(points[0], points[3]);
        vect[4] = getXY(points[1], points[3]);
        vect[5] = getXY(points[2], points[3]);
        return vect;
    }

    private Point getXY(Point a, Point b) {
        return new Point(b.getX() - a.getX(), b.getY() - a.getY());
    }

    private double[] getProducts(Point[] vect) {
        double[] vectProducts = new double[3];
        vectProducts[0] = getProd(vect[0], vect[3]);
        vectProducts[1] = getProd(vect[1], vect[4]);
        vectProducts[2] = getProd(vect[2], vect[5]);
        return vectProducts;
    }

    private double getProd(Point ab, Point ap) {
        return ab.getX() * ap.getY() - ab.getY() * ap.getX();
    }

}

class Point {

    private double x;
    private double y;

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

    public double getX() {
        return this.x;
    }

    public double getY() {
        return this.y;
    }

    @Override
    public String toString() {
        return "x : " + this.x + ",y : " + this.y;
    }
}

座標クラスに入力されたxy座標を振り分け、各辺のベクトルを求めます。その後に外積を求め、点Pが内か外かを判定しています。テストドライバは以下になります。

import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import volume0.BaseTest;

public class APointInATriangleTest extends BaseTest {

    private APointInATriangle apiat;

    @Before
    public void setUp() throws Exception {
        super.setUp();
        apiat = new APointInATriangle();
    }

    @After
    public void tearDown() throws Exception {
        super.tearDown();
    }

    @Test
    public void test() {
        apiat.exeFileIn("./data/volume0_0012/in.txt");
        assertOutList("./data/volume0_0012/out.txt");
    }
}

テストドライバ内で使用している「in.txt」・「out.txt」は以下になります。

in.txt
0.0 0.0 2.0 0.0 2.0 2.0 1.5 0.5
2.0 0.0 2.0 2.0 0.0 0.0 1.5 0.5
2.0 2.0 0.0 0.0 2.0 0.0 1.5 0.5
2.0 2.0 2.0 0.0 0.0 0.0 1.5 0.5
2.0 0.0 0.0 0.0 2.0 2.0 1.5 0.5
0.0 0.0 2.0 2.0 2.0 0.0 1.5 0.5
0.0 0.0 1.0 4.0 5.0 3.0 -1.0 3.0
1.0 4.0 5.0 3.0 0.0 0.0 -1.0 3.0
5.0 3.0 0.0 0.0 1.0 4.0 -1.0 3.0
0.0 0.0 5.0 3.0 1.0 4.0 -1.0 3.0
1.0 4.0 0.0 0.0 5.0 3.0 -1.0 3.0
5.0 3.0 1.0 4.0 0.0 0.0 -1.0 3.0
0.0 0.0 2.0 0.0 2.0 2.0 1.0 0.0

out.txt
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES

今回の問題は以下にあります。

三角形の中の点 | Aizu Online Judge

アルゴリスムで困った時は、以下の本を参考にしてます。Javaに置き換えるのが少々難解ですが、、、

固有処理の基底クラスは以下の記事に記載していますので、参考にしてください。

dadainu.hateblo.jp

テストドライバで継承しているクラスは以下の記事に記載していますので、参考にしてみてください。

dadainu.hateblo.jp