PythonでX軸・Y軸に平行な正方形を形成する4つの点を見つける方法

この記事では、n個の座標点が与えられたときに、その中から辺がX軸およびY軸に平行な正方形を形成できる4つの点を見つける方法を解説します。条件を満たす正方形が存在しない場合は「不可能」を返します。また、複数の正方形が構成できる場合は、面積が最大になるものを選択します。

問題の例

例として、n = 6、points = [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)] が入力された場合を考えてみましょう。このとき出力されるのは「3」で、正方形を構成する4点は (2, 2)、(5, 2)、(2, 5)、(5, 5) となります。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• まず、すべての点をキーとしたマップ(my_map)を作成し、各点の出現回数を記録します。
• side(一辺の長さ)、x、y を初期値 -1 で初期化します。
• すべての点のペア (i, j) について以下を確認します。
• 2つの点のX座標の差とY座標の差が等しい場合(正方形の対角線となる候補)、残りの2頂点 (points[i].x, points[j].y) と (points[j].x, points[i].y) がマップ内に存在するかどうかをチェックします。
• 4点すべてが存在し、かつ現在記録している side より大きい場合(または同じ長さで条件が良い場合)、その点と辺の長さを更新します。

最後に、side が -1 以外であれば正方形の一辺の長さと4つの頂点を出力し、そうでなければ「該当する正方形なし」と表示します。

実装コード

理解を深めるために、以下のPythonコードをご覧ください。

def get_square_points(points, n):
    my_map = dict()
    for i in range(n):
        my_map[(points[i][0], points[i][1])] = my_map.get((points[i][0], points[i][1]), 0) + 1
    side = -1
    x = -1
    y = -1
    for i in range(n):
        my_map[(points[i][0], points[i][1])] -= 1
        for j in range(n):
            my_map[(points[j][0], points[j][1])] -= 1
            if (i != j and (points[i][0] - points[j][0]) == (points[i][1] - points[j][1])):
                if (my_map[(points[i][0], points[j][1])] > 0 and my_map[(points[j][0], points[i][1])] > 0):
                    if (side < abs(points[i][0] - points[j][0]) or (side == abs(points[i][0] - points[j][0]) and ((points[i][0] * points[i][0] + points[i][1] * points[i][1]) < (x * x + y * y)))):
                        x = points[i][0]
                        y = points[i][1]
                        side = abs(points[i][0] - points[j][0])
            my_map[(points[j][0], points[j][1])] += 1
        my_map[(points[i][0], points[i][1])] += 1
    if (side != -1):
        print("Side:", side)
        print("Points:", (x, y), (x + side, y), (x, y + side), (x + side, y + side))
    else:
        print("No such square")

n = 6
points = [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)]
get_square_points(points, n)

入力

6, [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)]

出力

Side: 3
Points: (2, 2) (5, 2) (2, 5) (5, 5)

まとめ

このアルゴリズムでは、全ての点のペアを調べることで計算量はO(n²)となり、さらにマップによる存在確認を行うことで効率的に正方形を検出できます。対角線上にある2点の組み合わせを見つけ、残りの2頂点が存在するかをハッシュマップで即座に判定するのがポイントです。同サイズの正方形が複数ある場合には、基準点の座標値の二乗和が小さい方を優先することで、決定的な結果を得られるようになっています。