2つの線分が交差しているかどうかを判定するアルゴリズムとC++実装

ここでは、2つの線分が与えられたときに、それらが交差しているかどうかを判定する方法を解説します。1つ目の線分の両端を点 p1・p2、2つ目の線分の両端を点 q1・q2 とします。

2つの線分が交差していると判断できるのは、次の条件が満たされる場合です。

• (p1, p2, q1) と (p1, p2, q2) の向き（orientation）が異なる、かつ
• (q1, q2, p1) と (q1, q2, p2) の向きが異なる

さらに、(p1, p2, q1)、(p1, p2, q2)、(q1, q2, p1)、(q1, q2, p2) のすべてが同一直線上に乗る（共線：collinear）ケースも特別な条件として考慮が必要です。これは、一方の線分の端点がもう一方の線分上に接触しているような場合に該当します。

向き（orientation）の考え方

3点 a・b・c の並び順について、「時計回り」「反時計回り」「同一直線上」のいずれであるかを外積の符号から求めます。この情報を使うことで、ある点が線分に対してどちら側に位置するのかを効率よく判定できます。

入力と出力

Input:
Points of two line-segments
Line-segment 1: (0, 0) to (5, 5)
Line-segment 2: (2, -10) to (3, 10)
Output:
Lines are intersecting

アルゴリズム

direction(a, b, c)

入力: 3つの点

出力: 3点が「同一直線上」「反時計回り」「時計回り」のどれに該当するかを返す

Begin
    val := (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y)
    if val = 0, then
       return collinear
    else if val < 0, then
       return anti-clockwise
    return clockwise
End

val はベクトル ab と bc の外積に相当する値で、その符号によって3点の向きが決まります。

isIntersect(l1, l2)

入力: 2つの線分（それぞれ2点 p1・p2 を持つ）

出力: 交差していれば true

Begin
   dir1 = direction(l1.p1, l1.p2, l2.p1);
   dir2 = direction(l1.p1, l1.p2, l2.p2);
   dir3 = direction(l2.p1, l2.p2, l1.p1);
   dir4 = direction(l2.p1, l2.p2, l1.p2);

   if dir1 ≠ dir2 and dir3 ≠ dir4, then
      return true
   if dir1 = 0 and l2.p1 lies on line l1, then
      return true
   if dir2 = 0 and l2.p2 lies on line l1, then
      return true
   if dir3 = 0 and l1.p1 lies on line l2, then
      return true
   if dir4 = 0 and l1.p2 lies on line l2, then
      return true
   return false
End

まず相手の線分の端点それぞれについて4通りの向きを求め、dir1 と dir2、dir3 と dir4 がそれぞれ異なれば通常の交差と判定します。いずれかの向きが 0（共線）になった場合は、その点が相手の線分上に実際に乗っているかを onLine チェックで確認し、乗っていれば交差（接触）とみなします。

C++による実装例

#include<iostream>
using namespace std;

struct Point {
    int x, y;
};

struct line {
    Point p1, p2;
};

// 点pが線分l1上にあるかどうかを判定する
bool onLine(line l1, Point p) {
    if(p.x >= min(l1.p1.x, l1.p2.x) && p.x <= max(l1.p1.x, l1.p2.x) &&
       p.y >= min(l1.p1.y, l1.p2.y) && p.y <= max(l1.p1.y, l1.p2.y))
        return true;

    return false;
}

// 3点a, b, cの向きを求める
int direction(Point a, Point b, Point c) {
    int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if (val == 0)
        return 0;   // 同一直線上（collinear）
    else if(val < 0)
        return 2;   // 反時計回り（anti-clockwise）
    return 1;       // 時計回り（clockwise）
}

bool isIntersect(line l1, line l2) {
    // 相手の線分の端点それぞれについて向きを求める
    int dir1 = direction(l1.p1, l1.p2, l2.p1);
    int dir2 = direction(l1.p1, l1.p2, l2.p2);
    int dir3 = direction(l2.p1, l2.p2, l1.p1);
    int dir4 = direction(l2.p1, l2.p2, l1.p2);

    if(dir1 != dir2 && dir3 != dir4)
        return true; // 交差している

    if(dir1==0 && onLine(l1, l2.p1)) // 線分2のp1が線分1上にある場合
        return true;

    if(dir2==0 && onLine(l1, l2.p2)) // 線分2のp2が線分1上にある場合
        return true;

    if(dir3==0 && onLine(l2, l1.p1)) // 線分1のp1が線分2上にある場合
        return true;

    if(dir4==0 && onLine(l2, l1.p2)) // 線分1のp2が線分2上にある場合
        return true;

    return false;
}

int main() {
    line l1 = {{0,0}, {5, 5}};
    line l2 = {{2,-10}, {3, 10}};

    if(isIntersect(l1, l2))
        cout << "Lines are intersecting";
    else
        cout << "Lines are not intersecting";
}

実行結果

Lines are intersecting

線分1（(0,0)〜(5,5)）と線分2（(2,-10)〜(3,10)）は途中で交わるため、「Lines are intersecting」と出力されます。この手法は計算量 O(1) で判定でき、衝突判定や図形処理など幅広い場面で応用できます。