1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
#pragma once
#include "StarVector.hpp"
namespace Star {
// Iterate over integral cells based on Bresenham's line drawing algorithm.
// Returns false immediately when the callback returns false for any cell,
// returns true after iterating through every cell otherwise.
template <typename Scalar>
bool forBlocksAlongLine(Vector<Scalar, 2> origin, Vector<Scalar, 2> const& dxdy, function<bool(int, int)> callback) {
Vector<Scalar, 2> remote = origin + dxdy;
double dx = dxdy[0];
if (dx < 0)
dx *= -1;
double dy = dxdy[1];
if (dy < 0)
dy *= -1;
double oxfloor = floor(origin[0]);
double oyfloor = floor(origin[1]);
double rxfloor = floor(remote[0]);
double ryfloor = floor(remote[1]);
if (dx == 0) {
if (oyfloor < ryfloor) {
for (int i = oyfloor; i <= ryfloor; ++i) {
if (!callback(oxfloor, i))
return false;
}
} else {
for (int i = oyfloor; i >= ryfloor; --i) {
if (!callback(oxfloor, i))
return false;
}
}
return true;
} else if (dy == 0) {
if (oxfloor < rxfloor) {
for (int i = oxfloor; i <= rxfloor; ++i) {
if (!callback(i, oyfloor))
return false;
}
} else {
for (int i = oxfloor; i >= rxfloor; --i) {
if (!callback(i, oyfloor))
return false;
}
}
return true;
} else {
int x = oxfloor;
int y = oyfloor;
int n = 1;
int x_inc, y_inc;
double error;
if (dxdy[0] > 0) {
x_inc = 1;
n += int(rxfloor) - x;
error = (oxfloor + 1 - origin[0]) * dy;
} else {
x_inc = -1;
n += x - int(rxfloor);
error = (origin[0] - oxfloor) * dy;
}
if (dxdy[1] > 0) {
y_inc = 1;
n += int(ryfloor) - y;
error -= (oyfloor + 1 - origin[1]) * dx;
} else {
y_inc = -1;
n += y - int(ryfloor);
error -= (origin[1] - oyfloor) * dx;
}
for (; n > 0; --n) {
if (!callback(x, y))
return false;
if (error > 0) {
y += y_inc;
error -= dx;
} else if (error < 0) {
x += x_inc;
error += dy;
} else {
--n;
y += y_inc;
x += x_inc;
error += dy;
error -= dx;
}
}
return true;
}
}
}
|