algorithm - Elegante/limpio(caso especial) ¿Algoritmo transversal de cuadrícula en línea recta?

language-agnostic math (3)

Hay un algoritmo muy fácil para Tu problema que se ejecuta en tiempo lineal:

Dados dos puntos A y B, determine los puntos de intersección de la línea (A, B) con cada línea vertical de su cuadrícula, que se encuentra dentro de este intervalo.
Inserte dos puntos de intersección especiales dentro de las celdas que contienen A y B al comienzo / final de la lista desde el punto 1.
Interprete cada dos puntos de intersección secuenciales como los vectores mínimo y máximo de un rectángulo alineado por el eje y marque todas las celdas de la cuadrícula que se encuentran dentro de este rectángulo (esto es muy fácil (intersección de rectas alineadas de dos ejes), especialmente considerando que el rectángulo tiene un ancho de 1 y por lo tanto ocupa solo 1 columna de su cuadrícula)

Ejemplo:

+------+------+------+------+ | | | | | | | | B * | | | |/ | | +------+------*------+------+ | | /| | | | | / | | | | | / | | | +------+--/---+------+------+ | | / | | | | |/ | | | | * | | | +-----/+------+------+------+ | / | | | | * A | | | | | | | | | +------+------+------+------+

"A" y "B" son los puntos que terminan la línea representada por "/". "*" marca los puntos de intersección de la línea con la cuadrícula. Los dos puntos de intersección especiales son necesarios para marcar las celdas que contienen A y B y para manejar casos especiales como Ax == Bx

Una implementación optimizada necesita Θ (| Bx - Ax | + | By - Ay |) tiempo para una línea (A, B). Además, uno puede escribir este algoritmo para determinar los puntos de intersección con líneas de cuadrícula horizontales, si eso es más fácil para el implementador.

Actualización: casos fronterizos

Como brainjam señala correctamente en su respuesta, los casos difíciles son los que, cuando una línea pasa exactamente a través de un punto de cuadrícula. Supongamos que ocurre un caso así y que las operaciones aritméticas de punto flotante devuelven correctamente un punto de intersección con coordenadas integrales. En este caso, el algoritmo propuesto marca solo las celdas correctas (según lo especificado por la imagen proporcionada por el OP).

Sin embargo, los errores de punto flotante ocurrirán tarde o temprano y darán resultados incorrectos. Desde mi opinión, incluso usar el doble no es suficiente y uno debería cambiar a un tipo de número Decimal . Una implementación optimizada realizará (| max.x - min.x |) adiciones en ese tipo de datos, cada una de las cuales llevará Θ (log max.y) el tiempo. Eso significa que en el peor de los casos (la línea ((0, 0), (N, N)) con una gran N (> 10 ⁶ ) el algoritmo degrada a un O (N log N) en el peor tiempo de ejecución. Incluso cambiando entre vertical / la detección de intersección de la línea de la rejilla horizontal que depende de la pendiente de la línea (A, B) no ayuda en el peor de los casos, pero sí lo hace en el caso promedio; solo consideraría implementar un cambio de este tipo si un generador de perfiles produce el Decimal Operaciones para ser el cuello de la botella.

Por último, puedo imaginar que algunas personas inteligentes podrían llegar a una solución O (N) que se ocupe correctamente de estos casos fronterizos. Todas sus sugerencias son bienvenidas!

Corrección

brainjam señaló que un tipo de datos decimal no es satisfactorio incluso si puede representar números de punto flotante de precisión arbitrarios, ya que, por ejemplo, 1/3 no se puede representar correctamente. Por lo tanto, uno debería usar un tipo de datos de fracción, que debería poder manejar los casos de borde correctamente. Thx brainjam! :)

Estoy desempolvando un viejo proyecto mío. Una de las cosas que tenía que hacer era, dado un sistema de cuadrícula cartesiana y dos cuadrados en la cuadrícula, encontrar una lista de todos los cuadrados por los que pasaría una línea que une el centro de esos dos cuadrados.

El caso especial aquí es que todos los puntos de inicio y final se limitan al centro exacto de cuadrados / celdas.

Aquí hay algunos ejemplos, con pares de puntos de inicio y final de muestra. Los cuadrados sombreados son los que deben ser devueltos por la llamada de función respectiva

se eliminó el enlace de ImageShack muerto - ejemplo

Los puntos de inicio y final se refieren a los cuadrados en los que están. En la imagen anterior, suponiendo que la parte inferior izquierda es [1,1] , la línea de la parte inferior derecha se identificará como [6,2] a [9,5] .

Es decir, desde el cuadrado (centro del) en la sexta columna desde la izquierda, en la segunda fila desde la parte inferior hasta el cuadrado (centro del) en la novena columna desde la izquierda, en la quinta fila desde la parte inferior

Lo que realmente no parece tan complicado. Sin embargo, de alguna manera parecía haber encontrado algún algoritmo complejo en línea y lo había implementado.

