アルゴリズムクイックリファレンス 第2版

9.4

 線分交差を計算する

■

293

9.4

 線分交差を計算する

2

次元平面で線分の集合

S

が与えられたとき、すべての線分間の交点の全集合を

決定する必要がある。図9-6の例では、

4

つの線分に（黒丸で示された）交点が

2

つ

ある。例9-2のように、力任せの方式だと、

S

に含まれる線分間すべての交点を計

算するので、

C(n, 2)

、すなわち

n*(n

−

1)/2

個の交点の計算を行い、

O(n

2

)

時間か

かる。線分の各対について、交点を（もしあるなら）出力する。

図9-6　2 つの交点を持つ 4つの線分

例

9-2

 力任せ交点計算の実装

public class BruteForceAlgorithm extends IntersectionDetection {

public Hashtable<IPoint, List<ILineSegment[]>> intersections

(ILineSegment[] segments) {

initialize();

for (int i = 0; i < segments.length-1; i++) {

for (int j = i+1; j < segments.length; j++) {

IPoint p = segments[i].intersection(segments[j]);

if (p != null) {

record (p, segments[i], segments[j]);

}

}

}

return report;

}

}

この計算には、 ...