Python超矩形

Rectangle是 scipy.spatial中封装的类，其构造函数只需输入最小值和最大值的数组即可，并且可通过内置的 volume方法计算广义的体积。

from scipy.spatial import Rectanglerec = Rectangle((0,0), (5,5))
print(rec.maxes)    # [5. 5.]
print(rec.mins)     # [0. 0.]
print(rec.volume()) # 25
rec3 = Rectangle((0,0,0), (5,5,5))
print(rec3.volume())    # 125

距离函数

通过min_distance_point/max_distance_point可以计算某点到矩形内部的最近/最远距离

print(rec.min_distance_point((3,3)))
# 0.0
print(rec.max_distance_point((3,3)))
# 4.242640687119285

由于(3,3)在矩形内部，所以最小距离为0；而最大距离则位于(0,0)处。

通过min_distance_rectangle/max_distance_rectangle方法可以计算一个矩形和另一个矩形之间的最小/最大距离

rec2 = Rectangle((5,5),(10,10))
rec.max_distance_rectangle(rec2, 2)
# 14.142135623730951
rec.min_distance_rectangle(rec2, 2)
# 0.0

由于两个矩形存在交点，所以最近距离为0，而最远距离则在(0,0), (10,10)之间。

这4个距离函数均采用闵可夫斯基距离的定义，默认阶数为2，通过第二个参数p，可以修改距离的定义。对于点$x,y$而言，具体的距离公式为

$$d_p=\sqrt[p]{\sum _i|x_i-y_i{|}^p}$$

>>> rec.max_distance_point((3,3),1)
6.0

当p=1时，表示曼哈顿距离，即${\sum }_i|x_i-y_i|$，对于$(0,0)$到$(3,3)$来说就是$3+3=6$。

矩形分割

通过split，可以对矩形进行分割，其输入参数有2，分别是分割所在坐标轴，以及该坐标轴处的刻度，效果如下

rec.split(0, 2)
(<Rectangle [(0.0, 2.0), (0.0, 5.0)]>, <Rectangle [(2.0, 5.0), (0.0, 5.0)]>)

由于Rectangle定义的超矩形可以有不同的维度，换言之，一维的矩形就是线段，三维的矩形就是立方体。一旦接受了这种设定，那么矩形分割就可以理解为线段分割，或者立方体分割。有了这个，就可以更加便捷地进行非线性寻优了。

在scipy.optimize中，提供了DIRECT算法，运用的就是这种思想。

而在点云处理中使用更加频繁的八叉树，则是矩形分割更加直观的案例，open3d中实现了这种算法，以二维超矩形为例，则其运算流程可理解为四叉树。

仍以六个数据点作为研究对象：{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}，如果以$[0,10)$为坐标空间，那么通过对这个空间四等分，可得到下左图

	=》

令所有的分割都是左闭右开的，那么被分割后的四个区间中，除了右下角的方块包含三个点之外，剩下三个方块都只有一个点。只有一个点的方块显然就没法继续分割了，而第四个方块则可继续分割，得到右图。

这样，右下角的方块被继续分成了四个小方块，且每个小方块的元素都不超过一个，所以无法继续再分，四叉树也就完成了。