python - 找到 2D 中最小重叠共享表面

Question

考虑一个以 (0.5, 0.5) 为中心、大小已知 (0.2) 的正方形。我通过在 x 和 y 方向上随机移动原始方 block 一小部分来生成 N 个相同大小的方 block 。

我需要的是找到所有这些方 block 之间的最小重叠区域。这是，我需要它的中心坐标(引用引用正方形)，以及它的高度和宽度。

我已经玩了一段时间了，但我没有找到简单的方法来做到这一点。任何帮助将不胜感激。

---

import numpy as np
from matplotlib import pyplot as plt
from matplotlib.patches import Rectangle
from itertools import cycle

xc, yc = 0.4, 0.4
plt.figure()
currentAxis = plt.gca(aspect='equal')
currentAxis.add_patch(Rectangle((xc, yc), 0.2, 0.2, fill=None, alpha=1, lw=2.))
plt.scatter(0.5, 0.5)
print("Reference square centered at (0.5, 0.5)")

cols = ['r', 'b', 'g', 'm', 'c']
col_cyc = cycle(cols)
for _ in range(4):
    xs, ys = np.random.uniform(-0.1, 0.1, 2)
    print("Square {} shifted by: {:.3f}, {:.3f}".format(_, xs, ys))
    currentAxis.add_patch(
        Rectangle((xc + xs, yc + ys), 0.2, 0.2, fill=None, alpha=1,
                  color=next(col_cyc)))
plt.xlim(0.2, 0.8)
plt.ylim(0.2, 0.8)
plt.show()

Answer 1

给你

import numpy as np
#size of squares
size=0.2

#centers of all squares [x,y]
centers=[[0.5,0.5],
        [0.45,0.45],
        [0.6,0.6]]

centers=np.asarray(centers) #convert to numpy array

left_overlap=centers[::,0].max()-size #left border
right_overlap=centers[::,0].min()+size #right border
bottom_overlap=centers[::,1].max()-size #bottom border
top_overlap=centers[::,1].min()+size #top border

if left_overlap>right_overlap or bottom_overlap>top_overlap:
    print "No overlap"
else:
    x_center_overlap=(left_overlap+right_overlap)/2. #center x
    y_center_overlap=(bottom_overlap+top_overlap)/2. #center y

    print "Center of overlapping area is %s,%s"%(x_center_overlap,y_center_overlap)