C++で2本の直線の交点を求めるプログラムの書き方

直線ABを定義する2点A・Bと、直線CDを定義する2点C・Dが与えられたとき、この2つの直線の交点を求めるのが課題です。

注意 − すべての点は、X座標とY座標を持つ2次元平面上にあるものとします。

図では、A(a1, a2)とB(b1, b2)を通る直線、C(c1, c2)とD(d1, d2)を通る直線という、互いに異なる2つの直線が描かれており、P(p1, p2)がその交点を表しています。

交点の求め方

まず、2点を通る直線を「ax + by = c」の形の方程式で表します。各点の座標を使って、次のように係数を計算します。

A1 = b2 - a2
B1 = a1 - b1
C1 = (A1 * a1) + (B1 * a2)
A2 = d2 - c2
B2 = c1 - d1
C2 = (A2 * c1) + (B2 * c2)

こうして、2つの直線は次の連立一次方程式として表せます。

1. A1x + B1y = C1
2. A2x + B2y = C2

交点を求めるには、この連立方程式を解きます。式1にB2を掛け、式2にB1を掛けてから、2つの式の差を取ります。

A1B2x + B1B2y = C1B2
A2B1x + B2B1y = C2B1

辺々引くと、
(A1B2 - A2B1)x = C1B2 - C2B1

これでxの値が求まります。同様の手順でyの値も求められ、このxが交点のp1、yがp2に対応します。

注意 − 上記の式は「直線」同士の交点を求めるものです。与えられたのが線分の場合は、計算した交点が実際に線分上に存在するかを、次の条件で再確認する必要があります。

• min(x1, x2) <= x <= max(x1, x2)
• min(y1, y2) <= y <= max(y1, y2)

問題を解くためのアプローチ

• 入力値を受け取ります。
• 行列式 det = a1 * b2 - a2 * b1 を計算します。
• det = 0 の場合、2つの直線は平行であり、交点は存在しません。
• det ≠ 0 の場合、x = (c1 * b2 - c2 * b1) / det、y = (a1 * c2 - a2 * c1) / det として交点を求めます。
• 結果を返して出力します。

アルゴリズム

開始
ステップ1 -> x座標とy座標を表示する関数を宣言する
    void display(mk_pair par)
    par.first と par.second を出力する
ステップ2 -> 交点を計算する関数を宣言する
    mk_pair intersection(mk_pair A, mk_pair B, mk_pair C, mk_pair D)
    double a = B.second - A.second を宣言
    double b = A.first - B.first を宣言
    double c = a*(A.first) + b*(A.second) を宣言
    double a1 = D.second - C.second を宣言
    double b1 = C.first - D.first を宣言
    double c1 = a1*(C.first) + b1*(C.second) を宣言
    double det = a*b1 - a1*b を宣言
    IF (det == 0)
        return make_pair(FLT_MAX, FLT_MAX)
    End
    ELSE
        double x = (b1*c - b*c1)/det を宣言
        double y = (a*c1 - a1*c)/det を宣言
        return make_pair(x, y)
    End
ステップ3 -> main() 内で
    点を mk_pair q = make_pair(2, 1) などとして宣言する
    IF (inter.first == FLT_MAX AND inter.second == FLT_MAX)
        「与えられた直線は平行です」と出力する
    End
    ELSE
        display(inter) を呼び出す
    End
終了

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define mk_pair pair<double, double>

// x座標とy座標を表示する
void display(mk_pair par) {
    cout << "(" << par.first << ", " << par.second << ")" << endl;
}

mk_pair intersection(mk_pair A, mk_pair B, mk_pair C, mk_pair D) {
    // 直線ABを a1x + b1y = c1 の形で表す
    double a = B.second - A.second;
    double b = A.first - B.first;
    double c = a*(A.first) + b*(A.second);
    // 直線CDを a2x + b2y = c2 の形で表す
    double a1 = D.second - C.second;
    double b1 = C.first - D.first;
    double c1 = a1*(C.first) + b1*(C.second);
    double det = a*b1 - a1*b;
    if (det == 0) {
        return make_pair(FLT_MAX, FLT_MAX); // 平行の場合の目印
    } else {
        double x = (b1*c - b*c1)/det;
        double y = (a*c1 - a1*c)/det;
        return make_pair(x, y);
    }
}

int main() {
    mk_pair q = make_pair(2, 1);
    mk_pair r = make_pair(2, 7);
    mk_pair s = make_pair(4, 4);
    mk_pair t = make_pair(6, 4);
    mk_pair inter = intersection(q, r, s, t);
    if (inter.first == FLT_MAX && inter.second == FLT_MAX) {
        cout << "与えられた直線ABとCDは平行です。\n";
    } else {
        cout << "直線ABとCDの交点は: ";
        display(inter);
    }
    return 0;
}

出力

直線ABとCDの交点は: (2, 4)

この例では、点(2, 1)と(2, 7)を通る直線ABは垂直な直線「x = 2」、点(4, 4)と(6, 4)を通る直線CDは水平な直線「y = 4」となります。両者の交点は(2, 4)であり、プログラムの出力と一致します。なお、平行判定にはFLT_MAXを特別な値（番兵）として利用しており、detが0のときは交点が存在しないことを示しています。