python实现凹包的算法

以下是使用Python实现凹包算法的示例代码：

import numpy as np
from scipy.spatial import ConvexHull

def compute_concave_hull(points, alpha):
    # 计算凹包
    hull = ConvexHull(points)
    vertices = hull.vertices
    concave_hull = []

    for i in range(len(vertices)):
        p1 = points[vertices[i]]
        p2 = points[vertices[(i + 1) % len(vertices)]]
        p3 = points[vertices[(i + 2) % len(vertices)]]

        v1 = p2 - p1
        v2 = p3 - p2

        normal = np.cross(v1, v2)
        normal /= np.linalg.norm(normal)

        p4 = p2 + alpha * normal
        concave_hull.append(p4)

    return np.array(concave_hull)

# 示例用法
points = np.array([[0, 0], [1, 0], [1, 1], [0, 1], [0.5, 0.5]])
alpha = 0.1

concave_hull = compute_concave_hull(points, alpha)
print("Concave Hull:")
print(concave_hull)