Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <h2>Axis Aligned</h2> <p>Rectangles fit best when they are tiled, with no space between. So, an outline of how to do it:</p> <p>First, figure out how many fit if you just tile them in:</p> <pre><code>lFit = L / l // integer division for these, no remainder wFit = W / w </code></pre> <p>You know that you can fit <code>lFit * wFit</code> rectangles inside if you stack them in the same orientation as the big rectangle. Check again with the other orientation, and choose the bigger one as your base.</p> <p>Now you may have some space left over. That space is made up of rectangles. You can easily find the size of these from the previous step. Run it again for these smaller rectangles and add to the base number. Recurse until no more fit.</p> <p>If no tiles will fit into the "remaining" smaller rectangle, it's time to check for tilted ones.</p> <h2>Diagonal</h2> <p>Once your tile does not fit axis-aligned into the rectangle, you need to tilt it. You can pack the most tiles in by tilting them <em>just</em> enough to fit in the longest box dimension, and placing it firmly against three walls. Then you try stacking more in below it.</p> <p>Note: for all the math here, I'm using <code>width</code> as the "longest edge". If your rectangle/tile doesn't match, just flip the dimensions.</p> <p>To figure out what the proper rotation angle is, you can use a trial/error binary search. I'm sure there's a more "mathy" way to do it, but this works well enough. The formula for the bounding width of a rotated rectangle is(angle in radians):</p> <pre><code>width = w * cos(angle) + h * sin(angle) </code></pre> <p>To do a trial/error, just loop it until you reach your tolerance:</p> <pre><code>// boxWidth, tileWidth, tileHeight public static double getAngle(double bw, double tw, double th){ double err = 10; double maxAngle = PI * 0.25; // 45 degrees, any more would be taller than wide double angle = maxAngle * 0.5; // start in the middle double angleDelta = angle * 0.5; // amount to change; count = 0; while(count++ &lt; 100){ double rotatedWidth = tw * Math.cos(angle) + th * Math.sin(angle); err = rotatedWidth - bw; if(Math.abs(err) &lt; TOLERANCE){ return angle; } else if(err &lt; 0){ angle -= angleDelta; } else { angle += angleDelta; } angleDelta *= 0.5; } return -1; // found no good angle in 100 attempts } </code></pre> <p>Once you have the angle, you can use basic trig to figure out some other points:</p> <ul> <li>Find the lowest y-point of the <em>top</em> edge of the tile where it will be placed. Call this <code>y1</code> <ul> <li><code>y1 = sin(angle) * tileWidth</code></li> </ul></li> <li>Find the lowest point of the <em>left</em> edge of the tile. Call this <code>y2</code> <ul> <li><code>y2 = sin((PI * 0.5) - radians) * tileHeight</code></li> </ul></li> <li>Each added tile will take up <code>y2</code> vertical space, so the number that will fit is: <ul> <li><code>(boxHeight - y1) / y2</code></li> </ul></li> </ul> <p>I created a small <a href="http://ideone.com/QkUn51" rel="nofollow">ideone.com example</a> that you can play with, also. The code is rather ugly, but it works. For your example in comments(<code>13x8, 14x1</code>), it shows:</p> <pre><code>Rotated 26.23397827148437 degrees y1 = 6.188525444904378 y2 = 0.8969959689614577 numTiles = 2 </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POCover large rectangles with identical small rectangles
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USGeobits
    1. USGeobits
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks for your answer, but I think it is not correct. As I have stated in the question, you need not necessarily put the small rectangles in the big one with strictly vertical and/or horizontal orientation. You can, in fact, put them however you like. An example would be, a big rectangle with dimension 13*8, and small one 14*1. You cannot fit even one, either horizontally or vertically. But you can fit two diagonally.
      singulars
      1. PO
      1. USMathCs
    2. COAh, I wasn't thinking diagonally. The only time that would be more efficient(I believe) is when one dimension of the smaller tiles is longer than both dimensions on the larger. Can that be handled as a separate case?
      singulars
      1. PO
      1. USGeobits
    3. COPerhaps yes. It is exactly this case makes the problem challenging.
      singulars
      1. PO
      1. USMathCs
 

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