직교 2 차원 격자가있는 교차하는 평행선

Question

어느 방향 으로든 갈 수있는 두 개의 평행선이 있습니다. 그들은 동일하지 않을 것이 보장됩니다.

저는 2D 그리드 (0.0에서 1.0까지의 비 정수 좌표를 가졌지 만 전체적인 문제를 스케일링하여 해결할 수 있다고 생각합니다)가 일반적인 방법으로 직각으로 정렬되었습니다.

두 줄 사이에있는 모든 사각형의 목록을 생성하는 알고리즘이 필요합니다.

현재의 알고리즘은 비효율적입니다 (두 개의 선을 회전 된 직사각형으로 표시 한 다음 모든 정사각형에서 다각형 - 폴리곤 교차점을 테스트 함). 그것은 작동하지만 horrifically 천천히.

Answer 1

두 줄의 방향과 위치를 알고 있다면 Bresenham 선 알고리즘 (en.wikipedia.org/wiki/Bresenham's_line_algorithm 참조)을 사용하여 '터치'되는 모든 '사각형'을 계산할 수 있습니다. 두 줄 중 하나에 의해. 중간에 사각형을 추가하는 것은 간단한 작업입니다. 두 줄을 '사각형'의 정수로 구분하면 그 중 하나에 대해 Bressenham 만 해결해야하지만, 비 필수 분리가 있으면 두 가지 모두에 대해 불만을 나타내야합니다 (후자는 선이 평행하지 않더라도).