줄의 모든 격자 사각형을 찾는 방법은 무엇입니까?

Question

2 차원 격자에 가시선 (line-of-sight) 알고리즘을 구현하려고합니다. 개념적으로 어떻게 작동해야하는지 알고 있지만 알고리즘으로 구현하는 방법을 생각할 수는 없습니다.

기본 아이디어는 매우 간단합니다. 의사 코드 :

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

GetListOfSquaresOnLine (개념) POINT2에서 그리드 광장의 중심에 POINT1에서 그리드 광장의 중심에서 직선을 그리고이 선이 통과하는 모든 사각형의 목록을 반환 . 그러나 이것이 구현 방법을 모르는 부분입니다. 누구든지이 작업을 수행하는 방법을 알고 있습니까? 델파이 또는 C 예제가 선호 되나 필수는 아닙니다.

Answer 1

모두를 참조하십시오. 이 기사가 실제 크기로 제공 한 그림이 있습니다. 선이 강조 표시되지 않은 격자 사각형을 통과하므로 Bresenham의 알고리즘은 원하는 것의 하위 집합만을 제공합니다. 당신이 라인을 통해 이동 그리드 사각형을 모두 열거하는 알고리즘을 원하는처럼

는 "시선"을 언급 이후

, 그것은 소리. 이 세트는 수퍼 커버 (라인의)라고도하며 one algorithm is described here입니다.

this question에 대한 응답에서 제공되는 몇 가지 다른 접근 방식이 있습니다.

업데이트 :Here's another reference

Answer 2

Bresenham's Algorithm 무엇을 찾고 계하십니까?

Answer 3

은 Bresenhams의 알고리즘에 Wikipedia 기사에 지금까지 포인트 답변 http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Answer 4

여기 an implementation I wrote in C입니다.