Jak znaleźć wszystkie kwadraty siatki na linii?

Question

Próbuję zaimplementować algorytm linii wzroku na dwuwymiarowej siatce. Wiem, jak to musi działać koncepcyjnie, ale nie mogę myśleć o tym, jak zaimplementować go jako algorytm.

Podstawowy pomysł jest dość prosty. W pseudokodzie:

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

GetListOfSquaresOnLine że (koncepcyjnie) narysować linię prostą z centrum kwadratu siatki, punktem 1 do centrum kwadratu siatki, punktem2 i zwraca się wszystkie kwadraty, że oś przechodzi przez . Ale to jest część, której nie mam pojęcia, jak ją wprowadzić. Czy ktoś wie, jak to zrobić? Przykłady Delphi lub C są preferowane, ale nie są wymagane.

Answer 1

obydwie odpowiedzi do tej pory wskazują na artykuł na algorytmie Bresenhams „s. Oto ilustracja, którą artykuł podaje w pełnym rozmiarze. Zauważ, że linia przechodzi przez kwadraty siatki, które nie są podświetlone, więc algorytm Bresenhama podaje jedynie podzbiór tego, co chcesz.

Skoro wspomniałeś „linii wzroku”, to brzmi jak chcesz algorytm, który wylicza wszystkie kwadratów siatki że linia przebiega przez. Ten zestaw jest czasami określany jako super okładka (linii) i one algorithm is described here.

Istnieje również kilka innych podejść, podanych w odpowiedziach na this question.

Aktualizacja:Here's another reference

Answer 2

Czy nie jest to Bresenham's Algorithm czego szukasz?

Answer 3

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

Answer 4

Oto an implementation I wrote in C.