Find the intersection between line and grid in a fast manner

Is there anyway that allows me to find all the intersection points between a line and a grid? ( The intersection circles are not drawn to scale with each other, I know)

A brute force way is to compute very intersection for the x-y grid with the line, but this algorithm is awfully inefficient (O(m*n), where m is the number of x grid and n is the number of y grid).

I'm looking for a better algor开发者_如何学编程ithm on this.

Sounds like you need a Digital Differential Analyzer or Bresenham's line algorithm. Bresenham is the same algorithm used to draw lines on a bitmap; in this case, coloring a pixel is equivalent to checking for collisions in that square.

I'm not sure I really understand the question. Is this what you're looking for by any chance?

If the grid is axis aligned:

1. find out the line equation
2. calculate the intersection points directly using either the grid line's x or y as a fixed variable

If the grid is regular, the distance between the intersections with each horizontal line will be the same. The same also goes for the vertical lines. You could just do a simple iterative algorithm with dx and dy in that case.

Algorithm:

The grid consists out of walls.

A wall is of/in a certain dimension: (Vertical, Horizontal, Depth)

The wall dimensions intersect forming cells (in final dimension)

The line intersects the walls primarly in their own dimension.

The solution is to view the problem as: How to intersect a line with a wall in it's own dimension.

The solution is to slide across the line from wall to wall, switch dimensions as necessary.

The sliding across the line happens such that the nearest wall is always chosen as the next destination.

The sliding from wall to wall in it's own dimension is constant/always the same.

The intersection of the line and the walls is different per dimension.

This ultimately decides the order of the wall intersections.

The solution is therefore to:

Phase 1: Initialization

Compute Dimension.IntersectT

Compute Dimension.SlideT

Phase 2: Start sliding from origin towards destination selecting nearest wall:

Dimension.T := Dimension.IntersectT

while ? end condition ?

Select smallest Dimension.T

Update selected Dimension.T += Dimension.SlideT

end

The difficulty lies in computing the Ts.

Bye, Skybuck.