1. はじめに
今回は前回の記事「【プログラミング研修お題】あなたならどう解く？線のオーバーラップを判定する」の解答編になります。
お題の概要は「２つの線が重なるか（オーバーラップする）どうかを判断する処理」を実装するでした。詳細について前回の記事を参照ねがいます。
以下の観点で議論するということだったので、以下の内容も踏まえて、解答編に進みたいと思います。
- ロジックの分かりやすさ ⇒ 保守性
- ステップ数（実行行数） ⇒ 保守性、性能（フットプリント）
- 平均処理時間 ⇒ 性能（レスポンスタイム）
今回は３つの解答案を用意しました。
2. （解答１）端から端まで（Ｅ２Ｅ）の長さで判断する
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;
}
}
}
Ｅ２Ｅの長さを求めるために最大値と最小値が必要なため、配列を用意してArrays.sort()でまとめて求めました。
それぞれのラインの長さは絶対値を利用してp1、p2の大小関係を考慮しないようにしました。
- 実行行数 ： １２行（isOverlapメソッド）
[AVERGE] : 2381.846153846154 (nano second)
解答の１つ目なので速いかどうか判断できません。これを基準として次の解答に進みます。
あと、[AVERAGE]のTYPOしてますね、、、すみません。
3. （解答２）オーバーラップをしない場合を主に考える
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文が真にならない場合が「それ以外は全てオーバーラップする」です。
説明通りなのでソースコードは簡単に読めるかと思います。
ちなみに、空間が歪んでいない限り||（または）の前後が同時に成り立つことはありえません。
- 実行行数 ： ７行（isOverlapメソッド）
[AVERGE] : 793.8846153846154 (nano second)
平均処理時間は解答１の半分以下になりました。
配列を利用しない分だけ軽いのかと思います。
4. （解答３）４点をソートし、その順番で考える
実装しようと思いましたが、ぱっと見て解答１、解答２と比べてメドクサソウなので、この時点で止めました。
たぶんメンドクサイということは解答２より処理性能が短くなるとは思えません。
5. さいごに
みなさんはどうやって解いたでしょうか。そして解答１、解答２、（解答３）のどれが分かりやすいと思いましたか。
簡単な課題でしたが、いろいろな解き方があるということ、そして思いついた方法が最適な方法かどうか検討する必要があることを理解して貰えたかと思います。
ちなみに今回は「線（１次元）がオーバーラップするか」でしたが、次元数を増やすと「面（２次元）がオーバーラップするか」、「立体（３次元）がオーバーラップするか」も同様に判断できるようになります。
興味のある方は試してみてください。