Pythonで多角形の外周（周囲長）を求めるプログラム

問題の概要

2次元平面上にある単純な多角形（自己交差しないポリゴン）の頂点が、順序付きの点のリストとして与えられているとします。このとき、その多角形の外周（周囲長）を求めることが目的です。

例として、入力が points = [(0, 0), (0,5), (3, 5), (3,0)] の場合を考えてみましょう。このときの出力は 16 になります。

これは、図からも分かるように、長さ3の辺が2本、長さ5の辺が2本存在するためです。したがって、2×5 + 2×3 = 16 となります。

アルゴリズムの考え方

この問題は、「隣接する2つの頂点間の距離をすべて計算して合計する」というシンプルなアプローチで解くことができます。具体的な手順は以下の通りです。

• 2点間の距離を計算する関数 getInfo() を定義します。引数は x1, y1, x2, y2 です。
• ((x1−x2)*(x1−x2)+(y1−y2)*(y1−y2)) の平方根を返します。これが (x1, y1) と (x2, y2) の間のユークリッド距離です。
• メインの処理では以下を実行します。
• N := 点のリストのサイズ（頂点数）
• (firstx, firsty) := points[0]（最初の頂点を保存）
• (prevx, prevy) := (firstx, firsty)
• res := 0（外周の合計値を初期化）
• i を 1 から N−1 までループ：
  • (nextx, nexty) := points[i]
  • res := res + getInfo(prevx, prevy, nextx, nexty)
  • prevx := nextx、prevy := nexty
• 最後に、最後の頂点から最初の頂点へ戻る辺の距離も加算：res := res + getInfo(prevx, prevy, firstx, firsty)
• res を返す

実装例

理解を深めるために、以下の実装例を見てみましょう。

from math import sqrt
def getInfo(x1, y1, x2, y2):
   return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))

def solve(points):
   N = len(points)
   firstx, firsty = points[0]
   prevx, prevy = firstx, firsty
   res = 0

   for i in range(1, N):
      nextx, nexty = points[i]
      res = res + getInfo(prevx,prevy,nextx,nexty)
      prevx = nextx
      prevy = nexty
   res = res + getInfo(prevx,prevy,firstx,firsty)
   return res

points = [(0, 0), (0,5), (3, 5), (3,0)]
print(solve(points))

入力

[(0, 0), (0,5), (3, 5), (3,0)]

出力

16.0

コードのポイント

このアルゴリズムの計算量は O(N) であり、頂点数に比例して処理時間が増加します。実装上の注意点は次の2つです。

• 閉じるための辺を忘れないこと：ループでは「隣接する頂点間」の距離しか計算していないため、最後にもう一度 getInfo() を呼び出して、最後の頂点から最初の頂点へ戻る辺の長さを加算する必要があります。
• 浮動小数点数の扱い：sqrt() の返り値は float 型になるため、出力は整数の 16 ではなく 16.0 と表示されます。

このように、頂点の座標リストさえあれば、ユークリッド距離の累積だけで簡単に任意の多角形の外周を求めることができます。