Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Maintaining a dynamic tree might not be as bad as you think.</p> <p>As you insert new points/lines etc into the collection it's clear that you'd need to refine the current tree, but I can't see why you'd have to re-build the whole tree from scratch every time a new entity was added, as you're suggesting.</p> <p>With a dynamic tree approach you'd have a valid tree at all times, so you can then just use the fast range searches supported by your tree type to find the geometric entities you've mentioned.</p> <p>For your particular problem:</p> <ul> <li><p>You could setup a dynamic geometric tree, where the leaf elements maintain a list of geometric entities (points and lines) associated with that leaf.</p></li> <li><p>When a line is inserted into the collection it should be pushed onto the lists of all leaf elements that it intersects with. You can do this efficiently by traversing the subset of the tree from the root that intersects with the line.</p></li> <li><p>To find all points/lines within a specified radial halo you first need to find all leaves in this region. Again, this can be done by traversing the subset of the tree from the root that is enclosed by, or that intersects with the halo. Since there maybe some overlap, you need to check that the entities associated with this set of leaf elements actually lie within the halo.</p></li> <li><p>Once you've inserted a line into a set of leaf elements, you can find whether it intersects with another line by scanning all of the lines associated with the subset of leaf boxes you've just found. You can then do line-line intersection tests on this subset.</p></li> </ul> <p>A potential dynamic tree refinement algorithm, based on an upper limit to the number of entities associated with each leaf in the tree, might work along these lines:</p> <pre><code>function insert(x, y) find the tree leaf element enclosing the new entitiy at (x,y) based on whatever fast search algorithm your tree supports if (number of entities per leaf &gt; max allowable) do refine current leaf element (would typically either be a bisection or quadrisection based on a 2D tree type) push all entities from the old leaf element list onto the new child element lists, based on the enclosing child element else push new entity onto list for leaf element endif </code></pre> <p>This type of refinement strategy only makes local changes to the tree and is thus generally pretty fast in practice. If you're also deleting entities from the collection you can also support dynamic aggregation by imposing a minimum number of entities per leaf, and collapsing leaf elements to their parents when necessary.</p> <p>I've used this type of approach a number of times with quadtrees/octrees, and I can't at this stage see why a similar approach wouldn't work with kd-trees etc.</p> <p>Hope this helps.</p>
    singulars
    1. This table or related slice is empty.
    1. PONearest neighbour search in a constantly changing set of line segments
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDarren Engwirda
    1. USDarren Engwirda
    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
    1. COHow would you balance this tree ? The tree can become lopsided (albeit in the worst case) and this will reduce performance dramatically.
      singulars
      1. PO
      1. USSid Datta
    2. COI believe you have pointed me towards R trees (http://en.wikipedia.org/wiki/R-tree). Thanks!
      singulars
      1. PO
      1. USSid Datta
    3. COThe level of imbalance in the tree is dependent on your data. It's often stated that real-world data is reasonably well distributed, making worst-case behaviour unlikely practice - I would try first and see whether you have a problem before worrying about re-balance operations. Also note that it's only kd-like trees, which are split according to a median criteria that could be affected by the order in which points are added, and hence re-balancing. Trees that have a fixed geometric refinement (quadtrees/octrees etc) will give you the same result regardless of insertion order.
      singulars
      1. PO
      1. USDarren Engwirda
 

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