具有可变数量的小矩形的最佳拟合矩形，保持长宽比

Question

我需要找到给定的N个子矩形的最佳位置，同时保持父矩形的长宽比。用例如下：-父矩形是一张大图片，假设4000x3000像素（可以重新缩放）。-子矩形为296x128像素（用户的电子墨水显示）

目标是在所有当前显示数量上显示大图（此数字可以从1变为100）

这是一个示例：

可能发生的情况是，小矩形的数量将不适合大矩形的长宽比，就像小矩形的数量是奇数一样，在这种情况下，我认为可以按顺序添加少量（最多5个）备用矩形完成大矩形。

Answer 1

我们的解决方案将始终是矩形，我们已将最大的图片放入其中，以使纵横比保持正确。问题是我们如何种植它们。

在您的示例中，单个显示为296 x 128。 （我假设是长度和高度。）我们缩放为1的图像为170.6 x 128。 （您可以在缩放比例中取出小数像素。）

规则是，无论填充到哪个方向，在所有点上都填充有更多显示，因此我们可以扩展图片。因此，在单一显示解决方案中，我们从1x1矩形变为1x2矩形，现在有了296 x 256。我们的缩放图像现在为296 x 222。

我们的下一个解决方案是2x2显示。这给我们594 x 256，缩放后的图像为321.3 x 256。

接下来，我们将显示2x3。这给了我们594 x 384，而缩放后的显示现在是512 x 384。

由于我们仍然在第二维上达到最大，因此我们接下来转到2x4。这给了我们594 x 512，缩放后的显示为594 x 445.5。依此类推。

对于您的问题，花很长时间就能遍历所有尺寸，直到您拥有多少显示器，而您只是从列表中选取最大的矩形即可。

重要的特殊情况。如果显示矩形和图像的纵横比相同，则必须将这两个尺寸都添加。在图像和显示器具有相同长宽比的情况下，通过正方形可以为您提供1 x 1，2 x 2，3 x 3等。

Answer 2

这似乎是有效的方法（python + opencv）

import cv2
import imutils

def split_image(image, boards_no=25, boards_shape=(128, 296), additional=5):

    # find image aspect ratio
    aspect_ratio = image.shape[1]/image.shape[0]
    print("\nIMAGE INFO:", image.shape, aspect_ratio)

    # find all valid combination of a,b that maximize your available badges
    valid_props = [(a, b) for a in range(boards_no+additional+1) for b in range(boards_no+additional+1) if a*b in [q for q in range(boards_no, boards_no+additional)]]
    print("\nVALID COMBINATIONS", valid_props)

    # find all aspect ratio from previous combination
    aspect_ratio_all = [
        {
            'board_x': a, 
            'board_y': b, 
            'aspect_ratio': (a*boards_shape[1])/(b*boards_shape[0]), 
            'shape': (b*boards_shape[0], a*boards_shape[1]),
            'type': 'h'
        } for (a, b) in valid_props]
    aspect_ratio_all += [
        {
            'board_x': a, 
            'board_y': b, 
            'aspect_ratio': (a*boards_shape[0])/(b*boards_shape[1]), 
            'shape': (b*boards_shape[1], a*boards_shape[0]),
            'type': 'v'
        } for (a, b) in valid_props]

    min_ratio_diff = min([abs(aspect_ratio-x['aspect_ratio']) for x in aspect_ratio_all])
    best_ratio = [x for x in aspect_ratio_all if abs(aspect_ratio-x['aspect_ratio']) == min_ratio_diff][0]
    print("\MOST SIMILAR ASPECT RATIO:", best_ratio)

    # resize image maximining height or width
    resized_img = imutils.resize(image, height=best_ratio['shape'][0])
    border_width = int((best_ratio['shape'][1] - resized_img.shape[1]) / 2)
    border_height = 0

    if resized_img.shape[1] > best_ratio['shape'][1]:
        resized_img = imutils.resize(image, width=best_ratio['shape'][1])
        border_height = int((best_ratio['shape'][0] - resized_img.shape[0]) / 2)
        border_width = 0
    print("RESIZED SHAPE:", resized_img.shape, "BORDERS (H, W):", (border_height, border_width))

    # fill the border with black
    resized_img = cv2.copyMakeBorder(
        resized_img,
        top=border_height,
        bottom=border_height,
        left=border_width,
        right=border_width,
        borderType=cv2.BORDER_CONSTANT,
        value=[0, 0, 0]
    )

    # split in tiles
    M = resized_img.shape[0] // best_ratio['board_y']
    N = resized_img.shape[1] // best_ratio['board_x']
    return [resized_img[x:x+M,y:y+N] for x in range(0,resized_img.shape[0],M) for y in range(0,resized_img.shape[1],N)]

image = cv2.imread('image.jpeg')
tiles = split_image(image)