File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\mvstore\rtree\SpatialType.java.html

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