C++で3つの点が同一直線上にあるかどうかを判定するプログラム

3つの異なる座標を持つ点が与えられ、それらの点が同一直線上に並んでいるかどうか(共線性・コリニア)を判定するのが本記事のテーマです。

3つの点がすべて同じ直線上に乗っている場合、これらの点は「共線(collinear)」であるといいます。逆に、異なる直線上に配置されている場合は共線ではありません。以下の図は、共線な点と共線でない点の違いを示したものです。

入力例と出力例

入力1

x1 = 1, x2 = 2, x3 = 3, y1 = 1, y2 = 4, y3 = 5

出力1

no points are not collinear

入力2

x1 = 1, y1 = 1, x2 = 1, y2 = 4, x3 = 1, y3 = 5

出力2

points are collinear

判定に使うアプローチ

3点が同一直線上にあるかどうかは、「三角形の面積」を利用して簡単に判定できます。3点が同一直線上にあれば、その3点を頂点とする三角形の面積は0になるためです。

• 点を (x1, y1)、(x2, y2)、(x3, y3) として入力します

• 三角形の面積を求める公式 x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2) を適用します

• 以下の条件で判定します

  • 計算結果が 0 の場合 → 点は共線(同一直線上)であると表示

  • 計算結果が 0 以外の場合 → 点は共線ではないと表示

• 最終的な結果を出力します

アルゴリズム

Start
Step 1→ 点が共線かどうかを判定する関数を宣言する
    void check_collinear(int x1, int y1, int x2, int y2, int x3, int y3)
        int a = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2) を宣言
        IF (a == 0)
            "yes points are collinear" を出力
        End
        Else
            "no points are not collinear" を出力
Step 2→ main() 内での処理
    int x1 = 1, x2 = 2, x3 = 3, y1 = 1, y2 = 4, y3 = 5 を宣言
    check_collinear(x1, y1, x2, y2, x3, y3) を呼び出す
Stop

C++による実装例

#include <bits/stdc++.h>
#include <math.h>
#include <stdlib.h>
using namespace std;
//点が共線かどうかを判定する関数
void check_collinear(int x1, int y1, int x2, int y2, int x3, int y3){
    int a = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
    if (a == 0)
        cout << "yes points are collinear";
    else
        cout << "no points are not collinear";
}
int main(){
    int x1 = 1, x2 = 2, x3 = 3, y1 = 1, y2 = 4, y3 = 5;
    check_collinear(x1, y1, x2, y2, x3, y3);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

no points are not collinear

このように、三角形の面積が0になるかどうかを確認するだけで、3つの点が同一直線上にあるかどうかを効率よく判定できます。幾何学計算の基礎として、ぜひ活用してください。