Line Segment container for fast Ray intersection? (2D)

Question

I have a ray, I need to find the closest line segment that it hits. I think it's possible to do this in O(log n) time if I sort the line segments first, but I can't remember how to sort them... I think some sort of tree would work best, but how do I sort them by both start and end point? I would also like fast insertions into this data structure if possible.

There's lots of code for one ray vs one line segment, but I need something for one ray vs many line segments... I don't know what terms to google for.

A link to an appropriate article is good, C++ code is even better. Thanks! :)

PS: The line segments are actually the edges of a non-self-intersecting polygon, sorted in CCW order... but I think there may be some advantage to sorting them in a different fashion?

This is all 2D.

---

On second thought, I'm not entirely sure this is possible. Some sort of spatial partitioning might help, but otherwise, I can't think of any way to sort the lines so that they could be compared with an arbitrary ray.

Answer 1

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.

Find an intesection like this:

• Find out which cell the ray hits first (O(1))
• Use Grid traversal algorithm 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)).

You could also make the grid hierarchical (ie. quadtree - a tree you were asking for), and walk it using the same algorithm. This is done in raytracing in 3D and the time complexity is O(sqrt(N)).

---

Or, use the approach I did in my raytracer:

• Build a quadtree 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)

• Collect all leaf nodes of the quadtree that are hit by the ray:

  Compute ray-rectangle intersection (not hard) for the root. If the root is hit by the ray, proceed with its children recursively.

The cool thing about this is that when a tree node is not hit, you've skipped processing whole subtree (potentially a large rectangular area).

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).

This is O(sqrt(N)).

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).

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.

Answer 2

Are you looking for scanline/Active Edge Table based methods? You can take a look at the Wikipedia entry for Scanline Rendering or search the Graphics Gems directory for the algorithms (mostly C, but some C++ code as well).