algorithm - 如何确定任意数量的相等正方形的大小以适应固定大小的二维空间？

Question

我有一个固定大小的二维空间，我想用任意数量的大小相等的正方形填充它。我想要一种算法来确定这些正方形应该完全适合给定空间的确切大小(一侧的长度)。

Answer 1

请注意，必须有整数个正方形来填充宽度和高度。因此，长宽比必须是有理数。

输入:宽度(float 或 int)，height(float 或 int)

算法:

aspectRatio = RationalNumber(width/height).lowestTerms  #must be rational number

# it must be the case that our return values
# numHorizontalSqaures/numVerticalSquares = aspectRatio

return {
    numHorizontalSquares = aspectRatio.numerator,
    numVerticalSquares = aspectRatio.denominator,
    squareLength = width/aspectRatio.numerator
}

如果宽度/高度是有理数，您的答案只是纵横比的任意倍数! (例如，如果您的宽高比是 4/3，您可以用长度 width/4=height/3 的 4x3 正方形填充它，或者用一半大小的 8x6 正方形填充它，或三分之一大小的 12x9 正方形...)如果它不是有理数，则您的任务是不可能完成的。

通过对分子和分母进行因式分解，并删除所有重复的因子对，将分数转换为最低项；这相当于仅使用最大公约数算法 GCD(numer,denom) ，并将分子和分母除以该算法。

这里是 python3 中的示例实现:

from fractions import Fraction
def largestSquareTiling(width, height, maxVerticalSquares=10**6):
    """
        Returns the minimum number (corresponding to largest size) of square
        which will perfectly tile a widthxheight rectangle.

        Return format:
            (numHorizontalTiles, numVerticalTiles), tileLength
    """
    if isinstance(width,int) and isinstance(height,int):
        aspectRatio = Fraction(width, height)
    else:
        aspectRatio = Fraction.from_float(width/height)

    aspectRatio2 = aspectRatio.limit_denominator(max_denominator=maxVerticalSquares)
    if aspectRatio != aspectRatio2:
        raise Exception('too many squares') #optional
    aspectRatio = aspectRatio2

    squareLength = width/aspectRatio.numerator
    return (aspectRatio.numerator, aspectRatio.denominator), squareLength

例如

>>> largestSquareTiling(2.25, 11.75)
((9, 47), 0.25)

您可以调整可选参数 maxVerticalSquares 来让自己比浮点不精确更稳健(但缺点是操作可能会失败)，或者避免大量的垂直方 block (例如，如果这是架构代码，你正在铺地板)；根据您使用的数字范围，maxVerticalSquares=500 的默认值可能是合理的或类似的东西(甚至可能不包括异常代码)。

一旦你有了这个，以及所需的平方长度范围 (minLength, maxLength)，你只需乘以:

# inputs    
desiredTileSizeRange = (0.9, 0.13)
(minHTiles, minVTiles), maxTileSize = largestSquareTiling(2.25, 11.75)

# calculate integral shrinkFactor
shrinkFactorMin = maxTileSize/desiredTileSizeRange[0]
shrinkFactorMax = maxTileSize/desiredTileSizeRange[1]
shrinkFactor = int(scaleFactorMax)
if shrinkFactor<shrinkFactorMin:
    raise Exception('desired tile size range too restrictive; no tiling found')

例如，如果 shr​​inkFactor 现在是 2，则示例中的新输出值将是 ((9*2,47*2), 0.25/2)。