Encuentre la intersección entre la línea y la cuadrícula de una manera rápida

Question

¿Hay alguna forma que me permita encontrar todos los puntos de intersección entre una línea y una cuadrícula? (Los círculos de intersección no están dibujados a escala entre sí, sé)

Una manera la fuerza bruta es computar muy intersección de la cuadrícula x-y con la línea, pero este algoritmo es muy ineficiente (O(m*n) , donde m es el número de cuadrícula x y n es el número de cuadrícula y).

Estoy buscando un mejor algoritmo para esto.

Answer 1

Parece que necesita un Digital Differential Analyzer o Bresenham's line algorithm. Bresenham es el mismo algoritmo utilizado para dibujar líneas en un mapa de bits; en este caso, colorear un píxel es equivalente a verificar colisiones en ese cuadrado.

Answer 2

No estoy seguro de que realmente entiendo la pregunta. ¿Es esto lo que estás buscando por casualidad?

Illustration 1 http://i31.tinypic.com/mwwg37.png

Illustration 2 http://i27.tinypic.com/657uc1.png

Answer 3

Si la cuadrícula está alineado eje:

1. averiguar la ecuación línea
2. calcular los puntos de intersección directamente utilizando X o Y de la línea de cuadrícula como una variable fija

Si la cuadrícula es regular, la distancia entre las intersecciones con cada línea horizontal será la misma. Lo mismo ocurre con las líneas verticales. Podría hacer un algoritmo iterativo simple con dx y dy en ese caso.