python - 在 python 中从 2D 点创建一个矩形网络/列表

Question

我有一系列点，需要将它们分类到相邻的正方形中，以便创建网格。

是否有任何东西可以与 Delaunay 三角测量相媲美？

Picture from input points in blue and goal in red

import numpy as np
import matplotlib.pyplot as plt

points_2D = np.array([[2,2],[3,2],[5,2],[7,2],[8,2],[10,2],[2,4],[3,5],[5,4],[7,3],[8,4],[10,5],[2,7],[4,7],[5,7],[6,7],[8,6],[9,7],])

def find_rectangle(points):
    pass
    # return somthing like np.array([rectangle_number][
    # [x,y],
    # [x,y],
    # [x,y],
    # [x,y],
    # ])

#points_2D = find_rectangle(points_2D)

plt.scatter(points_2D[:,0], points_2D[:,1])
plt.show()

Answer 1

对于不完整的答案和缺乏解释表示歉意。 (我有预约。)

此代码为每个矩形打印一组点，但顺序不正确:

import numpy as np
import  itertools

points_2D = np.array([[2,2],[3,2],[5,2],[7,2],[8,2],[10,2],[2,4],[3,5],[5,4],[7,3],[8,4],[10,5],[2,7],[4,7],[5,7],[6,7],[8,6],[9,7],])

def rectangles(x1, x2, s1, s2):
    inter = s1.intersection(s2)
    if len(inter) > 1:
        comb = list(itertools.combinations(inter, 2))
        for c in comb:
            prod = itertools.product([x1, x2], list(c))
            res = [list(p) for p in prod]
            print(res)

def find_rectangle(points):
    psorted = points[points[:,0].argsort()]
    px = list(np.unique(psorted[:,0]))
    ypoints = np.split(psorted[:,1], np.unique(psorted[:, 0], return_index=True)[1][1:])
    sets = [set(list(arr)) for arr in ypoints]
    for i in range(len(px)):
        for j in range(i+1, len(px)):
            rectangles(px[i], px[j], sets[i], sets[j])

find_rectangle(points_2D)

输出:

[[2, 2], [2, 4], [5, 2], [5, 4]]
[[2, 2], [2, 7], [5, 2], [5, 7]]
[[2, 4], [2, 7], [5, 4], [5, 7]]
[[2, 2], [2, 4], [8, 2], [8, 4]]
[[3, 2], [3, 5], [10, 2], [10, 5]]
[[5, 2], [5, 4], [8, 2], [8, 4]]

上面 th2 第一行的正确顺序是:

[[2, 2], [2, 4], [5, 4], [5, 2]]