Create a rectangle net/list from 2D Points in python

Question

I have a series of points that are to be sorted into adjacent squares so that a mesh is created.

is there maby anything comparable to the Delaunay triangulation?

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

Apologies for the incomplete answer and the lack of an explanation. (I have an appointment.)

This code prints a set of points for each rectangle but NOT in the correct order:

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)

Output:

[[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]]

The correct order for th2 first line above is:

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