Pythonで凸包を求める方法

凸包というものがあります。
簡単に言うと、散らばった点の外側にある点の集まりです。

これを求めるアルゴリズムがあり、最も簡単なものがギフトラッピング法です。
Pythonで実装してみました。

本体

def wrap(ps):
  # ギフト包装法を使って凸包を求める。
  # 各点[x, y]をリストとして与えると凸包の各点をリストとして返す。
  qs = []
  # 最初の点
  x = [p[0] for p in ps]
  min_i = x.index(min(x))
  qs.append(ps[min_i]) # xが最小になる点をqs[0]とする。
  # 各点
  n = -1
  while True:
    n += 1
    for i in range(len(ps)):
      flag = False
      for p1 in ps:
        if qs[n] == ps[i]:
          flag = True
          break
        result = gaiseki(qs[n], ps[i], p1)
        if result > 0 : # left
          flag = True
          break
      if flag == False:
        this_i = i
    if ps[this_i] == qs[0]:
      break
    qs.append(ps[this_i])
  return qs

外積

外積を使うと、対象となる点が、ある向きに対して右にあるか左にあるかを判定できます。

def gaiseki(moto, saki0, saki1):
  # moto->saki0 の直線に対し saki1がどちら側にあるか
  # >0 ならば 左側 <0 ならば 右側
  x0 = saki0[0] - moto[0]
  y0 = saki0[1] - moto[1]
  x1 = saki1[0] - moto[0]
  y1 = saki1[1] - moto[1]
  gaiseki = x0 * y1 - x1 * y0
  return gaiseki

使い方

import matplotlib.pyplot as plt
def main():
  x = [1, 5, 6, 2, 3, 4]
  y = [1, 2, 6, 7, 3, 5]

  ps = []
  for i in range(len(x)):
    ps.append([x[i], y[i]])

  qs = wrap(ps)

  # 散布図の描画
  plt.scatter(x, y, color = "blue")
  a = []
  b = []
  for q in qs:
    a.append(q[0])
    b.append(q[1])
  a.append(qs[0][0])
  b.append(qs[0][1])
  plt.plot(a, b, linestyle = "solid", color = 'red')
  plt.show()

# def wrap(ps):
# def gaiseki(moto, saki0, saki1):

if __name__ == "__main__":
  main()

コメント

タイトルとURLをコピーしました