Recuerdo que fue muy, muy rápido. Al igual que, optimizado para cientos o miles de veces por fotogramas rápido.

Básicamente, saltó de borde a borde de los cuadrados, a lo largo de la línea (los puntos donde la línea cruza las líneas de la cuadrícula). Sabía dónde estaba el siguiente punto de cruce al ver qué punto de cruce estaba más cerca, uno horizontal o vertical, y se trasladó al siguiente.

Lo cual está bastante bien en concepto, pero la implementación real resultó no ser muy bonita, y me temo que el nivel de optimización podría ser demasiado alto para lo que prácticamente necesito (lo llamo transversal) Algoritmo tal vez cinco o seis veces por minuto).

¿Existe un algoritmo transversal de línea recta transparente, fácil de entender y simple?

En términos programáticos:

def traverse(start_point,end_point) # returns a list of all squares that this line would pass through end

Donde las coordenadas dadas identifican los cuadrados mismos.

Algunos ejemplos:

traverse([0,0],[0,4]) # => [0,0], [0,1], [0,2], [0,3], [0,4] traverse([0,0],[3,2]) # => [0,0], [0,1], [1,1], [2,1], [2,2], [3,2] traverse([0,0],[3,3]) # => [0,0], [1,1], [2,2], [3,3]

Tenga en cuenta que las líneas que se mueven directamente a través de las esquinas no deben incluir cuadrados en el "ala" de la línea.

(El buen Bresenham podría funcionar aquí, pero está un poco al revés de lo que quiero. Por lo que sé, para usarlo, básicamente tendría que aplicarlo a la línea y luego escanear cada cuadrado en el cuadrícula para verdadero o falso. Inasible (o al menos poco elegante) para cuadrículas grandes)

(Estoy revisando Bresenham y los algoritmos basados en Bresenham, debido a un malentendido mío)

Para aclarar, una posible aplicación de esto sería, si estuviera almacenando todos mis objetos en un juego dentro de las zonas (una cuadrícula), y tengo un rayo, y quiero ver qué objetos toca el rayo. Usando este algoritmo, podría probar el rayo solo para los objetos que están dentro de las zonas dadas, en lugar de cada objeto en el mapa.

El uso real de esto en mi aplicación es que cada mosaico tiene un efecto asociado, y un objeto se mueve a través de un segmento de línea dado cada turno. En cada turno, es necesario verificar para ver en qué cuadrados ha atravesado el objeto y, por lo tanto, qué efectos aplicar al objeto.

Tenga en cuenta que, en este punto, la implementación actual que tengo funciona. Esta pregunta es principalmente para el propósito de la curiosidad. Tiene que haber una forma más simple ... de alguna manera ... para un problema tan simple.

¿Qué estoy buscando exactamente? Algo conceptualmente / aseado y limpio. Además, me he dado cuenta de que, debido a lo que estoy especificando exactamente, todos los puntos de inicio y final siempre estarán en el centro de los cuadrados / celdas; Así que tal vez algo que se aproveche de eso sería bueno también.

Lo que desea es un caso particular de un supercubierto, que es todos los píxeles intersecados por un objeto geométrico. El objeto puede ser una línea o un triángulo, y hay generalizaciones a dimensiones más altas.

De todos modos, aquí hay una implementación para segmentos de línea . Esa página también compara la supercubia con el resultado del algoritmo de Bresenham: son diferentes. texto alternativo http://eugen.dedu.free.fr/projects/bresenham/diff.png

No sé si consideras el algoritmo como elegante / limpio, pero ciertamente parece lo suficientemente simple como para adaptar el código y pasar a otras partes de tu proyecto.

Por cierto, su pregunta implica que el algoritmo de Bresenham no es eficiente para grillas grandes. Eso no es cierto, solo genera los píxeles en la línea. No tiene que hacer una prueba de verdadero / falso para cada píxel en la cuadrícula.

Actualización 1: Noté que en la imagen hay dos cuadrados azules ''extra'' que creo que la línea no pasa. Uno de ellos es adyacente a la ''h'' en ''Este algoritmo''. No sé si eso refleja un error en el algoritmo o el diagrama (pero vea el comentario de @kikito a continuación).

En general, los casos "difíciles" son probablemente cuando la línea pasa exactamente a través de un punto de cuadrícula. Especulo que si está utilizando un punto flotante, ese error de punto flotante puede estropearlo en estos casos. En otras palabras, los algoritmos probablemente deberían atenerse a la aritmética de enteros.

Actualización 2: Otra implementación .

Un documento sobre este tema se puede encontrar here . Esto es en lo que respecta al trazado de rayos, pero de todos modos parece bastante relevante para lo que está buscando, y asumo que podrá trabajar un poco con él.

También hay otro artículo here , que trata de algo similar.

Ambos documentos están vinculados en la parte 4 de los excelentes tutoriales de Jakko Bikker sobre el trazado de rayos (que también incluyen su código fuente, para que pueda examinar / examinar sus implementaciones).