Question

Determine optimal tiling

jdh
Rank
Badge +22
  • jdh Contributor
  • Contributor
  • 1959 replies

I have an arbitrary rectangle I need to subdivide into equal tiles. I would like to optimise the number of tiles according to the following constraints in order of priority:

 

  • The original rectangle will always be an integer number of units
  • The maximum area of the tile is 12 units squared
  • All tiles should be equal in dimensions
  • Preference for compact tiles (closer to square)
  • Preference for tiles to be 8-9 units squared
  • Preference for tiles to be integer units
  • Preference for fewer tiles

Thoughts on how to calculate the number of horizontal and vertical tiles given the size of the original rectangle?

3 replies

takashi
Rank
Userlevel 2
Badge +17

Hi @jdh, if I understood the requirements correctly, this Python script could determine the optimal tiling parameters according to the constraints.

# PythonCaller Script Example
def determineOptimalTiling(feature):
    # Width/Height of the original rectangle.
    width = float(feature.getAttribute('_width'))
    height = float(feature.getAttribute('_height'))
    
    # List of all possible numbers of columns/rows for tiling.
    columns = [c for c in range(1, int(width) + 1)]
    rows = [r for r in range(1, int(height) + 1)]
    
    # Collect every set of tiling parameters that satisfies these constraints.
    # - The maximum area of the tile is 12 units squared
    # - All tiles should be equal in dimensions
    tilingParams = []
    for c in columns:
        w = width / c
        for r in rows:
            h = height / r
            a = w * h
            if a <= 12:
                tilingParams.append({
                    'width' : w,
                    'height' : h,
                    'area' : a,
                    'columns' : c,
                    'rows' : r,
                })
                
    # Sort the list of tiling parameters in the order of other constraints.
    tilingParams.sort(key=lambda p: (
        abs(p['width'] / p['height'] - 1.0), # compact tiles (closer to square)
        0 if (8 <= p['area'] and p['area'] <= 9) else 1, # tiles to be 8-9 units squared
        0 if (p['area'] == round(p['area'])) else 1, # tiles to be integer units
        p['columns'] * p['rows'], # fewer tiles
    ))    
    
    # Determine the first element in the sorted list as the optimal tiling parameters.
    feature.setAttribute('_num_columns', tilingParams[0]['columns'])
    feature.setAttribute('_num_rows', tilingParams[0]['rows'])
jdh
Rank
Badge +22

Hi @jdh, if I understood the requirements correctly, this Python script could determine the optimal tiling parameters according to the constraints.

# PythonCaller Script Example
def determineOptimalTiling(feature):
    # Width/Height of the original rectangle.
    width = float(feature.getAttribute('_width'))
    height = float(feature.getAttribute('_height'))
    
    # List of all possible numbers of columns/rows for tiling.
    columns = [c for c in range(1, int(width) + 1)]
    rows = [r for r in range(1, int(height) + 1)]
    
    # Collect every set of tiling parameters that satisfies these constraints.
    # - The maximum area of the tile is 12 units squared
    # - All tiles should be equal in dimensions
    tilingParams = []
    for c in columns:
        w = width / c
        for r in rows:
            h = height / r
            a = w * h
            if a <= 12:
                tilingParams.append({
                    'width' : w,
                    'height' : h,
                    'area' : a,
                    'columns' : c,
                    'rows' : r,
                })
                
    # Sort the list of tiling parameters in the order of other constraints.
    tilingParams.sort(key=lambda p: (
        abs(p['width'] / p['height'] - 1.0), # compact tiles (closer to square)
        0 if (8 <= p['area'] and p['area'] <= 9) else 1, # tiles to be 8-9 units squared
        0 if (p['area'] == round(p['area'])) else 1, # tiles to be integer units
        p['columns'] * p['rows'], # fewer tiles
    ))    
    
    # Determine the first element in the sorted list as the optimal tiling parameters.
    feature.setAttribute('_num_columns', tilingParams[0]['columns'])
    feature.setAttribute('_num_rows', tilingParams[0]['rows'])
Hi Takashi,

 

 

This gives me a very good starting point, though I think the constraints will have to be weighted, and then sorted to avoid cases like 5x5  being divided into 25 tiles.

 

 

I also assume that line 32 should be 0 if (8 >= p['area'] and p['area'] <= 9) else 1,

 

 

 

takashi
Rank
Userlevel 2
Badge +17

Hi @jdh, if I understood the requirements correctly, this Python script could determine the optimal tiling parameters according to the constraints.

# PythonCaller Script Example
def determineOptimalTiling(feature):
    # Width/Height of the original rectangle.
    width = float(feature.getAttribute('_width'))
    height = float(feature.getAttribute('_height'))
    
    # List of all possible numbers of columns/rows for tiling.
    columns = [c for c in range(1, int(width) + 1)]
    rows = [r for r in range(1, int(height) + 1)]
    
    # Collect every set of tiling parameters that satisfies these constraints.
    # - The maximum area of the tile is 12 units squared
    # - All tiles should be equal in dimensions
    tilingParams = []
    for c in columns:
        w = width / c
        for r in rows:
            h = height / r
            a = w * h
            if a <= 12:
                tilingParams.append({
                    'width' : w,
                    'height' : h,
                    'area' : a,
                    'columns' : c,
                    'rows' : r,
                })
                
    # Sort the list of tiling parameters in the order of other constraints.
    tilingParams.sort(key=lambda p: (
        abs(p['width'] / p['height'] - 1.0), # compact tiles (closer to square)
        0 if (8 <= p['area'] and p['area'] <= 9) else 1, # tiles to be 8-9 units squared
        0 if (p['area'] == round(p['area'])) else 1, # tiles to be integer units
        p['columns'] * p['rows'], # fewer tiles
    ))    
    
    # Determine the first element in the sorted list as the optimal tiling parameters.
    feature.setAttribute('_num_columns', tilingParams[0]['columns'])
    feature.setAttribute('_num_rows', tilingParams[0]['rows'])
Since the constraint "Preference for tiles to be integer units" has higher priority than the constraint "Preference for fewer tiles", cases like 5x5 being divided into 25 tiles cannot be avoided. However, if you replaced the line 32 with this expression, you might get a better result.

 

"Preference for tiles to be 8-9 units squared or closer to the range"
0 if (8 <= p['area'] and p['area'] <= 9) else max(8 - p['area'], p['area'] - 9)

 

Reply


Community Stats

28,670
Posts
109,366
Replies
36,531
Members
Terms & ConditionsCookie settings
A product of
Safe Software respectfully acknowledges that we live, learn and work on the traditional and unceded territories of the Kwantlen, Katzie, and Semiahmoo First Nations.