Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You could take a bounding box of the polygon (min-max x,y coordinates) and build a grid inside the box. Then, for each cell, remember all lines that cross the cell.</p> <p>Find an intesection like this:</p> <ul> <li>Find out which cell the ray hits first (O(1))</li> <li>Use <a href="http://www.devmaster.net/articles/raytracing_series/part4.php" rel="nofollow noreferrer">Grid traversal algorithm</a> to "draw" a ray through the grid. When you hit non-empty cell, check all its lines, check if intersection is inside the cell and pick the closest intersection. If all intersections are outside the cell, continue (this is O(grid length)).</li> </ul> <p>You could also make the grid hierarchical (ie. <a href="http://www.codeproject.com/KB/recipes/QuadTree.aspx" rel="nofollow noreferrer">quadtree</a> - a tree you were asking for), and walk it using the same algorithm. <a href="http://www.devmaster.net/articles/raytracing_series/part4.php" rel="nofollow noreferrer">This is done in raytracing in 3D</a> and the time complexity is O(sqrt(N)).</p> <hr> <p>Or, use the approach I did in my raytracer:</p> <ul> <li>Build a <a href="http://www.codeproject.com/KB/recipes/QuadTree.aspx" rel="nofollow noreferrer">quadtree</a> containing the lines (building quadtree is desribed in the article) - you split nodes (=areas) if they contain too many objects into 4 sub-nodes (sub-areas)</li> <li><p>Collect all <em>leaf nodes</em> of the quadtree that are hit by the ray:</p> <p>Compute ray-rectangle intersection (not hard) for the root. If the root is hit by the ray, proceed with its children recursively.</p></li> </ul> <p>The cool thing about this is that when a tree node is <em>not</em> hit, you've skipped processing whole subtree (potentially a large rectangular area).</p> <p>In the end, this is equivalent to traversing the grid - you collect the smallest cells on the ray's path, and then test all objects in them for intersection. You just have to test all of them and pick the closest intersection (so you explore all lines on ray's path).</p> <p>This is O(sqrt(N)).</p> <p>In grid traversal, when you find an intersection, you can stop searching. To achieve this with quadtree traversal, you would have to seach the children in the right order - either sort the 4 rect intersections by distance or cleverly traverse the 4-cell grid (an we are back to traversal).</p> <p>This is just a different approach, comparatively same difficult to implement I think, and works well (I tested it on real data - O(sqrt(N))). Again, you would only benefit from this approach if you have at least a couple of lines, when the polygon has 10 edges the benefit compared to just testing all of them would be little I think.</p>
    singulars
    1. This table or related slice is empty.
    1. POLine Segment container for fast Ray intersection? (2D)
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USMartin Konicek
    1. USMartin Konicek
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POLine Segment container for fast Ray intersection? (2D)
      singulars
      1. PTQuestion
    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. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CONo, the O(log n) I was thinking of was for horizontal or vertical line segments only I believe. Bresenham's algorithm looks like it could miss intersections though, can't it? It doesn't "fill" every cell it enters. Otherwise, this looks like a good approach.
      singulars
      1. PO
      1. USmpen
    2. COYou are right, grid traversal should be done by algorithm mentioned here http://www.devmaster.net/articles/raytracing_series/part4.php, look at section "Grid traversal". Note that you would probably only benefit if your polygon has many (~hundred) edges, as they show in the article.
      singulars
      1. PO
      1. USMartin Konicek
    3. COWell, there probably won't he hundreds of edges, but the same edges might get used thousands of times. This looks like the best answer on what I thought was a dead question, so I'll give you the check ;) Thanks.
      singulars
      1. PO
      1. USmpen
 

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