3点から定義される円の内側・外側に点があるか判定するC++プログラム

本記事では、平面上の3つの点 a、b、c によって定義される円に対して、ある点 d がその円の内側にあるのか、外側にあるのかを判定するC++プログラムを紹介します。判定には次の式を使用します。

s = (x - xt)^2 + (y - yt)^2 − r * r

ここで、平面上の任意の点 t (xt, yt) の位置が、3点 (x1, y1)、(x2, y2)、(x3, y3) で定義される円とどのような関係にあるかは、s の値によって以下のように判別できます。

• s < 0 の場合：点 t は円の内側にあります。
• s > 0 の場合：点 t は円の外側にあります。
• s = 0 の場合：点 t は円周上にあります。

アルゴリズム

処理の流れは以下の通りです。

1. 円を定義する3点を入力として受け取ります（サンプルコードでは乱数により生成）。
2. 定数 L = 0、H = 20 を宣言します。
3. 式に必要な変数を宣言します。
4. x および y の係数となる乱数を、コンパイルごとに rand 関数を使って生成します。
5. 円の中心を計算します。
6. 円の半径を計算します。
7. s の値を計算します。
8. s < 0 なら「点は円の内側にある」と出力し、s > 0 なら「点は円の外側にある」と出力し、s = 0 なら「点は円周上にある」と出力します。

サンプルコード

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

using namespace std;
const int L= 0;
const int H = 20;

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

    double x1, x2, y1, y2, x3, y3;
    double a1, a2, c1, c2, r;
    x1 = rand() % (H - L+ 1) + L;
    x2 = rand() % (H - L + 1) + L;
    x3 = rand() % (H- L + 1) + L;
    y1 = rand() % (H- L + 1) + L;
    y2 = rand() % (H- L+ 1) + L;
    y3 = rand() % (H- L + 1) + L;
    a1 = (y1 - y2) / (x1 - x2);
    a2 = (y3 - y2) / (x3 - x2);

    // 円の中心を計算
    c1 = ((a1 * a2 * (y3 - y1)) + (a1 * (x2 + x3)) - (a2 * (x1 + x2))) / (2 * (a1 - a2));
    c2 = ((((x1 + x2) / 2) - c1) / (-1 * a1)) + ((y1 + y2) / 2);
    // 半径を計算
    r = sqrt(((x3 - c1) * (x3 - c1)) + ((y3 - c2) * (y3 - c2)));
    cout << "The points on the circle are: (" << x1 << ", " << y1 << "), (" << x2 << ", " << y2 << "), (" << x3 << ", " << y3 << ")";
    cout << "\nThe center of the circle is (" << c1 << ", " << c2 << ") and radius is " << r;

    cout << "\nEnter the point : ";
    int u, v;
    cin >>u;
    cin >>v;

    // 判定値 s を計算
    double s1 = ((u - c1) * (u - c1)) + ((v - c2) * (v - c2)) - (r * r);
    if (s1 < 0)
        cout << "\nThe point lies inside the circle";
    else if (s1 >0)
        cout << "\nThe point lies outside the circle";
    else
        cout << "\nThe point lies on the circle";
    return 0;
}

実行結果

The points on the circle are: (8, 4), (9, 17), (5, 9)
The center of the circle is (12.6364, 10.8182) and radius is 7.84983
Enter the point : 7
6

The point lies outside the circle

解説

このプログラムでは、まず rand 関数を使って円上の3点の座標をランダムに生成しています。time 関数の戻り値を srand に渡すことで、実行するたびに異なる点列が得られるようになっています。

次に、3点の中点を通る垂直二等分線の交点として円の中心 (c1, c2) を求め、中心から任意の一点までの距離を半径 r として計算しています。これは「円周上のどの点も中心からの距離が等しい」という円の性質を利用した方法です。

最後に、判定したい点 (u, v) を入力として受け取り、(u − c1)² + (v − c2)² − r² を計算します。この値は「点と中心の距離の二乗」と「半径の二乗」の差に相当するため、その符号を見るだけで点が円の内側・外側・円周上のいずれにあるかを効率的に判定できます。距離そのものではなく二乗同士を比較することで、sqrt による計算コストや誤差を避けられるのもこの手法の利点です。