Class MortonCode

1	/*
2	* Copyright (c) 2019 Martin Davis.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12
13	package org.locationtech.jts.shape.fractal;
14
15	import org.locationtech.jts.geom.Coordinate;
16
17	/**
18	* Encodes points as the index along the planar Morton (Z-order) curve.
19	* <p>
20	* The planar Morton (Z-order) curve is a continuous space-filling curve.
21	* The Morton curve defines an ordering of the
22	* points in the positive quadrant of the plane.
23	* The index of a point along the Morton curve is called the Morton code.
24	* <p>
25	* A sequence of subsets of the Morton curve can be defined by a level number.
26	* Each level subset occupies a square range.
27	* The curve at level n M<sub>n</sub> contains 2<sup>n + 1</sup> points.
28	* It fills the range square of side 2<sup>level</sup>.
29	* Curve points have ordinates in the range [0, 2<sup>level</sup> - 1].
30	* The code for a given point is identical at all levels.
31	* The level simply determines the number of points in the curve subset
32	* and the size of the range square.
33	* <p>
34	* This implementation represents codes using 32-bit integers.
35	* This allows levels 0 to 16 to be handled.
36	* The class supports encoding points
37	* and decoding the point for a given code value.
38	* <p>
39	* The Morton order has the property that it tends to preserve locality.
40	* This means that codes which are near in value will have spatially proximate
41	* points. The converse is not always true - the delta between
42	* codes for nearby points is not always small. But the average delta
43	* is small enough that the Morton order is an effective way of linearizing space
44	* to support range queries.
45	*
46	* @author Martin Davis
47	*
48	* @see MortonCurveBuilder
49	* @see HilbertCode
50	*/
51	public class MortonCode
52	{
53	/**
54	* The maximum curve level that can be represented.
55	*/
56	public static final int MAX_LEVEL = 16;
57
58	/**
59	* The number of points in the curve for the given level.
60	* The number of points is 2<sup>2 * level</sup>.
61	*
62	* @param level the level of the curve
63	* @return the number of points
64	*/
65	public static int size(int level) {
66	checkLevel(level);
67	return (int) Math.pow(2, 2 *level);
68	}
69
70	/**
71	* The maximum ordinate value for points
72	* in the curve for the given level.
73	* The maximum ordinate is 2<sup>level</sup> - 1.
74	*
75	* @param level the level of the curve
76	* @return the maximum ordinate value
77	*/
78	public static int maxOrdinate(int level) {
79	checkLevel(level);
80	return (int) Math.pow(2, level) - 1;
81	}
82
83	/**
84	* The level of the finite Morton curve which contains at least
85	* the given number of points.
86	*
87	* @param numPoints the number of points required
88	* @return the level of the curve
89	*/
90	public static int level(int numPoints) {
91	int pow2 = (int) ( (Math.log(numPoints)/Math.log(2)));
92	int level = pow2 / 2;
93	int size = size(level);
94	if (size < numPoints) level += 1;
95	return level;
96	}
97
98	private static void checkLevel(int level) {
99	if (level > MAX_LEVEL) {
100	throw new IllegalArgumentException("Level must be in range 0 to " + MAX_LEVEL);
101	}
102	}
103	/**
104	* Computes the index of the point (x,y)
105	* in the Morton curve ordering.
106	*
107	* @param x the x ordinate of the point
108	* @param y the y ordinate of the point
109	* @return the index of the point along the Morton curve
110	*/
111	public static int encode(int x, int y) {
112	return (interleave(y) << 1) + interleave(x);
113	}
114
115	private static int interleave(int x) {
116	x &= 0x0000ffff; // x = ---- ---- ---- ---- fedc ba98 7654 3210
117	x = (x ^ (x << 8)) & 0x00ff00ff; // x = ---- ---- fedc ba98 ---- ---- 7654 3210
118	x = (x ^ (x << 4)) & 0x0f0f0f0f; // x = ---- fedc ---- ba98 ---- 7654 ---- 3210
119	x = (x ^ (x << 2)) & 0x33333333; // x = --fe --dc --ba --98 --76 --54 --32 --10
120	x = (x ^ (x << 1)) & 0x55555555; // x = -f-e -d-c -b-a -9-8 -7-6 -5-4 -3-2 -1-0
121	return x;
122	}
123
124	/**
125	* Computes the point on the Morton curve
126	* for a given index.
127	*
128	* @param index the index of the point on the curve
129	* @return the point on the curve
130	*/
131	public static Coordinate decode(int index) {
132	long x = deinterleave(index);
133	long y = deinterleave(index >> 1);
134	return new Coordinate(x, y);
135	}
136
137	private static long deinterleave(int x) {
138	x = x & 0x55555555;
139	x = (x \| (x >> 1)) & 0x33333333;
140	x = (x \| (x >> 2)) & 0x0F0F0F0F;
141	x = (x \| (x >> 4)) & 0x00FF00FF;
142	x = (x \| (x >> 8)) & 0x0000FFFF;
143	return x;
144	}
145	}
146