【C言語】ヘロンの公式を使って三角形を面積順にソートする方法

異なる三角形の配列があり、triangles[i] = [ai, bi, ci] が i 番目の三角形の3辺を表していると仮定します。これらの三角形を、それぞれの面積に基づいて昇順にソートする必要があります。3辺の長さから面積を求めるには、有名な「ヘロンの公式」を利用します。

ヘロンの公式による面積の計算方法

3辺 a、b、c を持つ三角形の面積は、次の式で求められます。

面積 = √( p × (p-a) × (p-b) × (p-c) )　※ p = (a+b+c)/2

ここで p は半周長（3辺の合計の半分）を表します。

入出力の例

たとえば、入力が (7, 24, 25)、(5, 12, 13)、(3, 4, 5) の場合、出力は次のようになります。

(3, 4, 5)
(5, 12, 13)
(7, 24, 25)

アルゴリズムの手順

この問題は、次の手順で解決できます。

• 辺 a、b、c をメンバに持つ Triangle 構造体を定義する
• 三角形 t を引数に受け取る関数 square() を定義する
• 関数内で a := t.a、b := t.b、c := t.c とする
• (a+b+c) × (a+b-c) × (a-b+c) × (-a+b+c) を戻り値として返す
• main 関数では、二重ループですべてのペアを比較し、面積が大きければ要素を交換する

ポイントは、square() 関数が平方根を計算していないことです。上記の式はヘロンの公式のルートの中身、つまり「面積の2乗」に相当します。面積の大小関係は2乗しても変わらないため、平方根の計算を省略すれば、浮動小数点演算による誤差や処理コストを気にせず、整数演算だけで正確かつ高速に比較できます。

C言語による実装例

理解を深めるために、実際のコードを見てみましょう。

#include <stdio.h>
#define N 3
struct Triangle{
    int a, b, c;
};
int square(struct Triangle t){
    int a = t.a, b = t.b, c = t.c;
    return (a + b + c)*(a + b - c)*(a - b + c)*(-a + b + c);
}
void solve(struct Triangle* a){
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            if (square(a[i]) > square(a[j])){
                struct Triangle temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
}
int main(){
    struct Triangle triangles[N] = {{7, 24, 25}, {5, 12, 13}, {3, 4, 5}};
    solve(triangles);
    for (int i = 0; i < N; i++){
        printf("(%d, %d, %d)\n", triangles[i].a, triangles[i].b, triangles[i].c);
    }
}

入力

{{7, 24, 25}, {5, 12, 13}, {3, 4, 5}}

出力

(3, 4, 5)
(5, 12, 13)
(7, 24, 25)

まとめ

本記事では、ヘロンの公式を整数演算の形に工夫することで、浮動小数点数を使わずに三角形を面積順にソートする方法を解説しました。ソート部分は計算量 O(N²) の単純なアルゴリズムですが、データ件数が少ない場合には十分に実用的です。より大きなデータセットを扱う際には、標準ライブラリの qsort 関数などへの置き換えも検討するとよいでしょう。