Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Note: I'm not going for a theoretically optimal solution here, but just for an approach that produces the correct answer and works fast enough on an input polygon of say 100 vertices. Also, special cases such as an input polygon with holes in it are not considered now. Also, polygons that are not x-monotone* need pre-processing which I won't discuss yet.<br> *Meaning: starting at any leftmost position in P, you can reach any other position by moving up, down or right, but without ever going left. </p> <p><strong>Assumptions</strong><br> As stated in your <a href="https://stackoverflow.com/questions/13399666/java-fit-minimum-amount-of-rectangles-into-polygon"><strong>earlier post</strong></a>, part of the question is in which direction to lay the decking boards (or "rectangles") in order to minimize the number of decking boards used. I will assume that your input polygon P will consist of mostly axis-aligned segments, so that the choice in direction is reduced to either horizontal or vertical. For the remainder, I will assume that a single decking board is always oriented vertically (i.e. runs from top to bottom). For calculating the result with horizontal decking boards, just rotate P by 90 degrees. </p> <p><strong>Problem statement</strong><br> We'll be trying to cover P with decking boards, each with an unlimited length and a maximum width of W. More specifically, we're looking for a coverage that minimizes the total length of all decking boards used. The parts of the used decking boards that fall outside P (i.e. the wastage) cannot be used to cover other parts of P. In order to minimize the wastage, it makes sense to align either the left or the right border of a decking board against a vertex of P, or to place a decking board right next to another decking board. </p> <p><strong>Solution</strong><br> The first step towards this is to partition P into a collection of vertical slabs: take the distinct x-coordinates of all vertices in P and sort them: each pair of consecutive x-coordinates then defines a slab S of P. <img src="https://i.stack.imgur.com/grQgF.gif" alt="Figure 1"></p> <p>Next recognise that, for each slab S, we have 4 possible ways to align the (one or more) decking boards to it:<br> * (SL) Start Left, i.e. align the left side of the decking board with the left side of the slab.<br> * (CL) Continue Left, i.e. continue the pattern of decking boards as determined by the slab to the left of it.<br> * (CR) Continue Right, i.e. continue the pattern of decking boards as determined by the slab to the right of it.<br> * (SR) Start Right, i.e. align the right side of the decking board with the right side of the slab. </p> <p>Hence, if we consider all possible combinations of the 4 alignments for each of the slabs S, we have all the possible decking configurations. Note that not all combinations of alignments are allowed; SL and SR can be used for any slab, but CL can only be used if the slab to the left of it is either SL or CL, and CR can only be used if the slab to the right of it is either SR or CR. </p> <p>-Snip- <em>The problem appears to be significantly different from what is attempted to solve here, so I won't be finishing this post.</em></p>
    singulars
    1. This table or related slice is empty.
    1. POCreate rectangles from an array of Coordinates/Points
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USAstrotrain
    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. CO"More specifically, we're looking for a coverage that minimises the total length of all decking boards used." - Not true, not sure whether this is a mistake or I've read it wrong. We're looking at minimising the amount of pieces used. So instead of using 3 deck boards @ 100 pixels I'd rather use 1 board @ 300 pixels (or whatever unit measurement you want to use). It means less cutting for the staff.
      singulars
      1. PO
      1. UScworner1
    2. COCan you explain why the 3rd slab (starting from the left) is labelled 'SR'. I was under the assumption we were starting from the left side and working our way to the right, in which case it should be labelled 'CR' - to continue right from the previous slab.
      singulars
      1. PO
      1. UScworner1
    3. COYep, the rest I can make sense of. Just so you get a perspective on scale etc... Each slab is going to take a lot more that just one or two deck boards: http://img29.imageshack.us/img29/6349/173zh.jpg This is the old method or drawing manually.
      singulars
      1. PO
      1. UScworner1
 

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