基于Lloyd算法生成Voronoi 图形的python代码
时间: 2024-05-03 18:19:48 浏览: 11
以下是基于Lloyd算法生成Voronoi图形的Python代码:
```python
import random
import numpy as np
import matplotlib.pyplot as plt
# 生成随机点
def generate_points(n, minval, maxval):
return [(random.uniform(minval, maxval), random.uniform(minval, maxval)) for _ in range(n)]
# 计算欧几里得距离
def distance(p1, p2):
return np.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
# 寻找每个点的最近邻
def nearest_neighbor(p, points):
min_dist = float("inf")
for i, point in enumerate(points):
if distance(p, point) < min_dist:
min_dist = distance(p, point)
index = i
return index
# 计算每个点的重心
def calculate_centroid(points):
x = [p[0] for p in points]
y = [p[1] for p in points]
centroid_x = sum(x) / len(points)
centroid_y = sum(y) / len(points)
return (centroid_x, centroid_y)
# Lloyd算法生成Voronoi图形
def lloyd_algorithm(points, n_iterations):
# 初始化中心点
centroids = points[:3]
# 迭代更新中心点
for i in range(n_iterations):
cell_points = [[] for _ in range(len(centroids))]
# 分配点到最近的中心点
for p in points:
index = nearest_neighbor(p, centroids)
cell_points[index].append(p)
# 计算每个中心点的重心
centroids = [calculate_centroid(cell) for cell in cell_points]
return centroids, cell_points
# 绘制Voronoi图形
def plot_voronoi(centroids, cell_points):
for i, cell in enumerate(cell_points):
x = [p[0] for p in cell]
y = [p[1] for p in cell]
plt.scatter(x, y)
plt.scatter(centroids[i][0], centroids[i][1], c='r')
plt.show()
# 测试代码
points = generate_points(100, -10, 10)
centroids, cell_points = lloyd_algorithm(points, 10)
plot_voronoi(centroids, cell_points)
```
代码中,`generate_points`函数生成指定数量的随机点,`distance`函数计算两个点之间的欧几里得距离,`nearest_neighbor`函数寻找每个点的最近邻,`calculate_centroid`函数计算每个点的重心。`lloyd_algorithm`函数是Lloyd算法的实现,它迭代更新中心点,直到收敛。最后,`plot_voronoi`函数绘制Voronoi图形。