-
Notifications
You must be signed in to change notification settings - Fork 0
/
algorithms.py
55 lines (47 loc) · 1.01 KB
/
algorithms.py
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
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def bresnham_line(a, b):
d, dx, dy, ai, bi, xi, yi = 0
x = a.x, y = a.y
# set drawing direction
if a.x < b.x:
xi = 1
dx = b.x - a.x
else:
xi = -1
dx = a.x - b.x
if a.y < b.y:
yi = 1
dy = b.y - a.y
else:
yi = -1
dy = a.y - b.y
line = [Point(x, y)]
if dx > dy:
ai = (dy - dx) * 2
bi = dy * 2
d = bi - dx
while x != b.x:
if d >= 0:
x += xi
y += yi
d += ai
else:
d += bi
x += xi
line.append(Point(x, y))
else:
ai = (dx - dy) * 2
bi = dx * 2
d = bi - dy
while y != b.y:
if d >= 0:
x += xi
y += yi
d += ai
else:
d += bi
y += yi
line.append(Point(x, y))