algorithm - quitar - para que sirven las lineas de cuadricula en word
¿Cómo encontrar todos los cuadrados de la cuadrícula en una línea? (4)
Estoy tratando de implementar un algoritmo de línea de visión en una cuadrícula bidimensional. Sé cómo debe funcionar conceptualmente, pero no puedo pensar en cómo implementarlo como un algoritmo.
La idea básica es bastante simple. En pseudocódigo:
function LineOfSight(point1, point2): boolean
squares = GetListOfSquaresOnLine(point1, point2)
for each square in squares
if square.IsOpaque then return false
return true
GetListOfSquaresOnLine (conceptualmente) una línea recta desde el centro del cuadrado de la cuadrícula en el punto 1 hasta el centro del cuadrado de la cuadrícula en el punto 2, y devolvería una lista de todos los cuadrados por los que pasa esta línea. Pero esa es la parte que no tengo idea de cómo implementar. Alguien sabe cómo hacer esto? Se prefieren los ejemplos de Delphi o C, pero no se requieren.
Ambas respuestas hasta ahora apuntan a un artículo de Wikipedia sobre el algoritmo de Bresenhams . Aquí está la ilustración que da el artículo, a tamaño completo. Observe que la línea pasa a través de cuadrados de cuadrícula que no están resaltados, por lo que el algoritmo de Bresenham solo proporciona un subconjunto de lo que desea.
Como mencionas "línea de visión", parece que quieres un algoritmo que enumere todos los cuadrados de cuadrícula por los que pasa la línea. Este conjunto a veces se denomina super cubierta (de la línea), y aquí se describe un algoritmo .
También hay algunos otros enfoques, dados en las respuestas a esta pregunta .
Actualización: Aquí hay otra referencia
Aquí hay una implementación que escribí en C.
No es Bresenhams lo que estás buscando?