Hilbert curve: Difference between revisions
Content added Content deleted
No edit summary |
(Added Java implementation) |
||
Line 140: | Line 140: | ||
260 PLOT LEFT 90*P; |
260 PLOT LEFT 90*P; |
||
270 END DEF</lang> |
270 END DEF</lang> |
||
=={{header|Java}}== |
|||
<lang java>// Translation from https://en.wikipedia.org/wiki/Hilbert_curve |
|||
import java.util.ArrayList; |
|||
import java.util.Arrays; |
|||
import java.util.List; |
|||
public class HilbertCurve { |
|||
public static class Point { |
|||
public int x; |
|||
public int y; |
|||
public Point(int x, int y) { |
|||
this.x = x; |
|||
this.y = y; |
|||
} |
|||
public String toString() { |
|||
return "(" + x + ", " + y + ")"; |
|||
} |
|||
//rotate/flip a quadrant appropriately |
|||
public void rot(int n, boolean rx, boolean ry) { |
|||
if (!ry) { |
|||
if (rx) { |
|||
x = (n - 1) - x; |
|||
y = (n - 1) - y; |
|||
} |
|||
//Swap x and y |
|||
int t = x; |
|||
x = y; |
|||
y = t; |
|||
} |
|||
return; |
|||
} |
|||
public int calcD(int n) { |
|||
boolean 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; |
|||
} |
|||
} |
|||
public static Point fromD(int n, int d) { |
|||
Point p = new Point(0, 0); |
|||
boolean 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; |
|||
} |
|||
public static List<Point> getPointsForCurve(int n) { |
|||
List<Point> points = new ArrayList<Point>(); |
|||
for (int d = 0; d < (n * n); d++) { |
|||
Point p = fromD(n, d); |
|||
points.add(p); |
|||
} |
|||
return points; |
|||
} |
|||
public static List<String> drawCurve(List<Point> points, int n) { |
|||
char[][] canvas = new char[n][n * 3 - 2]; |
|||
for (char[] line : canvas) { |
|||
Arrays.fill(line, ' '); |
|||
} |
|||
for (int i = 1; i < points.size(); i++) { |
|||
Point lastPoint = points.get(i - 1); |
|||
Point curPoint = points.get(i); |
|||
int deltaX = curPoint.x - lastPoint.x; |
|||
int deltaY = curPoint.y - lastPoint.y; |
|||
if (deltaX == 0) { |
|||
if (deltaY == 0) { |
|||
// A mistake has been made |
|||
throw new IllegalStateException("Duplicate point, deltaX=" + deltaX + ", deltaY=" + deltaY); |
|||
} |
|||
// Vertical line |
|||
int row = Math.max(curPoint.y, lastPoint.y); |
|||
int col = curPoint.x * 3; |
|||
canvas[row][col] = '|'; |
|||
} |
|||
else { |
|||
if (deltaY != 0) { |
|||
// A mistake has been made |
|||
throw new IllegalStateException("Diagonal line, deltaX=" + deltaX + ", deltaY=" + deltaY); |
|||
} |
|||
// Horizontal line |
|||
int row = curPoint.y; |
|||
int col = Math.min(curPoint.x, lastPoint.x) * 3 + 1; |
|||
canvas[row][col] = '_'; |
|||
canvas[row][col + 1] = '_'; |
|||
} |
|||
} |
|||
List<String> lines = new ArrayList<String>(); |
|||
for (char[] row : canvas) { |
|||
String line = new String(row); |
|||
lines.add(line); |
|||
} |
|||
return lines; |
|||
} |
|||
public static void main(String... args) { |
|||
for (int order = 1; order <= 5; order++) { |
|||
int n = (1 << order); |
|||
List<Point> points = getPointsForCurve(n); |
|||
System.out.println("Hilbert curve, order=" + order); |
|||
List<String> lines = drawCurve(points, n); |
|||
for (String line : lines) { |
|||
System.out.println(line); |
|||
} |
|||
System.out.println(); |
|||
} |
|||
return; |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>Hilbert curve, order=1 |
|||
|__| |
|||
Hilbert curve, order=2 |
|||
__ __ |
|||
__| |__ |
|||
| __ | |
|||
|__| |__| |
|||
Hilbert curve, order=3 |
|||
__ __ __ __ |
|||
|__| __| |__ |__| |
|||
__ |__ __| __ |
|||
| |__ __| |__ __| | |
|||
|__ __ __ __ __| |
|||
__| |__ __| |__ |
|||
| __ | | __ | |
|||
|__| |__| |__| |__| |
|||
Hilbert curve, order=4 |
|||
__ __ __ __ __ __ __ __ __ __ |
|||
__| |__ |__| __| |__ |__| __| |__ |
|||
| __ | __ |__ __| __ | __ | |
|||
|__| |__| | |__ __| |__ __| | |__| |__| |
|||
__ __ | __ __ __ __ | __ __ |
|||
| |__| | |__| __| |__ |__| | |__| | |
|||
|__ __| __ |__ __| __ |__ __| |
|||
__| |__ __| |__ __| |__ __| |__ __| |__ |
|||
| __ __ __ __ __ __ __ __ __ | |
|||
|__| __| |__ |__| |__| __| |__ |__| |
|||
__ |__ __| __ __ |__ __| __ |
|||
| |__ __| |__ __| | | |__ __| |__ __| | |
|||
|__ __ __ __ __| |__ __ __ __ __| |
|||
__| |__ __| |__ __| |__ __| |__ |
|||
| __ | | __ | | __ | | __ | |
|||
|__| |__| |__| |__| |__| |__| |__| |__| |
|||
Hilbert curve, order=5 |
|||
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ |
|||
|__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| |
|||
__ |__ __| __ | __ | __ |__ __| __ | __ | __ |__ __| __ |
|||
| |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |
|||
|__ __ __ __ __| __ __ | __ __ __ __ | __ __ |__ __ __ __ __| |
|||
__| |__ __| |__ | |__| | |__| __| |__ |__| | |__| | __| |__ __| |__ |
|||
| __ | | __ | |__ __| __ |__ __| __ |__ __| | __ | | __ | |
|||
|__| |__| |__| |__| __| |__ __| |__ __| |__ __| |__ __| |__ |__| |__| |__| |__| |
|||
__ __ __ __ |__ __ __ __ __ __ __ __ __ __| __ __ __ __ |
|||
| |__| | | |__| | __| |__ |__| __| |__ |__| __| |__ | |__| | | |__| | |
|||
|__ __| |__ __| | __ | __ |__ __| __ | __ | |__ __| |__ __| |
|||
__| |__ __ __| |__ |__| |__| | |__ __| |__ __| | |__| |__| __| |__ __ __| |__ |
|||
| __ __ __ __ | __ __ | __ __ __ __ | __ __ | __ __ __ __ | |
|||
|__| __| |__ |__| | |__| | |__| __| |__ |__| | |__| | |__| __| |__ |__| |
|||
__ |__ __| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __ |
|||
| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| | |
|||
|__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __| |
|||
__| |__ |__| __| |__ |__| __| |__ __| |__ |__| __| |__ |__| __| |__ |
|||
| __ | __ |__ __| __ | __ | | __ | __ |__ __| __ | __ | |
|||
|__| |__| | |__ __| |__ __| | |__| |__| |__| |__| | |__ __| |__ __| | |__| |__| |
|||
__ __ | __ __ __ __ | __ __ __ __ | __ __ __ __ | __ __ |
|||
| |__| | |__| __| |__ |__| | |__| | | |__| | |__| __| |__ |__| | |__| | |
|||
|__ __| __ |__ __| __ |__ __| |__ __| __ |__ __| __ |__ __| |
|||
__| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ |
|||
| __ __ __ __ __ __ __ __ __ | | __ __ __ __ __ __ __ __ __ | |
|||
|__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| |
|||
__ |__ __| __ __ |__ __| __ __ |__ __| __ __ |__ __| __ |
|||
| |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | |
|||
|__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| |
|||
__| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ |
|||
| __ | | __ | | __ | | __ | | __ | | __ | | __ | | __ | |
|||
|__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |