Line segment container for fast ray crossing? (2D)

Question

I have a beam, I need to find the closest segment of the line into which it hits. I think this can be done in O (log n) if you first sort the line segments, but I don’t remember how to sort them ... I think some kind of tree will work best, but how do I sort them like starting and ending point? I would also like a quick insert into this data structure, if possible.

There is a lot of code for one beam compared to one line segment, but I need something for one beam and many line segments ... I don’t know what conditions google has for.

A link to a suitable article is good, C ++ code is even better. Thank you :)

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

This is all 2D.

---

On the other hand, I am not entirely sure that this is possible. Some kind of spatial splitting may be useful, but otherwise I can not think of any way to sort the strings so that they can be compared with an arbitrary ray.

Answer 1

You can take the bounding box from the polygon (min-max x, y coordinates) and build a grid inside the box. Then for each cell, remember all the lines that intersect the cell.

Find such an intuition:

• Find out which cell the ray hits (O (1))
• Use the grid traversal algorithm to “draw” a ray through the grid. When you click on a non-empty cell, check all its rows, check if the intersection is inside the cell and select the nearest intersection. If all intersections are outside the cell, continue (this is O (grid length)).

You can also make the grid hierarchical (i.e. quadtree is the tree you requested) and go through 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:

• Create a quadtree containing strings (building a quadtree is described in the article) - you separate nodes (= areas) if they contain too many objects on 4 sub-nodes (sub-areas)

• Collect all the leaf quadrant nodes that fall on the beam:

  Calculate the rectangular intersection of the rectangle (not difficult) for the root. If the root hits the beam, continue it recursively.

The great thing is that when the node tree didn’t hit, you skipped processing the entire subtree (a potentially large rectangular area).

In the end, this is equivalent to crossing the grid - you collect the smallest cells in the path of the beam, and then check all the objects in them for intersection. You just need to check everything and choose the nearest intersection (so that you explore all the lines in the path of the beam).

This is O (sqrt (N)).

When traversing the grid, when you find the intersection, you can stop the search. To achieve this by using the quadrant traversal, you will need to find the children in the correct order - either collect 4 direct intersections by distance, or deftly walk along a 4-element grid (we will return to the traversal).

This is just another approach, relatively difficult to implement, I think, and works well (I tested it on real data - O (sqrt (N))). Again, you would benefit from this approach, if you have at least a couple of lines, when the polygon has 10 edges, the advantage compared to just testing all of them will be small, I think.

Answer 2

How are you sure that you will get into any of them? If these are lines, this is unlikely.

If this is really a polygon (i.e. planar) that you are trying to test, the usual way to do such a thing is to first intersect with the plane, and then check this point (in 2d coordinates) for the inside / outside polygon.

Perhaps I misunderstood what you are actually doing.

In general, accelerating intersections with complex numbers are performed with spatial separation (and then with methods such as a mailbox if your tests are expensive).

[Update: I misunderstood the original intention] You can still use (2d) spatial partitioning, but the overhead might not be worth it. Individual tests are cheap, if your policies are not complicated, it may be cheaper to just walk on them. It is hard to say from the description.

Answer 3

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

Answer 4

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

Answer 5

Ask for clarification, is this correct?

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

So is the point (x, y) not fixed? (Can it be any point and any direction?)