1 | /* |
2 | * Copyright 2004-2014 H2 Group. Multiple-Licensed under the MPL 2.0, |
3 | * and the EPL 1.0 (http://h2database.com/html/license.html). |
4 | * Initial Developer: H2 Group |
5 | */ |
6 | package org.h2.mvstore.rtree; |
7 | |
8 | import java.nio.ByteBuffer; |
9 | import java.util.ArrayList; |
10 | import org.h2.mvstore.DataUtils; |
11 | import org.h2.mvstore.WriteBuffer; |
12 | import org.h2.mvstore.type.DataType; |
13 | |
14 | /** |
15 | * A spatial data type. This class supports up to 31 dimensions. Each dimension |
16 | * can have a minimum and a maximum value of type float. For each dimension, the |
17 | * maximum value is only stored when it is not the same as the minimum. |
18 | */ |
19 | public class SpatialDataType implements DataType { |
20 | |
21 | private final int dimensions; |
22 | |
23 | public SpatialDataType(int dimensions) { |
24 | // Because of how we are storing the |
25 | // min-max-flag in the read/write method |
26 | // the number of dimensions must be < 32. |
27 | DataUtils.checkArgument( |
28 | dimensions >= 1 && dimensions < 32, |
29 | "Dimensions must be between 1 and 31, is {0}", dimensions); |
30 | this.dimensions = dimensions; |
31 | } |
32 | |
33 | @Override |
34 | public int compare(Object a, Object b) { |
35 | long la = ((SpatialKey) a).getId(); |
36 | long lb = ((SpatialKey) b).getId(); |
37 | return la < lb ? -1 : la > lb ? 1 : 0; |
38 | } |
39 | |
40 | /** |
41 | * Check whether two spatial values are equal. |
42 | * |
43 | * @param a the first value |
44 | * @param b the second value |
45 | * @return true if they are equal |
46 | */ |
47 | public boolean equals(Object a, Object b) { |
48 | long la = ((SpatialKey) a).getId(); |
49 | long lb = ((SpatialKey) b).getId(); |
50 | return la == lb; |
51 | } |
52 | |
53 | @Override |
54 | public int getMemory(Object obj) { |
55 | return 40 + dimensions * 4; |
56 | } |
57 | |
58 | @Override |
59 | public void read(ByteBuffer buff, Object[] obj, int len, boolean key) { |
60 | for (int i = 0; i < len; i++) { |
61 | obj[i] = read(buff); |
62 | } |
63 | } |
64 | |
65 | @Override |
66 | public void write(WriteBuffer buff, Object[] obj, int len, boolean key) { |
67 | for (int i = 0; i < len; i++) { |
68 | write(buff, obj[i]); |
69 | } |
70 | } |
71 | |
72 | @Override |
73 | public void write(WriteBuffer buff, Object obj) { |
74 | SpatialKey k = (SpatialKey) obj; |
75 | int flags = 0; |
76 | for (int i = 0; i < dimensions; i++) { |
77 | if (k.min(i) == k.max(i)) { |
78 | flags |= 1 << i; |
79 | } |
80 | } |
81 | buff.putVarInt(flags); |
82 | for (int i = 0; i < dimensions; i++) { |
83 | buff.putFloat(k.min(i)); |
84 | if ((flags & (1 << i)) == 0) { |
85 | buff.putFloat(k.max(i)); |
86 | } |
87 | } |
88 | buff.putVarLong(k.getId()); |
89 | } |
90 | |
91 | @Override |
92 | public Object read(ByteBuffer buff) { |
93 | int flags = DataUtils.readVarInt(buff); |
94 | float[] minMax = new float[dimensions * 2]; |
95 | for (int i = 0; i < dimensions; i++) { |
96 | float min = buff.getFloat(); |
97 | float max; |
98 | if ((flags & (1 << i)) != 0) { |
99 | max = min; |
100 | } else { |
101 | max = buff.getFloat(); |
102 | } |
103 | minMax[i + i] = min; |
104 | minMax[i + i + 1] = max; |
105 | } |
106 | long id = DataUtils.readVarLong(buff); |
107 | return new SpatialKey(id, minMax); |
108 | } |
109 | |
110 | /** |
111 | * Check whether the two objects overlap. |
112 | * |
113 | * @param objA the first object |
114 | * @param objB the second object |
115 | * @return true if they overlap |
116 | */ |
117 | public boolean isOverlap(Object objA, Object objB) { |
118 | SpatialKey a = (SpatialKey) objA; |
119 | SpatialKey b = (SpatialKey) objB; |
120 | for (int i = 0; i < dimensions; i++) { |
121 | if (a.max(i) < b.min(i) || a.min(i) > b.max(i)) { |
122 | return false; |
123 | } |
124 | } |
125 | return true; |
126 | } |
127 | |
128 | /** |
129 | * Increase the bounds in the given spatial object. |
130 | * |
131 | * @param bounds the bounds (may be modified) |
132 | * @param add the value |
133 | */ |
134 | public void increaseBounds(Object bounds, Object add) { |
135 | SpatialKey b = (SpatialKey) bounds; |
136 | SpatialKey a = (SpatialKey) add; |
137 | for (int i = 0; i < dimensions; i++) { |
138 | b.setMin(i, Math.min(b.min(i), a.min(i))); |
139 | b.setMax(i, Math.max(b.max(i), a.max(i))); |
140 | } |
141 | } |
142 | |
143 | /** |
144 | * Get the area increase by extending a to contain b. |
145 | * |
146 | * @param objA the bounding box |
147 | * @param objB the object |
148 | * @return the area |
149 | */ |
150 | public float getAreaIncrease(Object objA, Object objB) { |
151 | SpatialKey a = (SpatialKey) objA; |
152 | SpatialKey b = (SpatialKey) objB; |
153 | float min = a.min(0); |
154 | float max = a.max(0); |
155 | float areaOld = max - min; |
156 | min = Math.min(min, b.min(0)); |
157 | max = Math.max(max, b.max(0)); |
158 | float areaNew = max - min; |
159 | for (int i = 1; i < dimensions; i++) { |
160 | min = a.min(i); |
161 | max = a.max(i); |
162 | areaOld *= max - min; |
163 | min = Math.min(min, b.min(i)); |
164 | max = Math.max(max, b.max(i)); |
165 | areaNew *= max - min; |
166 | } |
167 | return areaNew - areaOld; |
168 | } |
169 | |
170 | /** |
171 | * Get the combined area of both objects. |
172 | * |
173 | * @param objA the first object |
174 | * @param objB the second object |
175 | * @return the area |
176 | */ |
177 | float getCombinedArea(Object objA, Object objB) { |
178 | SpatialKey a = (SpatialKey) objA; |
179 | SpatialKey b = (SpatialKey) objB; |
180 | float area = 1; |
181 | for (int i = 0; i < dimensions; i++) { |
182 | float min = Math.min(a.min(i), b.min(i)); |
183 | float max = Math.max(a.max(i), b.max(i)); |
184 | area *= max - min; |
185 | } |
186 | return area; |
187 | } |
188 | |
189 | /** |
190 | * Check whether a contains b. |
191 | * |
192 | * @param objA the bounding box |
193 | * @param objB the object |
194 | * @return the area |
195 | */ |
196 | public boolean contains(Object objA, Object objB) { |
197 | SpatialKey a = (SpatialKey) objA; |
198 | SpatialKey b = (SpatialKey) objB; |
199 | for (int i = 0; i < dimensions; i++) { |
200 | if (a.min(i) > b.min(i) || a.max(i) < b.max(i)) { |
201 | return false; |
202 | } |
203 | } |
204 | return true; |
205 | } |
206 | |
207 | /** |
208 | * Check whether a is completely inside b and does not touch the |
209 | * given bound. |
210 | * |
211 | * @param objA the object to check |
212 | * @param objB the bounds |
213 | * @return true if a is completely inside b |
214 | */ |
215 | public boolean isInside(Object objA, Object objB) { |
216 | SpatialKey a = (SpatialKey) objA; |
217 | SpatialKey b = (SpatialKey) objB; |
218 | for (int i = 0; i < dimensions; i++) { |
219 | if (a.min(i) <= b.min(i) || a.max(i) >= b.max(i)) { |
220 | return false; |
221 | } |
222 | } |
223 | return true; |
224 | } |
225 | |
226 | /** |
227 | * Create a bounding box starting with the given object. |
228 | * |
229 | * @param objA the object |
230 | * @return the bounding box |
231 | */ |
232 | Object createBoundingBox(Object objA) { |
233 | float[] minMax = new float[dimensions * 2]; |
234 | SpatialKey a = (SpatialKey) objA; |
235 | for (int i = 0; i < dimensions; i++) { |
236 | minMax[i + i] = a.min(i); |
237 | minMax[i + i + 1] = a.max(i); |
238 | } |
239 | return new SpatialKey(0, minMax); |
240 | } |
241 | |
242 | /** |
243 | * Get the most extreme pair (elements that are as far apart as possible). |
244 | * This method is used to split a page (linear split). If no extreme objects |
245 | * could be found, this method returns null. |
246 | * |
247 | * @param list the objects |
248 | * @return the indexes of the extremes |
249 | */ |
250 | public int[] getExtremes(ArrayList<Object> list) { |
251 | SpatialKey bounds = (SpatialKey) createBoundingBox(list.get(0)); |
252 | SpatialKey boundsInner = (SpatialKey) createBoundingBox(bounds); |
253 | for (int i = 0; i < dimensions; i++) { |
254 | float t = boundsInner.min(i); |
255 | boundsInner.setMin(i, boundsInner.max(i)); |
256 | boundsInner.setMax(i, t); |
257 | } |
258 | for (int i = 0; i < list.size(); i++) { |
259 | Object o = list.get(i); |
260 | increaseBounds(bounds, o); |
261 | increaseMaxInnerBounds(boundsInner, o); |
262 | } |
263 | double best = 0; |
264 | int bestDim = 0; |
265 | for (int i = 0; i < dimensions; i++) { |
266 | float inner = boundsInner.max(i) - boundsInner.min(i); |
267 | if (inner < 0) { |
268 | continue; |
269 | } |
270 | float outer = bounds.max(i) - bounds.min(i); |
271 | float d = inner / outer; |
272 | if (d > best) { |
273 | best = d; |
274 | bestDim = i; |
275 | } |
276 | } |
277 | if (best <= 0) { |
278 | return null; |
279 | } |
280 | float min = boundsInner.min(bestDim); |
281 | float max = boundsInner.max(bestDim); |
282 | int firstIndex = -1, lastIndex = -1; |
283 | for (int i = 0; i < list.size() && |
284 | (firstIndex < 0 || lastIndex < 0); i++) { |
285 | SpatialKey o = (SpatialKey) list.get(i); |
286 | if (firstIndex < 0 && o.max(bestDim) == min) { |
287 | firstIndex = i; |
288 | } else if (lastIndex < 0 && o.min(bestDim) == max) { |
289 | lastIndex = i; |
290 | } |
291 | } |
292 | return new int[] { firstIndex, lastIndex }; |
293 | } |
294 | |
295 | private void increaseMaxInnerBounds(Object bounds, Object add) { |
296 | SpatialKey b = (SpatialKey) bounds; |
297 | SpatialKey a = (SpatialKey) add; |
298 | for (int i = 0; i < dimensions; i++) { |
299 | b.setMin(i, Math.min(b.min(i), a.max(i))); |
300 | b.setMax(i, Math.max(b.max(i), a.min(i))); |
301 | } |
302 | } |
303 | |
304 | } |