10

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 algorithm on this.

Graviton
  • 81,782
  • 146
  • 424
  • 602

4 Answers4

8

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.

celion
  • 3,864
  • 25
  • 19
  • 1
    I believe this should be the accepted answer. Using an algorithm like Bresenham's will give the grid points to check, and then from there individual intersection points can be calculated with much more ease - The horizontal and vertical components are all known. – Bryan Rayner Jun 27 '14 at 15:30
7

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

Illustration 1

Illustration 2

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
dtb
  • 213,145
  • 36
  • 401
  • 431
  • I want every single intersection point between the red line and the grid line. So, the points are `(0,b)`, `((h-b)/m, h)`, `(w, mw+b)`, `(2w, 2wm+b)`, `((2h-b)/m,2h)`, `(3w, 3wm+b)` and so on – Graviton Jul 17 '10 at 11:22
  • @dtb, nothing missing. But I want an efficient algorithm for that – Graviton Jul 17 '10 at 11:42
  • 2
    This looks like one calculation per intersection to me. I can't imagine anything more efficient than that. – dtb Jul 17 '10 at 11:44
  • 1
    @dtb, if that were the case, that would be awfully inefficient. Consider that you have a 100*100 grid, then you have to do at 100*100 operation. – Graviton Jul 18 '10 at 02:20
  • @Ngu Soon Hui: I don't understand. The grid in my answer is made up of 5 horizontal and 5 vertical lines. The red line intersects with the grid lines at 7 places. To find these 7 intersections, you need to perform at most 10 calculations, not 25. – dtb Jul 18 '10 at 10:01
  • @dtb, Ah, OK, you are right. But is there no other way to further optimize the thing? – Graviton Jul 18 '10 at 11:58
  • @Ngu Soon Hui: You can stop when you get the first intersection outside the grid. Alternatively, since all intersections with horizontal grid lines and all intersections with vertical grid lines are equidistant respectively, you can simply calculate the first intersection respectively and get the other intersections by adding the delta repeatedly. Either way requires 9 calculations for the example in my answer. – dtb Jul 18 '10 at 13:12
0

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.

jackrabbit
  • 5,525
  • 1
  • 27
  • 38
-2

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.

oOo
  • 261
  • 2
  • 16