001: // Spatial Index Library
002: //
003: // Copyright (C) 2002 Navel Ltd.
004: //
005: // This library is free software; you can redistribute it and/or
006: // modify it under the terms of the GNU Lesser General Public
007: // License as published by the Free Software Foundation; either
008: // version 2.1 of the License, or (at your option) any later version.
009: //
010: // This library is distributed in the hope that it will be useful,
011: // but WITHOUT ANY WARRANTY; without even the implied warranty of
012: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: // Lesser General Public License for more details.
014: //
015: // You should have received a copy of the GNU Lesser General Public
016: // License along with this library; if not, write to the Free Software
017: // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: //
019: // Contact information:
020: // Mailing address:
021: // Marios Hadjieleftheriou
022: // University of California, Riverside
023: // Department of Computer Science
024: // Surge Building, Room 310
025: // Riverside, CA 92521
026: //
027: // Email:
028: // marioh@cs.ucr.edu
029: package org.geotools.caching.spatialindex.spatialindex;
030:
031: public class Region implements IShape {
032: public double[] m_pLow = null;
033: public double[] m_pHigh = null;
034:
035: public Region() {
036: }
037:
038: public Region(final double[] pLow, final double[] pHigh) {
039: if (pLow.length != pHigh.length) {
040: throw new IllegalArgumentException(
041: "Region: arguments have different number of dimensions.");
042: }
043:
044: m_pLow = new double[pLow.length];
045: System.arraycopy(pLow, 0, m_pLow, 0, pLow.length);
046:
047: m_pHigh = new double[pHigh.length];
048: System.arraycopy(pHigh, 0, m_pHigh, 0, pHigh.length);
049: }
050:
051: public Region(final Point low, final Point high) {
052: if (low.m_pCoords.length != high.m_pCoords.length) {
053: throw new IllegalArgumentException(
054: "Region: arguments have different number of dimensions.");
055: }
056:
057: m_pLow = new double[low.m_pCoords.length];
058: System.arraycopy(low.m_pCoords, 0, m_pLow, 0,
059: low.m_pCoords.length);
060: m_pHigh = new double[high.m_pCoords.length];
061: System.arraycopy(high.m_pCoords, 0, m_pHigh, 0,
062: high.m_pCoords.length);
063: }
064:
065: public Region(final Region r) {
066: m_pLow = new double[r.m_pLow.length];
067: System.arraycopy(r.m_pLow, 0, m_pLow, 0, r.m_pLow.length);
068: m_pHigh = new double[r.m_pHigh.length];
069: System.arraycopy(r.m_pHigh, 0, m_pHigh, 0, r.m_pHigh.length);
070: }
071:
072: public boolean equals(Object o) {
073: if (o instanceof Region) {
074: Region r = (Region) o;
075:
076: if (r.m_pLow.length != m_pLow.length) {
077: return false;
078: }
079:
080: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
081: if ((m_pLow[cIndex] < (r.m_pLow[cIndex] - SpatialIndex.EPSILON))
082: || (m_pLow[cIndex] > (r.m_pLow[cIndex] + SpatialIndex.EPSILON))
083: || (m_pHigh[cIndex] < (r.m_pHigh[cIndex] - SpatialIndex.EPSILON))
084: || (m_pHigh[cIndex] > (r.m_pHigh[cIndex] + SpatialIndex.EPSILON))) {
085: return false;
086: }
087: }
088:
089: return true;
090: }
091:
092: return false;
093: }
094:
095: //
096: // Cloneable interface
097: //
098: public Object clone() {
099: return new Region(m_pLow, m_pHigh);
100: }
101:
102: //
103: // IShape interface
104: //
105: public boolean intersects(final IShape s) {
106: if (s instanceof Region) {
107: return intersects((Region) s);
108: }
109:
110: if (s instanceof Point) {
111: return contains((Point) s);
112: }
113:
114: throw new IllegalStateException(
115: "intersects: Not implemented yet!");
116: }
117:
118: public boolean contains(final IShape s) {
119: if (s instanceof Region) {
120: return contains((Region) s);
121: }
122:
123: if (s instanceof Point) {
124: return contains((Point) s);
125: }
126:
127: throw new IllegalStateException(
128: "contains: Not implemented yet!");
129: }
130:
131: public boolean touches(final IShape s) {
132: if (s instanceof Region) {
133: return touches((Region) s);
134: }
135:
136: if (s instanceof Point) {
137: return touches((Point) s);
138: }
139:
140: throw new IllegalStateException("touches: Not implemented yet!");
141: }
142:
143: public double[] getCenter() {
144: double[] pCoords = new double[m_pLow.length];
145:
146: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
147: pCoords[cIndex] = (m_pLow[cIndex] + m_pHigh[cIndex]) / 2.0;
148: }
149:
150: return pCoords;
151: }
152:
153: public long getDimension() {
154: return m_pLow.length;
155: }
156:
157: public Region getMBR() {
158: return new Region(m_pLow, m_pHigh);
159: }
160:
161: public double getArea() {
162: double area = 1.0;
163:
164: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
165: area *= (m_pHigh[cIndex] - m_pLow[cIndex]);
166: }
167:
168: return area;
169: }
170:
171: public double getMinimumDistance(final IShape s) {
172: if (s instanceof Region) {
173: return getMinimumDistance((Region) s);
174: }
175:
176: if (s instanceof Point) {
177: return getMinimumDistance((Point) s);
178: }
179:
180: throw new IllegalStateException(
181: "getMinimumDistance: Not implemented yet!");
182: }
183:
184: public boolean intersects(final Region r) {
185: if (m_pLow.length != r.m_pLow.length) {
186: throw new IllegalArgumentException(
187: "intersects: Shape has the wrong number of dimensions.");
188: }
189:
190: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
191: if ((m_pLow[cIndex] > r.m_pHigh[cIndex])
192: || (m_pHigh[cIndex] < r.m_pLow[cIndex])) {
193: return false;
194: }
195: }
196:
197: return true;
198: }
199:
200: public boolean contains(final Region r) {
201: if (m_pLow.length != r.m_pLow.length) {
202: throw new IllegalArgumentException(
203: "contains: Shape has the wrong number of dimensions.");
204: }
205:
206: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
207: if ((m_pLow[cIndex] > r.m_pLow[cIndex])
208: || (m_pHigh[cIndex] < r.m_pHigh[cIndex])) {
209: return false;
210: }
211: }
212:
213: return true;
214: }
215:
216: public boolean touches(final Region r) {
217: if (m_pLow.length != r.m_pLow.length) {
218: throw new IllegalArgumentException(
219: "touches: Shape has the wrong number of dimensions.");
220: }
221:
222: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
223: if (((m_pLow[cIndex] > (r.m_pLow[cIndex] - SpatialIndex.EPSILON)) && (m_pLow[cIndex] < (r.m_pLow[cIndex] + SpatialIndex.EPSILON)))
224: || ((m_pHigh[cIndex] > (r.m_pHigh[cIndex] - SpatialIndex.EPSILON)) && (m_pHigh[cIndex] < (r.m_pHigh[cIndex] + SpatialIndex.EPSILON)))) {
225: return true;
226: }
227: }
228:
229: return false;
230: }
231:
232: public double getMinimumDistance(final Region r) {
233: if (m_pLow.length != r.m_pLow.length) {
234: throw new IllegalArgumentException(
235: "getMinimumDistance: Shape has the wrong number of dimensions.");
236: }
237:
238: double ret = 0.0;
239:
240: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
241: double x = 0.0;
242:
243: if (r.m_pHigh[cIndex] < m_pLow[cIndex]) {
244: x = Math.abs(r.m_pHigh[cIndex] - m_pLow[cIndex]);
245: } else if (m_pHigh[cIndex] < r.m_pLow[cIndex]) {
246: x = Math.abs(r.m_pLow[cIndex] - m_pHigh[cIndex]);
247: }
248:
249: ret += (x * x);
250: }
251:
252: return Math.sqrt(ret);
253: }
254:
255: public boolean contains(final Point p) {
256: if (m_pLow.length != p.m_pCoords.length) {
257: throw new IllegalArgumentException(
258: "contains: Shape has the wrong number of dimensions.");
259: }
260:
261: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
262: if ((m_pLow[cIndex] > p.m_pCoords[cIndex])
263: || (m_pHigh[cIndex] < p.m_pCoords[cIndex])) {
264: return false;
265: }
266: }
267:
268: return true;
269: }
270:
271: public boolean touches(final Point p) {
272: if (m_pLow.length != p.m_pCoords.length) {
273: throw new IllegalArgumentException(
274: "touches: Shape has the wrong number of dimensions.");
275: }
276:
277: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
278: if (((m_pLow[cIndex] > (p.m_pCoords[cIndex] - SpatialIndex.EPSILON)) && (m_pLow[cIndex] < (p.m_pCoords[cIndex] + SpatialIndex.EPSILON)))
279: || ((m_pHigh[cIndex] > (p.m_pCoords[cIndex] - SpatialIndex.EPSILON)) && (m_pHigh[cIndex] < (p.m_pCoords[cIndex] + SpatialIndex.EPSILON)))) {
280: return true;
281: }
282: }
283:
284: return false;
285: }
286:
287: public double getMinimumDistance(final Point p) {
288: if (m_pLow.length != p.m_pCoords.length) {
289: throw new IllegalArgumentException(
290: "getMinimumDistance: Shape has the wrong number of dimensions.");
291: }
292:
293: double ret = 0.0;
294:
295: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
296: if (p.m_pCoords[cIndex] < m_pLow[cIndex]) {
297: ret += Math.pow(m_pLow[cIndex] - p.m_pCoords[cIndex],
298: 2.0);
299: } else if (p.m_pCoords[cIndex] > m_pHigh[cIndex]) {
300: ret += Math.pow(p.m_pCoords[cIndex] - m_pHigh[cIndex],
301: 2.0);
302: }
303: }
304:
305: return Math.sqrt(ret);
306: }
307:
308: public double getIntersectingArea(final Region r) {
309: if (m_pLow.length != r.m_pLow.length) {
310: throw new IllegalArgumentException(
311: "getIntersectingArea: Shape has the wrong number of dimensions.");
312: }
313:
314: int cIndex;
315:
316: // check for intersection.
317: // marioh: avoid function call since this is called billions of times.
318: for (cIndex = 0; cIndex < m_pLow.length; cIndex++) {
319: if ((m_pLow[cIndex] > r.m_pHigh[cIndex])
320: || (m_pHigh[cIndex] < r.m_pLow[cIndex])) {
321: return 0.0;
322: }
323: }
324:
325: double ret = 1.0;
326: double f1;
327: double f2;
328:
329: for (cIndex = 0; cIndex < m_pLow.length; cIndex++) {
330: f1 = Math.max(m_pLow[cIndex], r.m_pLow[cIndex]);
331: f2 = Math.min(m_pHigh[cIndex], r.m_pHigh[cIndex]);
332: ret *= (f2 - f1);
333: }
334:
335: return ret;
336: }
337:
338: public Region combinedRegion(final Region r) {
339: if (m_pLow.length != r.m_pLow.length) {
340: throw new IllegalArgumentException(
341: "combinedRegion: Shape has the wrong number of dimensions.");
342: }
343:
344: double[] mn = new double[m_pLow.length];
345: double[] mx = new double[m_pLow.length];
346:
347: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
348: mn[cIndex] = Math.min(m_pLow[cIndex], r.m_pLow[cIndex]);
349: mx[cIndex] = Math.max(m_pHigh[cIndex], r.m_pHigh[cIndex]);
350: }
351:
352: return new Region(mn, mx);
353: }
354:
355: public static Region combinedRegion(Region[] pRegions) {
356: double[] mn = new double[pRegions[0].m_pLow.length];
357: double[] mx = new double[pRegions[0].m_pLow.length];
358:
359: for (int cDim = 0; cDim < pRegions[0].m_pLow.length; cDim++) {
360: mn[cDim] = Double.POSITIVE_INFINITY;
361: mx[cDim] = Double.NEGATIVE_INFINITY;
362:
363: for (int cIndex = 0; cIndex < pRegions.length; cIndex++) {
364: mn[cDim] = Math.min(mn[cDim],
365: pRegions[cIndex].m_pLow[cDim]);
366: mx[cDim] = Math.max(mx[cDim],
367: pRegions[cIndex].m_pHigh[cDim]);
368: }
369: }
370:
371: return new Region(mn, mx);
372: }
373:
374: // Modifies the first argument to include the second.
375: public static void combinedRegion(Region pToModify,
376: final Region pConst) {
377: if (pToModify.m_pLow.length != pConst.m_pLow.length) {
378: throw new IllegalArgumentException(
379: "combineRegion: Shape has the wrong number of dimensions.");
380: }
381:
382: for (int cIndex = 0; cIndex < pToModify.m_pLow.length; cIndex++) {
383: pToModify.m_pLow[cIndex] = Math.min(
384: pToModify.m_pLow[cIndex], pConst.m_pLow[cIndex]);
385: pToModify.m_pHigh[cIndex] = Math.max(
386: pToModify.m_pHigh[cIndex], pConst.m_pHigh[cIndex]);
387: }
388: }
389:
390: // Returns the margin of a region. It is calcuated as the sum of 2^(d-1) * width in each dimension.
391: public double getMargin() {
392: double mul = Math.pow(2.0, ((double) m_pLow.length) - 1.0);
393: double margin = 0.0;
394:
395: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) {
396: margin += ((m_pHigh[cIndex] - m_pLow[cIndex]) * mul);
397: }
398:
399: return margin;
400: }
401:
402: public double getLow(int index) throws IndexOutOfBoundsException {
403: if (index >= m_pLow.length) {
404: throw new IndexOutOfBoundsException("" + index);
405: }
406:
407: return m_pLow[index];
408: }
409:
410: public double getHigh(int index) throws IndexOutOfBoundsException {
411: if (index >= m_pLow.length) {
412: throw new IndexOutOfBoundsException("" + index);
413: }
414:
415: return m_pHigh[index];
416: }
417:
418: public String toString() {
419: String s = "";
420:
421: for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
422: s += (m_pLow[cIndex] + " ");
423:
424: s += ": ";
425:
426: for (int cIndex = 0; cIndex < m_pHigh.length; cIndex++)
427: s += (m_pHigh[cIndex] + " ");
428:
429: return s;
430: }
431: }
|