C++で垂直区間内の直線同士の交点を検出する方法

直線が y = mx + c という形式で複数本与えられているとします。これらの直線と垂直区間(縦方向の帯状領域)を考え、指定された区間内に直線同士の交点が存在するかどうかを判定します。例として、次のような直線があるとします。

L1 = y = x + 2
L2 = y = -x + 7
L3 = y = -3
L4 = y = 2x - 7

そして、垂直区間は x = 2 から x = 4 までとします。

この場合、L1 と L2 の交点はこの区間内に存在するため、答えは true となります。

解法の考え方

この問題は、ソートのテクニックを使うことで効率的に解けます。まず、各直線と垂直区間の両端(左境界・右境界)との交点を計算し、その結果をペアとして保存します。x座標は境界の値そのものと一致するため、保存が必要なのは交点のy座標だけです。

次に、これらのペアを「左境界でのy座標」を基準にソートします。その後、ペアを先頭から順に走査し、隣接する2つのペアを比較します。現在のペアの右境界でのy座標が、直前のペアの右境界でのy座標より小さくなっていたら、その垂直区間内に必ず交点が存在すると判断できます。

これは、区間内で交わる2本の直線は、左境界と右境界における上下の位置関係が入れ替わるという幾何学的な性質によるものです。

コード例

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
class line {
    public:
        int slope, intercept;
        line(){
        }
        line(int slope, int intercept) : slope(slope), intercept(intercept) {
    }
};
int getYCoordinate(line l, int x) {
    return (l.slope * x + l.intercept);
}
bool hasIntersectionPoint(line lines[], int left_range, int right_range, int N) {
    pair<int, int> y_border[N];
    for (int i = 0; i < N; i++)
        y_border[i] = make_pair(getYCoordinate(lines[i], left_range), getYCoordinate(lines[i], right_range));
    sort(y_border, y_border + N);
    for (int i = 1; i < N; i++) {
        if (y_border[i].second < y_border[i - 1].second)
            return true;
    }
    return false;
}
int main() {
    int N = 4;
    int slope[] = { 1, -1, 0, 2 };
    int intercept[] = { 2, 7, -3, -7 };
    line lines[N];
    for (int i = 0; i < N; i++)
        lines[i] = line(slope[i], intercept[i]);
    int left_range = 2;
    int right_range = 4;
    if (hasIntersectionPoint(lines, left_range, right_range, N)) {
        cout << "The intersection point is lies between " << left_range << " and " << right_range;
    } else {
        cout << "No intersection point is present in between " << left_range << " and " << right_range;
    }
}

出力

The intersection point is lies between 2 and 4

この出力から、交点が x = 2 から x = 4 の区間内に存在することが確認できます。

コードのポイント

line クラスは直線の傾き(slope)と切片(intercept)を保持します。getYCoordinate 関数は、指定したx座標における直線のy座標を返します。hasIntersectionPoint 関数では、まず全直線について左右の境界でのy座標をペア化し、ソートした上で順序の反転をチェックしています。計算量はソート処理が支配的で、全体の計算量は O(N log N) となります。