C++で直線に対する点の位置を判定！Above-Below-onテストの実装方法

この記事では、Above-Below-on テストを適用して、ある点が直線に対してどの位置（下側・上側・直線上）にあるのかを判定する C++ プログラムを紹介します。

平面上の任意の点 t(xt, yt) について、2点 m と n を結ぶ直線 L に対する位置関係は、次のスカラー値 s を計算することで求められます。

Y = A·xt + B·yt + C

計算結果の符号により、次のように判定できます。

• s < 0 の場合：点 t は直線 L の時計回り側の半平面（下側・左側）にあります。
• s > 0 の場合：点 t は直線 L の反時計回り側の半平面（上側・右側）にあります。
• s = 0 の場合：点 t は直線 L 上にあります。

アルゴリズム

開始
    点を入力として受け取る。
    直線の方程式を生成するため、コンパイルのたびに rand 関数を使って x・y の係数（x1, x2, y1, y2）に相当する乱数を生成する。
    s を (y2 - y1) * x + (x1 - x2) * y + (x2 * y1 - x1 * y2) として計算する。
    if (s < 0)
        「点は直線の下側（左側）にあります」と出力する。
    else if (s > 0)
        「点は直線の上側（右側）にあります」と出力する。
    else
        「点は直線上にあります」と出力する。
終了

C++ サンプルコード

#include<stdlib.h>
#include<iostream>
#include<math.h>
#include<time.h>
using namespace std;

const int L = 0;
const int H = 20;

int main(int argc, char **argv) {
    time_t seconds;
    time(&seconds);
    srand((unsigned int) seconds);

    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 << "1本目の直線の方程式 : (" << (y2 - y1) << ")x+(" << (x1 - x2) << ")y+(" << (x2 * y1 - x1 * y2) << ") = 0\n";

    int x, y;
    cout << "\n点を入力してください:";
    cin >> x;
    cin >> y;

    int s = (y2 - y1) * x + (x1 - x2) * y + (x2 * y1 - x1 * y2);
    if (s < 0)
        cout << "点は直線の下側（左側）にあります";
    else if (s > 0)
        cout << "点は直線の上側（右側）にあります";
    else
        cout << "点は直線上にあります";
    return 0;
}

実行結果

1本目の直線の方程式 : (7)x+(0)y+(-105) = 0

点を入力してください:7
6
点は直線の下側（左側）にあります

プログラムのポイント

このプログラムは、直線の一般形 Ax + By + C = 0 を利用しています。2点 (x1, y1) と (x2, y2) を通る直線の場合、各係数は次のように表されます。

• A = y2 − y1
• B = x1 − x2
• C = x2 × y1 − x1 × y2

判定したい点 (x, y) をこの式に代入して得られる値 s の符号を調べることで、点が直線のどちら側に位置するのかを一意に決定できます。これは外積（クロス積）の符号判定と本質的に同じ考え方であり、計算幾何学における最も基本的かつ重要な処理の一つです。

また、srand 関数のシードに現在時刻を渡しているため、プログラムを実行するたびに異なる直線がランダムに生成され、さまざまなケースで動作を確認できるのが特徴です。