Bug about box_collision_test

[SubChange]

When using funtions to detect bbox collision, I found:

from utils.process import box_collision_test

bbox = np.array([[[205.73,   6.56],
                        [205.73,   9.36],
                        [214.53,   9.36],
                        [214.53,   6.56]],
                    [[205.75,   6.66],
                        [205.75,   9.36],
                        [214.35,   9.36],
                        [214.35,   6.66]]], dtype=np.float32)
mtx = box_collision_test(bbox, bbox)
print(mtx)

Result

[[False, False],
[False, False]]

I know box[1] overlap with box[2], but the result is False. It would be wonderful if anyone helps to solve this problem, Thank you very much.

[SubChange]

I rewrite this function based on SAT thoery,

def box2d_sat_collision_test(box1, box2):
    # box1: 4 x 2
    boxes = np.vstack((box1, box2)) # 8*2
    
    # 逆时针旋转90度 矩阵
    rot90 = np.array([[0.,1.],[-1.,0.]], dtype=np.float32)
    # 分割线 每一个box的前2条边向量
    line_vec = np.array([box1[1]-box1[0],
                     box1[2]-box1[1],
                     box2[1]-box2[0],
                     box2[2]-box2[1]]) # 4 x 2
    nl = np.sqrt(np.sum(line_vec**2, axis=1))
    line_vec = line_vec / nl[:,None]
    # 旋转90度 得到法向量 也就是投影轴
    nvec = line_vec @ rot90.T # 4x2
    # boxes顶点在投影轴上的坐标
    projL = np.dot(boxes, nvec.T) # 

    x1_min, x1_max = np.min(projL[:4, :], axis=0), np.max(projL[:4, :], axis=0)
    x2_min, x2_max = np.min(projL[-4:, :], axis=0), np.max(projL[-4:, :], axis=0)

    if np.any(x1_min>x2_max) or np.any(x1_max<x2_min):
        return False

    return True

def box_collision_test(boxes, qboxes, clockwise=True, ignore_diag=True):
    """Box collision test.
    Args:
        boxes (np.ndarray): Corners of current boxes. # (n1, 4, 2)
        qboxes (np.ndarray): Boxes to be avoid colliding. # (n2, 4, 2)
        clockwise (bool, optional): Whether the corners are in
            clockwise order. Default: True.
    return: shape=(n1, n2)
    """
    N = boxes.shape[0]
    K = qboxes.shape[0]
    ret = np.zeros((N, K), dtype=np.bool_)
    # slices = np.array([1, 2, 3, 0])
    # lines_boxes = np.stack((boxes, boxes[:, slices, :]),
    #                        axis=2)  # [N, 4, 2(line), 2(xy)] # 新增了一个维度
    # lines_qboxes = np.stack((qboxes, qboxes[:, slices, :]), axis=2)
    # # vec = np.zeros((2,), dtype=boxes.dtype)
    # boxes_standup = bevcorner2alignedbbox(boxes)
    # qboxes_standup = bevcorner2alignedbbox(qboxes)
    for i in range(N):
        for j in range(K):
            if ignore_diag and i==j:
                continue
            ret[i, j] = box2d_sat_collision_test(boxes[i], qboxes[j])
           
    return ret

However, numba can not be used, because I don't familiar with it.

[zhulf0804]

Hi @SubChange, nice implementation based on SAT thoery.

There might be some issues with the handling of collinear cases in the origin code, and I will fix it soon.

Best.