Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Let <code>W</code> and <code>H</code> be the width and height of the rectangle.</p> <p>Let <code>s</code> be the length of the side of a square.</p> <p>Then the number of squares <code>n(s)</code> that you can fit into the rectangle is <code>floor(W/s)*floor(H/s)</code>. You want to find the maximum value of <code>s</code> for which <code>n(s) &gt;= N</code></p> <p>If you plot the number of squares against <code>s</code> you will get a piecewise constant function. The discontinuities are at the values <code>W/i</code> and <code>H/j</code>, where <code>i</code> and <code>j</code> run through the positive integers.</p> <p>You want to find the smallest <code>i</code> for which <code>n(W/i) &gt;= N</code>, and similarly the smallest <code>j</code> for which <code>n(H/j) &gt;= N</code>. Call these smallest values <code>i_min</code> and <code>j_min</code>. Then the largest of <code>W/i_min</code> and <code>H/j_min</code> is the <code>s</code> that you want. </p> <p>I.e. <code>s_max = max(W/i_min,H/j_min)</code></p> <p>To find <code>i_min</code> and <code>j_min</code>, just do a brute force search: for each, start from 1, test, and increment. </p> <p>In the event that N is very large, it may be distasteful to search the <code>i</code>'s and <code>j</code>'s starting from 1 (although it is hard to imagine that there will be any noticeable difference in performance). In this case, we can estimate the starting values as follows. First, a ballpark estimate of the area of a tile is <code>W*H/N</code>, corresponding to a side of <code>sqrt(W*H/N)</code>. If <code>W/i &lt;= sqrt(W*H/N)</code>, then <code>i &gt;= ceil(W*sqrt(N/(W*H)))</code>, similarly <code>j &gt;= ceil(H*sqrt(N/(W*H)))</code></p> <p>So, rather than start the loops at <code>i=1</code> and <code>j=1</code>, we can start them at <code>i = ceil(sqrt(N*W/H))</code> and <code>j = ceil(sqrt(N*H/W)))</code>. And OP suggests that <code>round</code> works better than <code>ceil</code> -- at worst an extra iteration. </p> <p>Here's the algorithm spelled out in C++:</p> <pre><code>#include &lt;math.h&gt; #include &lt;algorithm&gt; // find optimal (largest) tile size for which // at least N tiles fit in WxH rectangle double optimal_size (double W, double H, int N) { int i_min, j_min ; // minimum values for which you get at least N tiles for (int i=round(sqrt(N*W/H)) ; ; i++) { if (i*floor(H*i/W) &gt;= N) { i_min = i ; break ; } } for (int j=round(sqrt(N*H/W)) ; ; j++) { if (floor(W*j/H)*j &gt;= N) { j_min = j ; break ; } } return std::max (W/i_min, H/j_min) ; } </code></pre> <p>The above is written for clarity. The code can be tightened up considerably as follows:</p> <pre><code>double optimal_size (double W, double H, int N) { int i,j ; for (i = round(sqrt(N*W/H)) ; i*floor(H*i/W) &lt; N ; i++){} for (j = round(sqrt(N*H/W)) ; floor(W*j/H)*j &lt; N ; j++){} return std::max (W/i, H/j) ; } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithm for maximizing coverage of rectangular area with scaling tiles
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USbrainjam
    1. USbrainjam
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POAlgorithm for maximizing coverage of rectangular area with scaling tiles
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO@Kendall, is there any reason this solution doesn't work for you?
      singulars
      1. PO
      1. USbrainjam
    2. CO@brainjamin, can you run it on one example for us? If the optimal i is different from the optimal j, than s is different from s. But if W >> H this is obviously the case. So I think your method is contradictory.
      singulars
      1. PO
      1. USpiccolbo
    3. CO@piccolbo, I've edited the last part of the answer to try to clarify the algorithm .. I've introduced i_min, j_min, s_max to distinguish the actual extrema.
      singulars
      1. PO
      1. USbrainjam
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload