Группировка и сортировка ящиков (ndarray координат)

Question

У меня есть многомерный массив numpy, содержащий четыре точки (координаты), представляющие поле:

[startX, startY], [endX, startY], [endX, endY], [startX , endY]

Пример:

[[[298.      404.     ]
  [354.      404.     ]
  [354.      430.     ]
  [298.      430.     ]]

 [[358.      404.     ]
  [416.      404.     ]
  [416.      428.     ]
  [358.      428.     ]]

 [[136.      406.     ]
  [190.      406.     ]
  [190.      428.     ]
  [136.      428.     ]]

 [[194.      406.     ]
  [246.      406.     ]
  [246.      430.     ]
  [194.      430.     ]]

 [[422.49792 403.28558]
  [505.2563  408.01465]
  [503.85352 432.56305]
  [421.09515 427.83398]]

 [[246.68146 410.22128]
  [291.68146 407.22128]
  [293.1947  429.92038]
  [248.1947  432.92038]]

 [[234.      436.     ]
  [296.      436.     ]
  [296.      460.     ]
  [234.      460.     ]]

 [[298.      436.     ]
  [342.      436.     ]
  [342.      462.     ]
  [298.      462.     ]]

 [[343.37756 438.08197]
  [455.64294 434.57367]
  [456.55414 463.73267]
  [344.28876 467.24097]]

 [[186.      440.     ]
  [230.      440.     ]
  [230.      464.     ]
  [186.      464.     ]]]

Поскольку каждый блок представляет позицию слова на изображении, я хочу отсортировать эти блоки так, как они будут читаться , Начиная сверху слева и заканчивая снизу справа. Я думал о сортировке ящиков по их начальному значению с помощью:

box_group = box_group[np.argsort(box_group[:, 0, 1])]

Это прекрасно работает. Теперь я должен сгруппировать каждую коробку, которая перекрывает другую по высоте, в одну строку. Я проверяю это следующим образом:

def isOnSameLine(boxOne, boxTwo):
    boxOneStartY = boxOne[0,1]
    boxOneEndY = boxOne[2,1]
    boxTwoStartY = boxTwo[0,1]
    boxTwoEndY = boxTwo[2,1]
    if((boxTwoStartY < boxOneEndY and boxTwoStartY > boxOneStartY)
    or(boxTwoEndY < boxOneEndY and boxTwoEndY > boxOneStartY)):
        return True
    else:
        return False

Имея сгруппированные блоки, которые находятся в одной строке, я могу отсортировать их по значению startX, и это должно быть сделано. Но я понятия не имею, как при этом перебирать все блоки и группировать / сортировать их по строкам. Любые идеи?

Answer 1

Похоже, что lexsort - это все, что вам нужно (возможно, с переворотом x / y):

startY = boxes[:, 0, 1]
startX = boxes[:, 0, 0]
order = np.lexsort([startY, startX])

Answer 2

Это подойдет.

def isOnSameLine(boxOne, boxTwo):
    boxOneStartY = boxOne[0,1]
    boxOneEndY = boxOne[2,1]
    boxTwoStartY = boxTwo[0,1]
    boxTwoEndY = boxTwo[2,1]
    if((boxTwoStartY <= boxOneEndY and boxTwoStartY >= boxOneStartY)
    or(boxTwoEndY <= boxOneEndY and boxTwoEndY >= boxOneStartY)
    or(boxTwoEndY >= boxOneEndY and boxTwoStartY <= boxOneStartY)):
        return True
    else:
        return False

# list of indexes
temp = []
i = 0

# TODO: check if there is more than one box_group
while i < len(box_group):
    for j in range(i + 1, len(box_group)):
        if(isOnSameLine(box_group[i],box_group[j])):
            print(str(i) + " and " + str(j) + " on same line")
            if i not in temp:
                temp.append(i)
            if j not in temp:
                temp.append(j)
        else:
            print(str(i) + " and " + str(j) + " not on same line")
        # append temp with i if the current box (i) is not on the same line with any other box
        if len(temp) == 0:
            temp.append(i)

    # put boxes on same line into lined_box_group array
    lined_box_group = box_group[np.array(temp)]
    # sort boxes by startX value
    lined_box_group = lined_box_group[np.argsort(lined_box_group[:, 0, 0])]
    # copy sorted boxes on same line into sorted_box_group
    sorted_box_group[i:temp[-1]+1] = lined_box_group

    # skip to the index of the box that is not on the same line
    i = temp[-1] + 1
    # clear list of indexes
    temp = []