-
Notifications
You must be signed in to change notification settings - Fork 0
/
HilbertCurve.cpp
122 lines (109 loc) · 3.12 KB
/
HilbertCurve.cpp
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
class Point {
int x_, y_;
public:
Point(int x, int y) : x_(x), y_(y) {}
int get_x() const {
return x_;
}
int get_y() const {
return y_;
}
Point move_with(int x, int y) const {
return Point(x_ + x, y_ + y);
}
};
class HilbertCurve {
std::vector<Point> curve_;
static void concat(std::vector<Point>& target, const std::vector<Point>& source) {
target.insert(target.end(), source.begin(), source.end());
}
std::vector<Point> up(Point start, int order, int line) {
std::vector<Point> result;
if (order == 0) {
result.push_back(start);
return result;
}
concat(result, left(start, order - 1, line));
start = result.back().move_with(0, -line);
concat(result, up(start, order - 1, line));
start = result.back().move_with(line, 0);
concat(result, up(start, order - 1, line));
start = result.back().move_with(0, line);
concat(result, right(start, order - 1, line));
return result;
}
std::vector<Point> down(Point start, int order, int line) {
std::vector<Point> result;
if (order == 0) {
result.push_back(start);
return result;
}
concat(result, left(start, order - 1, line));
start = result.back().move_with(0, line);
concat(result, down(start, order - 1, line));
start = result.back().move_with(-line, 0);
concat(result, down(start, order - 1, line));
start = result.back().move_with(0, -line);
concat(result, right(start, order - 1, line));
return result;
}
std::vector<Point> right(Point start, int order, int line) {
std::vector<Point> result;
if (order == 0) {
result.push_back(start);
return result;
}
concat(result, down(start, order - 1, line));
start = result.back().move_with(-line, 0);
concat(result, right(start, order - 1, line));
start = result.back().move_with(0, line);
concat(result, right(start, order - 1, line));
start = result.back().move_with(line, 0);
concat(result, up(start, order - 1, line));
return result;
}
std::vector<Point> left(Point start, int order, int line) {
std::vector<Point> result;
if (order == 0) {
result.push_back(start);
return result;
}
concat(result, up(start, order - 1, line));
start = result.back().move_with(line, 0);
concat(result, left(start, order - 1, line));
start = result.back().move_with(0, -line);
concat(result, left(start, order - 1, line));
start = result.back().move_with(-line, 0);
concat(result, down(start, order - 1, line));
return result;
}
public:
HilbertCurve(int order, int width) {
curve_ = up(Point(0, width), order, width / count_lines(order));
}
static int count_lines(int order) {
if (order == 1) {
return 1;
}
return 2 * count_lines(order - 1) + 1;
}
void draw(std::ostream& out) {
out << "newpath" << std::endl;
out << curve_[0].get_x() << " " << curve_[0].get_y() << " moveto" << std::endl;
for (int i = 1; i < curve_.size(); i++) {
out << curve_[i].get_x() << " " << curve_[i].get_y() << " lineto" << std::endl;
}
out << "stroke" << std::endl;
}
};
int main() {
HilbertCurve hc(10, 10);
std::ofstream file("hilbert.ps");
hc.draw(file);
file.close();
return 0;
}