凸包のPython実装

参考文献

しっかり学ぶ数理最適化　モデルからアルゴリズムまで
梅谷俊治・著
発行 2020/10/23

参考ページ

準備

オンラインコンパイラを使用します。

ソースコード

sample.py

# -*- coding: utf-8 -*-
import numpy as np
import matplotlib.pyplot as plt

def convex_hull(points):
    start = np.argmin(points[:, 1])
    current_point = start
    hull = []

    while True:
        hull.append(current_point)
        next_point = (current_point + 1) % len(points)

        for i in range(len(points)):
            cross_product = np.cross(points[next_point] - points[current_point], points[i] - points[current_point])
            if cross_product > 0:
                next_point = i
        
        current_point = next_point
        
        if current_point == start:
            break

    return hull

np.random.seed(0)
points = np.random.rand(20, 2)
hull_indices = convex_hull(points)
hull_points = points[hull_indices]

plt.scatter(points[:, 0], points[:, 1])
plt.plot(hull_points[:, 0], hull_points[:, 1], 'r--', lw=2)
plt.title('Convex Hull')
plt.show()