python3 如何过滤如图座标？

Question

如图，点的座标已知，如何过滤出松散的点呢？

就是我只想要每个正方形内只有1到2个点的点。

我能想到用循环遍历比较出来，有什么高效的方案吗？
谢谢

点数据参考:
[ (12, 562), (759, 526), ...]

请不要用numpy以外的工具，blender插件用的，只支持numpy，谢谢

import random

print("#"*55)

verts = []
axis_x = []
axis_y = []

# 数据量万级
for i in range(10000):    
    x = random.randint(0,999)
    y = random.randint(0,999)
    axis_x.append(x)
    axis_y.append(y)
    verts.append( (x, y) )
x_d = max(axis_x)
y_d = max(axis_y)


data = {}

x_c = (x_d // 100) + 1
y_c = (y_d // 100) + 1
for y in range(y_c):
    for x in range(x_c):
        data[(x, y)] = []

for v in verts:
    x = v[0] // 100
    y = v[1] // 100
    k = (x,y)
    if k in data:
        data[k].append(v)


for v in data.values():
    if len(v) in [1,2]:
        print(v)
        

以上代码可用，但怎么实现更高效的方法？

Answer 1

import random
import collections
import matplotlib.pyplot as plt

# 数据量万级
n = 10000

# 随机生成点
points = [(random.randint(0,999), random.randint(0,999)) for _ in range(n)]

# 调整桶的大小为10x10
buckets = collections.defaultdict(lambda: collections.defaultdict(list))

# 分配点到桶
for point in points:
    x, y = point
    buckets[x // 10][y // 10].append(point)

# 过滤桶
filtered_points = []
for bucket in buckets.values():
    for points in bucket.values():
        if 1 <= len(points) <= 2:
            filtered_points.extend(points)

# 提取 x, y 坐标
x_values, y_values = zip(*filtered_points)

# 创建一个新的图表
plt.figure(figsize=(10, 10))

# 绘制点
plt.scatter(x_values, y_values, s=5)

# 设置图表的标题和坐标轴标签
plt.title('Filtered Points')
plt.xlabel('X')
plt.ylabel('Y')

# 显示图表
plt.show()

输出：
([(464, 825),
  (467, 892),
  (469, 849),
  (465, 843),
  (464, 851),
  (469, 863),
  (462, 862),
  (468, 870),
  (461, 886),
  (476, 895)],
 80)

Answer 2

题主的参考代码中给出的区间是 (0,999) ，然而数据是 1000000 ，那再怎么松散也散不干净啊，阈值太小了

试试看k聚类吧，最终 只渲染 代表点应该能满足题主的需求（但是我测试没用那么大数据）

import random
import numpy as np
import matplotlib.pyplot as plt


def k_means(points, k, max_iterations=100):
    num_points = len(points)
    dim = len(points[0])

    # 初始化聚类中心点
    centers = [points[i] for i in np.random.randint(num_points, size=k)]

    for _ in range(max_iterations):
        # 分配每个点到最近的聚类中心点
        clusters = [[] for _ in range(k)]
        for point in points:
            distances = [np.linalg.norm(point - center) for center in centers]
            cluster_idx = np.argmin(distances)
            clusters[cluster_idx].append(point)

        # 更新聚类中心点
        new_centers = [np.mean(cluster, axis=0) for cluster in clusters]

        # 判断聚类中心点是否发生变化
        if np.allclose(centers, new_centers):
            break

        centers = new_centers

    return centers


# 示例数据
points = [(random.uniform(0, 999), random.uniform(0, 999)) for _ in range(5000)]
points = np.array(points)
k = 7
representative_points = k_means(points, k)

# 绘制聚类结果的代表点
colors = ['r', 'g', 'b', 'c', 'm', 'y', '#00acec']  # 每个簇的颜色
plt.figure()

# 绘制每个簇的代表点
for i, center in enumerate(representative_points):
    plt.scatter(center[0], center[1], c=colors[i], label=f'Cluster {i + 1}')

plt.xlabel('X')
plt.ylabel('Y')
plt.title('k-means')
plt.legend()
plt.show()

聚类 k 值越大，划分的也就越精细，下面是上方代码中 5000 个点测试结果

原始数据：

• 我输出元素数据的时候 k 用的默认值 2，和代表点效果会不大一样
  

代表点：

• 渲染代表点时 k 选择了 7，嫌少可以自己增加，注意下方 colors 也要同步增加颜色