与えられた3点が同一直線上にあるかどうかを判定するC++プログラム

3点が同一直線上にあるかどうかの判定方法

この記事では、与えられた3点が同一直線上にあるかどうかを判定するC++プログラムを紹介します。判定のポイントは、3点を頂点とする三角形の面積がゼロになるかどうかです。3点が同一直線上に並んでいる場合、三角形はつぶれた形になるため、その面積はゼロになります。

3点 (x1, y1)、(x2, y2)、(x3, y3) からなる三角形の面積は、次の式で計算できます。

0.5 * (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))

この式は、座標から図形の面積を求める「靴ひも公式(シューレースの公式)」に基づいています。計算結果が正でも負でも、3点は同一直線上にはありません。面積がちょうどゼロになる場合のみ、3点は同一直線上にあると判定できます。

アルゴリズム

開始
    3点の座標をランダムに生成する
    上記の式を使って三角形の面積を計算する
    もし面積 > 0 なら
        3点は同一直線上にない
    そうでなく面積 < 0 なら
        3点は同一直線上にない
    それ以外(面積 = 0)なら
        3点は同一直線上にある
終了

サンプルコード

以下のプログラムでは、rand()関数を使って1から20の範囲で3点の座標をランダムに生成し、上記の式で面積を計算して直線上にあるかどうかを判定します。

#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
static int L = 1;
static int U = 20;
int main(int argc, char **argv) {
    int x1, y1, x2, y2, x3, y3;
    time_t seconds;
    time(&seconds);
    srand((unsigned int) seconds);
    // rand()を使って点の座標をランダムに生成
    x1 = rand() % (U - L + 1) + L;
    y1 = rand() % (U - L + 1) + L;
    x2 = rand() % (U - L + 1) + L;
    y2 = rand() % (U - L + 1) + L;
    x3 = rand() % (U - L + 1) + L;
    y3 = rand() % (U - L + 1) + L;
    cout << "The points are: (" << x1 << ", " << y1 << "), (" << x2 << ", " << y2 << "), & (" << x3 << ", " << y3 << ")\n";
    // 三角形の面積を計算
    float a = 0.5 * (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
    if (a == 0)
        cout << "The points lie on the straight line";
    else
        cout << "The points don't lie on the straight line";
}

実行結果

The points are: (20, 9), (6, 13), & (13, 11)
The points lie on the straight line

The points are: (9, 15), (4, 15), & (11, 16)
The points don't lie on the straight line

1回目の実行では、3点 (20, 9)、(6, 13)、(13, 11) から計算した面積がゼロになったため、「同一直線上にある」と判定されています。2回目の実行では面積がゼロでないため、「同一直線上にない」と判定されています。

注意点

座標が整数の場合は上記の判定で問題ありませんが、浮動小数点数を扱う場合は計算誤差により面積が厳密にはゼロにならないことがあります。そのような場合は、面積の絶対値が十分に小さい値(例: 1e-9)未満であるかどうかで判定すると安全です。