Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>OK, I've asked enough questions, here's something of an answer ...</p> <p>If the data is represented as a raster one algorithm is trivial:</p> <ol> <li>Create a boolean array representing the model (ie Blue) rectangle. Set all elements to FALSE (representing 'not covered')</li> <li>For each Red rectangle (ignore the ones which can't overlap the Blue) set all elements of the array to TRUE if they are inside the Red rectangle.</li> <li>Finally, check whether or not every element of the array has been set TRUE.</li> </ol> <p>If the data is vector it's a little more complicated. First define a function which returns the rectangle representing the intersection (if any) of two rectangles. This is simple. Then proceed:</p> <ol> <li>Create a variable called 'UnCoveredRectangle' which is initialised to be the same as the Blue rectangle.</li> <li><p>Again, only bother with the Red rectangles which intersect the Blue one. For each Red rectangle, compute the intersection of the rectangle with the UnCoveredRectangle. The intersection will result in one of the following situations:</p> <p>2.1 The intersection equals the UnCoveredRectangle. The job is finished.</p> <p>2.2 The intersection 'bites' a rectangular chunk out of the CoveredRectangle. The remaining UnCoveredRectangle will be either a rectangle, an L-shaped piece, or a U-shaped piece. If it is a rectangle itself, set UnCoveredRectangle to be the remaining rectangle, and go to step 2. If the UnCoveredRectangle is L- or U-shaped, split it into 2, or 3, rectangles and recurse from step 2..</p></li> <li><p>If you run out of Red rectangles before the area of (part of) UnCoveredRectangle is sent to 0, you've finished.</p></li> </ol> <p>OK I haven't got a clue about the complexity of this algorithm, but unless the number of rectangles is huge, I'm not too concerned, though perhaps @den is. And I've omitted a lot of details. And I can't draw nice diagrams like @den did, so you'll have to picture it for yourselves.</p>
    singulars
    1. This table or related slice is empty.
    1. PORectangles Covering
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USHigh Performance Mark
    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
    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. VTDownMod
    1. COit is decision, but complexity...
      singulars
      1. PO
      1. USden bardadym
    2. COIf you don't sort the rectangles by position, you have different sorts of results: it can be an `O` (cut to 4), or even `||`, split to two. Sorting also helps, as you can know early the rectangles don't fully cover the area.
      singulars
      1. PO
      1. USKobi
    3. COAs for complexity - basically, you take the model as a polygon (with more than one path - it may be split), and subtract each rectangle. The polygon grows more and more complex, so I believe we're looking at O(N²). The opposite is about that same: you can unite all rectangles, and then add the model and see if it makes a difference.
      singulars
      1. PO
      1. USKobi
 

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