Come trovare tutti i quadrati della griglia su una linea?

Question

Sto cercando di implementare un algoritmo line-of-sight su una griglia a 2 dimensioni. So come deve funzionare concettualmente, ma non riesco a pensare a come implementarlo come un algoritmo.

L'idea di base è piuttosto semplice. In pseudocodice:

function LineOfSight(point1, point2): boolean 
    squares = GetListOfSquaresOnLine(point1, point2) 
    for each square in squares 
    if square.IsOpaque then return false 
    return true 

GetListOfSquaresOnLine sarebbe (concettualmente) disegnare una linea retta dal centro del quadrato della griglia al point1 al centro della piazza griglia a point2, e restituire un elenco di tutti i quadrati che questa linea attraversa . Ma questa è la parte che non ho idea di come implementare. Qualcuno sa come fare questo? Esempi di Delphi o C preferiti, ma non richiesti.

Answer 1

Entrambe le risposte punto finora per un articolo di Wikipedia su algoritmo Bresenhams s'. Ecco l'illustrazione fornita dall'articolo, a grandezza naturale. Si noti che la linea passa attraverso i quadrati della griglia che non sono evidenziati, quindi l'algoritmo di Bresenham fornisce solo un sottoinsieme di ciò che si desidera.

Dal momento che si parla di "linea di vista", suona come si desidera un algoritmo che enumera tutti i quadrati della griglia che la linea passa attraverso. Questo set viene a volte definito super cover (della riga) e one algorithm is described here.

ci sono anche alcuni altri approcci, indicati nelle risposte alle this question.

Aggiornamento:Here's another reference

Answer 2

non Bresenham's Algorithm è quello che stai cercando?

Answer 3

Vedi http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Answer 4

Ecco an implementation I wrote in C.