Find the Intersection Between LIne and Grid in A Fast Manner

tags:

c#
geometry

views:

102

answers:

+3 Q:

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

+1 A:

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 2010-07-17 10:48:34

+2 A:

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

dtb 2010-07-17 11:15:30

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

Ngu Soon Hui 2010-07-17 11:22:17

So what's missing?

dtb 2010-07-17 11:25:11

@dtb, nothing missing. But I want an efficient algorithm for that

Ngu Soon Hui 2010-07-17 11:42:32

This looks like one calculation per intersection to me. I can't imagine anything more efficient than that.

dtb 2010-07-17 11:44:58

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

Ngu Soon Hui 2010-07-18 02:20:32

@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 2010-07-18 10:01:39

@dtb, Ah, OK, you are right. But is there no other way to further optimize the thing?

Ngu Soon Hui 2010-07-18 11:58:22

@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 2010-07-18 13:12:17

If the grid is axis aligned:

find out the line equation
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 2010-07-17 11:30:48

ansaurus

tags:

views:

answers:

Find the Intersection Between LIne and Grid in A Fast Manner

related questions