C++で学ぶ線と点の双対変換：実装プログラムと解説

本記事では、線と点の双対変換（Duality Transformation）を示すC++プログラムを紹介します。双対変換とは、平面上の点と直線を互いに対応付ける変換であり、計算幾何学において重要な概念です。この変換には、次の2つの場合が存在します。

双対変換の2つのケース

• ケース1： 点 (a, b) を直線 y = ax − b へ変換する
• ケース2： 直線 D（y = cx + d）を点 D’(c, −d) へ変換する

この対応関係により、点に関する問題を直線に関する問題へ（あるいはその逆へ）置き換えて考えることが可能になります。

関数と擬似コード

関数 LineTransformation(double c, double d)

直線の係数を受け取り、対応する点の座標を出力します。

Print C: (d / c)
D: (d * -1)

関数 PointTransformation(double x, double y)

点の座標を受け取り、対応する直線の式を出力します。

Print a = (-1 * y / x)
b = (-1 * y)

C++による実装例

以下は、ユーザーが「直線→点」または「点→直線」のどちらかの変換を選択できる完全なサンプルコードです。

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

// 直線を点へ変換する関数
void LineTransformation(double c, double d) {
   cout << "C: " << (d / c) << ", D: " << (d * -1);
}

// 点を直線へ変換する関数
void PointTransformation(double x, double y) {
   cout << "y=" << (-1 * y / x) << "x +" << (-1 * y);
}

int main(int argc, char **argv) {
   cout << "\n1. Line Transformation\n2. Point Transformation";
   int c;
   cin >> c;
   switch (c) {
      case 1:
         cout << "Enter the coefficients of line y=ax-b:";
         double a, b;
         cin >> a >> b;
         LineTransformation(a, b);
         break;
      case 2:
         cout << "Enter the coordinate of point <a, b>";
         double x, y;
         cin >> x >> y;
         PointTransformation(x, y);
         break;
      default:
         break;
   }
}

実行結果

ケース1：直線から点への変換

1. Line Transformation
2. Point Transformation
1
Enter the coefficients of line y=ax-b:
1
2
C: 2, D: -2

直線 y = x − 2 を入力すると、対応する点 (2, −2) が出力されます。

ケース2：点から直線への変換

1. Line Transformation
2. Point Transformation
2
Enter the coordinate of point <a, b>
1
2
y=-2x +-2

点 (1, 2) を入力すると、対応する直線 y = −2x − 2 が出力されます。

まとめ

このように、双対変換を用いることで点と直線を簡単に相互変換できます。計算幾何学のアルゴリズム（例えば、凸包やボロノイ図の問題）では、双対性を利用することで問題を別の視点から捉え、解法を単純化できる場合があります。ぜひ本サンプルコードを参考に、実際に動かして挙動を確認してみてください。