C++で直線が通過する単位正方形の数を求める方法

概要

本記事では、2つの端点 (x1, y1) と (x2, y2) が与えられたときに、その2点を結ぶ直線が通過する単位面積の正方形（マス）の数を求める方法を解説します。

アルゴリズム

直線が通過するマスの数を求めるには、次の値を計算します。

• x座標の差（dx）＝ x2 − x1
• y座標の差（dy）＝ y2 − y1
• 答え ＝ dx + dy − gcd(dx, dy)

つまり、dx と dy の合計から、両者の最大公約数（GCD）を引いた値が求める結果となります。

unitSquares(int x1, int y1, int x2, int y2) 関数は、4つの値 x1、y1、x2、y2 を引数として受け取ります。まず x2 と x1 の絶対差、および y2 と y1 の絶対差をそれぞれ計算します。次に dx と dy を加算し、そこから dx と dy の最大公約数を減算します。計算結果は変数 ans に格納され、main 関数へ返されて出力されます。

int unitSquares(int x1, int y1, int x2, int y2){
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
    int ans = dx + dy - __gcd(dx, dy);
    return ans;
}

実装例

それでは、直線が通過する単位面積の正方形の数を求める具体的な実装例を見てみましょう。

#include<iostream>
#include <algorithm>
using namespace std;
int unitSquares(int x1, int y1, int x2, int y2){
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
    int ans = dx + dy - __gcd(dx, dy);
    return ans;
}
int main(){
    int x1 = 3, y1 = 3, x2 = 12, y2 = 6;
    cout<<"この直線は "<<unitSquares(x1, y1, x2, y2)<<" 個の正方形を通過します";
    return 0;
}

出力

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

この直線は 9 個の正方形を通過します