Estoy tratando de combinar dos cosas. Estoy escribiendo un juego y necesito determinar los cuadrados de la cuadrícula que se encuentran en una línea con los puntos finales de punto flotante.
Además, necesito que incluya todos los cuadrados de cuadrícula que toca (es decir, no solo la línea de Bresenham sino la azul):
¿Alguien puede ofrecerme alguna idea sobre cómo hacerlo? La solución obvia es usar un algoritmo de línea ingenuo, pero ¿hay algo más optimizado (más rápido)?
c#
algorithm
grid
interpolation
floating-point
SmartK8
fuente
fuente
Respuestas:
Está buscando un algoritmo transversal de cuadrícula. Este documento ofrece una buena implementación;
Aquí está la implementación básica en 2D que se encuentra en el documento:
También hay una versión de proyección de rayos 3D en el papel.
En caso de que el enlace se pudra , puede encontrar muchos espejos con su nombre: un algoritmo de recorrido de voxel más rápido para el trazado de rayos .
fuente
La idea de Blue es buena, pero la implementación es un poco torpe. De hecho, puede hacerlo fácilmente sin sqrt. Supongamos por el momento que excluye casos degenerados (
BeginX==EndX || BeginY==EndY
) y nos enfocamos solo en las direcciones de línea en el primer cuadrante, entoncesBeginX < EndX && BeginY < EndY
. También tendrá que implementar una versión para al menos otro cuadrante, pero es muy similar a la versión para el primer cuadrante: solo verifica otros bordes. En el pseudocódigo C'ish:Ahora, para otros cuadrantes, que acaba de cambiar la
++cx
o++cy
y la condición del bucle. Si usa esto para colisión, es probable que tenga que implementar las 4 versiones, de lo contrario, puede salirse con dos intercambiando adecuadamente los puntos de inicio y finalización.fuente
Su suposición no es necesariamente encontrar las celdas sino las líneas que cruza en esta cuadrícula.
Por ejemplo, al tomar su imagen, podemos resaltar no las celdas, sino las líneas de la cuadrícula que cruza:
Esto muestra que si cruza una línea de cuadrícula, las celdas a cada lado de esta línea son las que están rellenas.
Puede usar un algoritmo de intersección para encontrar si su línea de coma flotante los cruzará escalando sus puntos a píxeles. Si tiene una relación de 1.0: 1 de coordenadas flotantes: píxeles, entonces está ordenado y puede traducirlo directamente. Usando el algoritmo de intersección de segmento de línea puede verificar si su línea inferior izquierda (1,7) (2,7) se cruza con su línea (1.3,6.2) (6.51,2.9). http://alienryderflex.com/intersect/
Se necesitará alguna traducción de c a C #, pero puede obtener la idea de ese documento. Pondré el código a continuación en caso de que el enlace se rompa.
Si necesita averiguar solo cuándo (y dónde) se intersecan los segmentos de línea, puede modificar la función de la siguiente manera:
fuente
Demo de JS:
Mostrar fragmento de código
fuente
Me encontré con el mismo problema hoy e hice una gran montaña de espagueti con una colina de mole, pero terminé con algo que funciona: https://github.com/SnpM/Pan-Line-Algorithm .
Desde el archivo Léame:
ReadMe explica la solución mucho mejor que el código. Estoy planeando revisarlo para que sea menos dolor de cabeza.
Sé que llegué un año tarde a esta pregunta, pero espero que esto llegue a otros que buscan una solución a este problema.
fuente