Hilbert curve: Difference between revisions

=={{header|C++}}==

{{trans|D}}

<lang cpp>#include <algorithm>

#include <iostream>

#include <vector>

struct Point {

int x, y;

//rotate/flip a quadrant appropriately

void rot(int n, bool rx, bool ry) {

if (!ry) {

if (rx) {

x = (n - 1) - x;

y = (n - 1) - y;

}

std::swap(x, y);

}

}

int calcD(int n) {

bool rx, ry;

int d = 0;

for (int s = n >> 1; s > 0; s >>= 1) {

rx = ((x & s) != 0);

ry = ((y & s) != 0);

d += s * s * ((rx ? 3 : 0) ^ (ry ? 1 : 0));

rot(s, rx, ry);

}

return d;

}

friend std::ostream &operator<<(std::ostream &, const Point &);

};

std::ostream &operator<<(std::ostream &out, const Point &p) {

return out << '(' << p.x << ", " << p.y << ')';

}

Point fromD(int n, int d) {

Point p = { 0, 0 };

bool rx, ry;

int t = d;

for (int s = 1; s < n; s <<= 1) {

rx = ((t & 2) != 0);

ry = (((t ^ (rx ? 1 : 0)) & 1) != 0);

p.rot(s, rx, ry);

p.x += (rx ? s : 0);

p.y += (ry ? s : 0);

t >>= 2;

}

return p;

}

std::vector<Point> getPointsForCurve(int n) {

std::vector<Point> points;

for (int d = 0; d < n * n; ++d) {

points.push_back(fromD(n, d));

}

return points;

}

std::vector<std::string> drawCurve(const std::vector<Point> &points, int n) {

auto canvas = new char *[n];

for (size_t i = 0; i < n; i++) {

canvas[i] = new char[n * 3 - 2];

std::memset(canvas[i], ' ', n * 3 - 2);

}

for (int i = 1; i < points.size(); i++) {

auto lastPoint = points[i - 1];

auto curPoint = points[i];

int deltaX = curPoint.x - lastPoint.x;

int deltaY = curPoint.y - lastPoint.y;

if (deltaX == 0) {

// vertical line

int row = std::max(curPoint.y, lastPoint.y);

int col = curPoint.x * 3;

canvas[row][col] = '|';

} else {

// horizontal line

int row = curPoint.y;

int col = std::min(curPoint.x, lastPoint.x) * 3 + 1;

canvas[row][col] = '_';

canvas[row][col + 1] = '_';

}

}

std::vector<std::string> lines;

for (size_t i = 0; i < n; i++) {

std::string temp;

temp.assign(canvas[i], n * 3 - 2);

lines.push_back(temp);

}

return lines;

}

int main() {

for (int order = 1; order < 6; order++) {

int n = 1 << order;

auto points = getPointsForCurve(n);

std::cout << "Hilbert curve, order=" << order << '\n';

auto lines = drawCurve(points, n);

for (auto &line : lines) {

std::cout << line << '\n';

}

std::cout << '\n';

}

return 0;

}</lang>

{{out}}

<pre>Hilbert curve, order=1

|__|

Hilbert curve, order=2

__ __

__| |__

| __ |

|__| |__|

Hilbert curve, order=3

__ __ __ __

|__| __| |__ |__|

__ |__ __| __

| |__ __| |__ __| |

|__ __ __ __ __|

__| |__ __| |__

| __ | | __ |

|__| |__| |__| |__|

Hilbert curve, order=4

__ __ __ __ __ __ __ __ __ __

__| |__ |__| __| |__ |__| __| |__

| __ | __ |__ __| __ | __ |

|__| |__| | |__ __| |__ __| | |__| |__|

__ __ | __ __ __ __ | __ __

| |__| | |__| __| |__ |__| | |__| |

|__ __| __ |__ __| __ |__ __|

__| |__ __| |__ __| |__ __| |__ __| |__

| __ __ __ __ __ __ __ __ __ |

|__| __| |__ |__| |__| __| |__ |__|

__ |__ __| __ __ |__ __| __

| |__ __| |__ __| | | |__ __| |__ __| |

|__ __ __ __ __| |__ __ __ __ __|

__| |__ __| |__ __| |__ __| |__

| __ | | __ | | __ | | __ |

|__| |__| |__| |__| |__| |__| |__| |__|

Hilbert curve, order=5

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

|__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__|

__ |__ __| __ | __ | __ |__ __| __ | __ | __ |__ __| __

| |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__| |__| | |__ __| |__ __| |

|__ __ __ __ __| __ __ | __ __ __ __ | __ __ |__ __ __ __ __|

__| |__ __| |__ | |__| | |__| __| |__ |__| | |__| | __| |__ __| |__

| __ | | __ | |__ __| __ |__ __| __ |__ __| | __ | | __ |

|__| |__| |__| |__| __| |__ __| |__ __| |__ __| |__ __| |__ |__| |__| |__| |__|

__ __ __ __ |__ __ __ __ __ __ __ __ __ __| __ __ __ __

| |__| | | |__| | __| |__ |__| __| |__ |__| __| |__ | |__| | | |__| |

|__ __| |__ __| | __ | __ |__ __| __ | __ | |__ __| |__ __|

__| |__ __ __| |__ |__| |__| | |__ __| |__ __| | |__| |__| __| |__ __ __| |__

| __ __ __ __ | __ __ | __ __ __ __ | __ __ | __ __ __ __ |

|__| __| |__ |__| | |__| | |__| __| |__ |__| | |__| | |__| __| |__ |__|

__ |__ __| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __

| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |

|__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __|

__| |__ |__| __| |__ |__| __| |__ __| |__ |__| __| |__ |__| __| |__

| __ | __ |__ __| __ | __ | | __ | __ |__ __| __ | __ |

|__| |__| | |__ __| |__ __| | |__| |__| |__| |__| | |__ __| |__ __| | |__| |__|

__ __ | __ __ __ __ | __ __ __ __ | __ __ __ __ | __ __

| |__| | |__| __| |__ |__| | |__| | | |__| | |__| __| |__ |__| | |__| |

|__ __| __ |__ __| __ |__ __| |__ __| __ |__ __| __ |__ __|

__| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__

| __ __ __ __ __ __ __ __ __ | | __ __ __ __ __ __ __ __ __ |

|__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__|

__ |__ __| __ __ |__ __| __ __ |__ __| __ __ |__ __| __

| |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| |

|__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __|

__| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__

| __ | | __ | | __ | | __ | | __ | | __ | | __ | | __ |

|__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__|</pre>