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

How are you certain that you'll hit any of them? If they're lines, it's unlikely.

If it's really a polygon (i.e. planar) that you're trying to test, the usual way to do this sort of thing is intersect with the plane first, then test that point (in the 2d coordinates) for inside/outside polygon.

Maybe I misunderstood what you're actually doing.

In general accelerating intersections with complex figures is done with spatial partitioning (and then techniques like mailboxing, if your tests are expensive).

[Update: I misread the original intent] You can still use (2d) spatial partitioning but the overhead may not be worth it. Individual test are cheap, if your polys aren't complicated it might be cheaper to just walk them. Hard to say from description.

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

Answer 3

Keep in mind that sorting is an O(n log n) operation at best. You may be better off just checking each individually.

Answer 4

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 - This 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 5

Ask for clarification, is this correct?

• You have a dynamic set of line segments L.
• Query: given any point (x,y) and and any direction of the ray from this point, you want to determine the closest line in L (if any) ?

So the point (x,y) is not fix? (It could be any point, and any direction?)