CODEWITHSUNDEEP
algorithm
Jake Frederick
Jake Frederick

Reputation: 47

How do I determine the size of an arbitrary number of equal squares to be fit into an fixed size 2D space?

I have a fixed size 2D space that I would like to fill with an arbitrary number of equal sized squares. I'd like an algorithm that determines the exact size (length of one side) that these squares should be in order to fit perfectly into the given space.

Upvotes: 1

Views: 483

Answers (4)

Frank Hagenson
Frank Hagenson

Reputation: 1033

I think this is what you want. At least it solved the problem I was googling for when I found this question.

// 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);
}

Upvotes: 0

Cybercartel
Cybercartel

Reputation: 12592

You want to use a space-filling-curve or a spatial index. A sfc recursivley subdivide the plane into 4 tiles and reduce the 2d complexity to a 1d complexity. You want to look for Nick's hilbert curve quadtree spatial index blog.

Upvotes: 0

ninjagecko
ninjagecko

Reputation: 91122

Notice that there must be an integer number of squares which fill the width and height. Therefore, the aspect ratio must be a rational number.

Input: width(float or int), height(float or int)

Algorithm:

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
}

If the width/height is a rational number, your answer is merely any multiple of the aspect ratio! (e.g. if your aspect ratio was 4/3, you could fill it with 4x3 squares of length width/4=height/3, or 8x6 squares of half that size, or 12x9 squares of a third that size...) If it is not a rational number, your task is impossible.

You convert a fraction to lowest terms by factoring the numerator and denominator, and removing all duplicate factor pairs; this is equivalent to just using the greatest common divisor algorithm GCD(numer,denom) , and dividing both numerator and denominator by that.

Here is an example implementation in 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

e.g.

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

You can tune the optional parameter maxVerticalSquares to give yourself more robustness versus floating-point imprecision (but the downside is the operation may fail), or to avoid a larger number of vertical squares (e.g. if this is architecture code and you are tiling a floor); depending on the range of numbers you are working with, a default value of maxVerticalSquares=500 might be reasonable or something (possibly not even including the exception code).

Once you have this, and a range of desired square lengths (minLength, maxLength), you just multiply:

# 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')

If shrinkFactor is now 2 for example, the new output value in the example would be ((9*2,47*2), 0.25/2).

Upvotes: 4

Agustin Cautin
Agustin Cautin

Reputation: 411

If the sides are integers you need to find the Greatest common divisor between the sides A and B, that is the side of the square that you are looking for.

Upvotes: 0

Related Questions