(新人必見)【解答編】【プログラミング研修お題】あなたならどう解く?線のオーバーラップを判定する


1. はじめに

今回は前回の記事「【プログラミング研修お題】あなたならどう解く?線のオーバーラップを判定する」の解答編になります。

お題の概要は「2つの線が重なるか(オーバーラップする)どうかを判断する処理」を実装するでした。詳細について前回の記事を参照ねがいます。

以下の観点で議論するということだったので、以下の内容も踏まえて、解答編に進みたいと思います。

  • ロジックの分かりやすさ ⇒ 保守性
  • ステップ数(実行行数) ⇒ 保守性、性能(フットプリント)
  • 平均処理時間 ⇒ 性能(レスポンスタイム)

今回は3つの解答案を用意しました。

2. (解答1)端から端まで(E2E)の長さで判断する

LineUtils.java(解答1)
package com.example.training;

import java.util.Arrays;

public class LineUtils {

    public static boolean isOverlap(Line l1, Line l2) {
        int[] points = { l1.getP1(), l1.getP2(), l2.getP1(), l2.getP2() };
        Arrays.sort(points);
        int e2eLength = points[3] - points[0];
        int length1 = Math.abs(l1.getP1() - l1.getP2());
        int length2 = Math.abs(l2.getP1() - l2.getP2());
        if (e2eLength >= length1 + length2) {
            return false;
        } else {
            return true;
        }
    }
}

E2Eの長さを求めるために最大値と最小値が必要なため、配列を用意してArrays.sort()でまとめて求めました。
それぞれのラインの長さは絶対値を利用してp1、p2の大小関係を考慮しないようにしました。

  • 実行行数 : 12行(isOverlapメソッド)
平均処理時間
[AVERGE] : 2381.846153846154 (nano second)

解答の1つ目なので速いかどうか判断できません。これを基準として次の解答に進みます。
あと、[AVERAGE]のTYPOしてますね、、、すみません。

3. (解答2)オーバーラップをしない場合を主に考える

LineUtils.java(解答2)
package com.example.training;

public class LineUtils {

    public static boolean isOverlap(Line l1, Line l2) {
        if ((Math.min(l2.getP1(), l2.getP2()) >= Math.max(l1.getP1(), l1.getP2()))
                || (Math.max(l2.getP1(), l2.getP2()) <= Math.min(l1.getP1(), l1.getP2()))) {
            return false;
        }
        return true;
    }
}

IF文の最初の評価が「赤のラインのMin >= 青のラインのMax オーバーラップしない」です。
||(または)の後の評価が「赤のラインのMax <= 青のラインのMin オーバーラップしない」です。
IF文が真にならない場合が「それ以外は全てオーバーラップする」です。
説明通りなのでソースコードは簡単に読めるかと思います。
ちなみに、空間が歪んでいない限り||(または)の前後が同時に成り立つことはありえません。

  • 実行行数 : 7行(isOverlapメソッド)
平均処理時間
[AVERGE] : 793.8846153846154 (nano second)

平均処理時間は解答1の半分以下になりました。
配列を利用しない分だけ軽いのかと思います。

4. (解答3)4点をソートし、その順番で考える

実装しようと思いましたが、ぱっと見て解答1、解答2と比べてメドクサソウなので、この時点で止めました。
たぶんメンドクサイということは解答2より処理性能が短くなるとは思えません。

5. さいごに

みなさんはどうやって解いたでしょうか。そして解答1、解答2、(解答3)のどれが分かりやすいと思いましたか。
簡単な課題でしたが、いろいろな解き方があるということ、そして思いついた方法が最適な方法かどうか検討する必要があることを理解して貰えたかと思います。

ちなみに今回は「線(1次元)がオーバーラップするか」でしたが、次元数を増やすと「面(2次元)がオーバーラップするか」、「立体(3次元)がオーバーラップするか」も同様に判断できるようになります。
興味のある方は試してみてください。