読者です 読者をやめる 読者になる 読者になる

丸三角四角

IT業界にしがみつく新人SEが立派なプログラマになろうともがく奮闘記

【Java】外接円の半径と座標点をもとめる_Ver1

今回は入力された3点からなる三角形の外接円の半径と中心の座標点を求める問題です。

コード更新しています。解説等はこのままこの記事で解説していますので、解説等読んだ後はVer2のコードを参照してください。

dadainu.hateblo.jp

外接円の中心座標点は、辺ABに直交する1次関数と辺ACに直交する1次関数の交点が得られれば求めることができます。外接円の半径は、三平方の定理から求めることができます。辺ABに直交する1次関数は以下の式で求めることができます。

座標A(ax, ay)、座標B(bx, by)とした場合
(bx - ax)x + (by - ay)y = (by^2 - ay^2 + bx^2 - ax^2) / 2
「^2」は2乗を表している。

上記の処理の流れを元に以下コードです。

import static java.lang.Math.sqrt;
import static java.lang.Math.pow;
import static java.lang.System.out;
import static java.lang.Integer.parseInt;
import static java.lang.Double.parseDouble;
import java.io.File;
import java.util.Scanner;

public class CircumscribedCircleofaTriangle {

    public static void main(String[] args) {
        new CircumscribedCircleofaTriangle().cirCircle();
    }

    public void cirCircle() {
        try (Scanner scan = new Scanner(System.in)) {
            circTriangle(scan);
        } catch (Exception e) {
            System.exit(0);
        }
    }

    public void cirCircle(String inputDataPath) {
        try (Scanner scan = new Scanner(new File(inputDataPath))) {
            circTriangle(scan);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private void circTriangle(Scanner scan) {
        int dataCount = parseInt(scan.nextLine());
        for (int i = 0; i < dataCount; i++) {
            double[] vertexList = getVertexList(scan);
            double[] pXY = getXY(vertexList);
            out.printf("%.3f %.3f %.3f\n", pXY[0], pXY[1], getR(vertexList, pXY));
        }
    }

    private double[] getVertexList(Scanner scan) {
        String[] vertexStrList = scan.nextLine().split(" ");
        double[] vertexList = new double[6];
        for (int i = 0; i < 6; i++) {
            vertexList[i] = parseDouble(vertexStrList[i]);
        }
        return vertexList;
    }

    private double[] getIn(double[] vertexList) {
        double ax = vertexList[0];
        double ay = vertexList[1];
        double bx = vertexList[2];
        double by = vertexList[3];
        double cx = vertexList[4];
        double cy = vertexList[5];
        double abDX = bx - ax;
        double abDY = by - ay;
        double acDX = cx - ax;
        double acDY = cy - ay;
        double[] in = { abDX, abDY, getB(ax, ay, bx, by), acDX, acDY, getB(ax, ay, cx, cy) };
        return in;
    }

    private double getR(double[] vertexList, double[] pXY) {
        return sqrt(pow(vertexList[0] - pXY[0], 2) + pow(vertexList[1] - pXY[1], 2));
    }

    private double[] getXY(double[] vertexList) {
        double[] in = getIn(vertexList);
        double deno = (in[1] * in[3] - in[0] * in[4]);
        double[] xy = new double[2];
        xy[0] = judge((in[1] * in[5] - in[2] * in[4]) / deno);
        xy[1] = judge((in[0] * in[5] - in[2] * in[3]) / (deno * -1));
        return xy;
    }

    public double judge(double num) {
        return (num == -0.0) ? 0.0 : num;
    }

    private double getB(double ax, double ay, double bx, double by) {
        return (pow(by, 2) - pow(ay, 2) + pow(bx, 2) - pow(ax, 2)) / 2;
    }
}

方程式の交点の求め方は以前にも紹介しましたが、NaNを回避するために今回は異なる求め方をしています。getInでは細かく変数に分けておりますが、インデックスに名前をつければ良かったですね。コードが長くなってしまったので、もっとよくできる方法があればコメントいただけるとありがたいです。

テストドライバは以下になります。

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

public class CircumscribedCircleofaTriangleTest extends BaseTest {

    private CircumscribedCircleofaTriangle cct;

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

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

    @Test
    public void test() {
        try {
            cct.cirCircle("./data/volume0_0010/in.txt");
            outList = outContent.toString().split("\n");
            assertOut(outList, "./data/volume0_0010/out.txt");
        } catch (Exception e) {
            e.printStackTrace();
            printErr(e);
        }
    }
}

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

in.txt
4
0.0 0.0 2.0 0.0 2.0 2.0
2.0 0.0 2.0 2.0 0.0 0.0
2.0 2.0 0.0 0.0 2.0 0.0
2.0 2.0 2.0 0.0 0.0 0.0
out.txt
1.000 1.000 1.414
1.000 1.000 1.414
1.000 1.000 1.414
1.000 1.000 1.414
1.000 1.000 1.414

答えは同じですが、入力する座標の順番を変えています。入力順番を変えても答えが一致しなければいけませんので、テストを作るというのは大事です。

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

三角形の外接円 | Aizu Online Judge

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

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

dadainu.hateblo.jp