上下（above-below）プリミティブを使って2本の直線が交差するかどうかを判定するC++プログラム

ここでは、「上・下（above-below）」プリミティブを用いて、2本の直線が交差するかどうかを判定するC++プログラムを紹介します。この手法は、ある直線と線分の交差判定にも応用できます。線分が直線と交差するのは、線分の一方の端点が直線の左側にあり、もう一方の端点が右側にある場合、そのときに限られます。

交差判定の仕組み

直線の一般形 ax + by + c = 0 に、ある点の座標を代入すると、その結果の符号から点が直線のどちら側にあるかが分かります。結果が正なら一方の側、負なら反対側、0なら直線上に存在することを意味します。そこで、線分の両端点を同じ直線の方程式に代入し、得られる符号が異なれば、その線分は直線と交差していると判断できるのです。

アルゴリズム

Begin
    1本目の直線の方程式を生成するため、実行のたびに rand() を使って x と y の係数に乱数を発生させる。
    2本目の直線についても同様に、rand() で係数となる乱数を生成する。
    直線1に対する線分の判定値を Y1 として求める。
    if (Y1 < 0)
        もう一方の端点に対する判定値 Y2 を求める
        if (Y2 >= 0) → 「交差している」と出力
        else if (Y2 < 0) → 「交差していない」と出力
    else if (Y1 > 0)
        判定値 Y2 を求める
        if (Y2 <= 0) → 「交差している」と出力
        else if (Y2 > 0) → 「交差していない」と出力
    else
        「点は直線上にある」と出力
End.

処理の流れのポイント

まず一方の端点を直線の式に代入して判定値 Y1 を求め、その符号を確認します。Y1 が負の場合は、もう一方の端点の判定値 Y2 が 0 以上であれば交差、負であれば非交差と判定します。逆に Y1 が正の場合は、Y2 が 0 以下なら交差とみなします。Y1 がちょうど 0 の場合は、端点そのものが直線上にあることになります。

サンプルコード

#include<time.h>
#include<stdlib.h>
#include<iostream>
#include<math.h>

using namespace std;
const int L = 2;
const int H= 20;
int main(int argc, char **argv) {
    time_t s;
    time(&s);
    srand((unsigned int) s);

    int x1, x2, y1, y2;
    x1 = rand() % (H - L+ 1) + L;
    x2 = rand() % (H - L+ 1) + L;
    y1 = rand() % (H- L+ 1) + L;
    y2 = rand() % (H - L + 1) + L;

    cout << "The Equation of the 1st line is : (" << (y2 - y1) << ")x+(" << (x1 - x2) << ")y+(" << (x2 * y1 - x1 * y2) << ") = 0\n";

    int p1, p2, q1, q2;
    p1 = rand() % (H- L+ 1) + L;
    p2 = rand() % (H- L + 1) + L;
    q1 = rand() % (H - L + 1) + L;
    q2 = rand() % (H - L + 1) + L;

    cout << "The Equation of the 2nd line is : (" << (q2 - q1) << ")x+(" << (p1 - p2) << ")y+(" << (p2 * q1 - p1 * q2) << ") = 0\n";

    int Y1 = (y2 - y1) * p1 + (x1 - x2) * q1 + (x2 * y1 - x1 * y2); //Y1 segment
    if (Y1 < 0) {
        int Y2 = (y2 - y1) * p2 + (x1 - x2) * q2 + (x2 * y1 - x1 * y2); //Y2 segment
    if (Y2 >= 0)
        cout << "Lines are intersecting";
    else if (Y2 < 0)
        cout << "Lines are not intersecting";
    } else if (Y1 >0) {
        int Y2 = (y2 - y1) * p2 + (x1 - x2) * q2 + (x2 * y1 - x1 * y2);
       if (Y2 <= 0)
           cout << "Lines are intersecting";
       else if (Y2 >0)
           cout << "Lines are not intersecting";
    } else
        cout << "The point lies on the line";
    return 0;
}

このコードでは、現在時刻をシードとして乱数を初期化し、範囲 [L, H] 内の座標値から2本の直線の方程式を自動生成しています。その後、2本目の直線の端点を1本目の直線の方程式に代入し、判定値 Y1・Y2 の符号の組み合わせによって交差の有無を出力します。

実行結果

The Equation of the 1st line is : (-3)x+(2)y+(1) = 0
The Equation of the 2nd line is : (-5)x+(-5)y+(130) = 0
Lines are intersecting


The Equation of the 1st line is : (-1)x+(7)y+(-15) = 0
The Equation of the 2nd line is : (-4)x+(4)y+(-8) = 0
Lines are not intersecting

1回目の実行では2本の直線が交差していると判定され、2回目では交差していないと判定されています。乱数を使用しているため、実行するたびに異なる直線の方程式が生成され、判定結果もそれに応じて変化します。