Как определить размер произвольного числа равных квадратов, чтобы поместиться в двухмерное пространство фиксированного размера?

Question

У меня есть 2D-пространство фиксированного размера, которое я хотел бы заполнить произвольным числом квадратов одинакового размера.Я хотел бы алгоритм, который определяет точный размер (длина одной стороны), что эти квадраты должны быть для того, чтобы идеально вписаться в данное пространство.

Answer 1

Обратите внимание, что должно быть целое число квадратов, которые заполняют ширину и высоту.Следовательно, соотношение сторон должно быть рациональным числом.

Ввод: width (с плавающей точкой или целым числом), height (с плавающей точкой или целым числом)

Алгоритм:

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, вы можете заполнить его квадратами 4x3 длины width/4 = height/3, или 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, чтобы повысить надежность по сравнению с плавающимнеточность в точках (но недостатком является то, что операция может потерпеть неудачу) или избегать большего числа вертикальных квадратов (например, если это код архитектуры, а вы выкладываете пол);в зависимости от диапазона чисел, с которыми вы работаете, значение по умолчанию 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')

Если shrinkFactor теперь, например, 2, новое выходное значение в примере будет ((9*2,47*2), 0.25/2).

Answer 2

Я думаю, это то, что вы хотите.По крайней мере, это решило проблему, по которой я гуглял, когда нашел этот вопрос.

// width = width of area to fill
// height = height of area to fill
// sqareCount = number of sqares to fill the area with
function CalcSquareSide(float width, float height, int squareCount)
{
  return Math.Sqrt((height * width) / squareCount);
}

Answer 3

Вы хотите использовать кривую заполнения пространства или пространственный индекс. SFC рекурсивный разделить плоскость на 4 плитки и уменьшить 2-й сложности до 1-й сложности. Вы хотите найти блог Ника по пространственному индексу с квадратом кривой Гильберта.

Answer 4

Если стороны целые, вам нужно найти Величайший общий делитель между сторонами A и B, то есть ту сторону квадрата, которую вы ищете.