Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Here's a generic algorithm</p> <ol> <li>is there any rectangle covering the whole model?<br> if yes you are done </li> <li>if no are there any rectangles partially covering the model?<br> if yes </li> <li>is the union of all the intersections of rectangle and model equal to the model<br> if 2. or 3. is no then the answer is no, otherwise it is yes </li> </ol> <p>Now the question is how to do the above efficiently. The above can be done in a single loop over all polygons, so I think you are looking at O(n) time.</p> <p>If you need to create efficient algorithm that will test multiple models, or if you must optimize for fastest answer possible (at the expense of preparing the data) then you are looking for a structure that will allow quick answer to question if a rectangle intersects (or contains) a rectangle.</p> <p>If you use, for example <a href="http://en.wikipedia.org/wiki/Interval_tree" rel="nofollow noreferrer">kd-trees</a>, I believe that this can be answered in O(log n) time - but the important variable in this algorithm is also the number of found rectangles k. You will end up with something like O(k + log n) and you will also need to do the union part to test if the model is covered.</p> <p>My guess is that the union could be computed in O(k log k), so if k is small then you are looking at O(log n) and if k is comparable to n then it should be O(k log k).</p> <p>See also <a href="https://stackoverflow.com/questions/97762/algorithm-for-hit-test-in-non-overlapping-rectangles">this</a> question.</p> <p>EDIT: In response to complexity of intersections and unions. </p> <p>In more details, we have two scenarios depending on if k &lt;&lt; n or k comparable to n</p> <p>a) in case of k &lt;&lt; n and assuming polynomial complexity for intersection/union (so here I give up the guess O(k log k) ) we have:</p> <ul> <li>log n to <a href="http://en.wikipedia.org/wiki/Kd-tree" rel="nofollow noreferrer">find a range</a> in kd indexed tree (of rectangles),</li> <li>k steps to retrieve all the rectangles in that 'branch',</li> <li>f(k) some polynomial time to calculate intersections and union </li> </ul> <p>The total is O(k + log n + f(k)), which is directly equal to O(log n) since big O depends only on the fastest growing term.</p> <p>In this case the more significant part of the algorithm is finding the polygons.</p> <p>b) in the case of k comparable to n we must take a look at the complexity of intersection and union algorithms (notice the parallel here on how the RDBMs, depending on selectivity, might use index or do table scan; it is a similar choice to what we have here).<br> If k is big enough the algorithm becomes less of an algorithm for finding rectangles that intersect with the rectangle and becomes more of an algorithm for calculating the union of polygons.</p> <p>But, i believe that the kd tree can also help in finding the intersection of segments (which are necessary to build the union), so even this part of algorithm might not need k^2 time. At this point I would investigate efficient algorithms for calculating the area of unions.</p>
    singulars
    1. This table or related slice is empty.
    1. PORectangles Covering
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USUnreason
    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. VTDownMod
    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. COAre you sure you can merge N intersections in O(N) time? The problem in your third point the essentially same as the original question, 1 and 2 are just trivial cases you can solve in O(N). The complexity of the polygon will increase as you unite more rectangles, leading to a O(N²) operation. I should say, though, I have limited experience, and may be thinking of a naive approach.
      singulars
      1. PO
      1. USKobi
    2. CONo, i said that efficient algoritm can do this by O(n log n).
      singulars
      1. PO
      1. USden bardadym
    3. CO@Kobi: Union of the intersections will happen in O(f(k)) time, for k << n, where k is the number of polygons that intersect with the model, this is not the fastest growing term and gets dropped. For the analysis of the merge/union algorithm check the EDIT in the answer.
      singulars
      1. PO
      1. USUnreason
 

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