Import Upstream version 0.6.5~20141030

1 files changed, 65 insertions, 41 deletions

diff --git a/src/de/lmu/ifi/dbs/elki/data/spatial/SpatialUtil.java b/src/de/lmu/ifi/dbs/elki/data/spatial/SpatialUtil.java
index 50ea7243..873e2e30 100644
--- a/src/de/lmu/ifi/dbs/elki/data/spatial/SpatialUtil.java
+++ b/src/de/lmu/ifi/dbs/elki/data/spatial/SpatialUtil.java
@@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.data.spatial;
  This file is part of ELKI:
  Environment for Developing KDD-Applications Supported by Index-Structures
 
- Copyright (C) 2013
+ Copyright (C) 2014
  Ludwig-Maximilians-Universität München
  Lehr- und Forschungseinheit für Datenbanksysteme
  ELKI Development Team
@@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.data.spatial;
  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-import de.lmu.ifi.dbs.elki.data.HyperBoundingBox;
 import de.lmu.ifi.dbs.elki.data.ModifiableHyperBoundingBox;
 import de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike.ArrayAdapter;
 
@@ -35,7 +34,7 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike.ArrayAdapter;
  * @apiviz.landmark
  * 
  * @apiviz.uses SpatialComparable oneway - - «compares»
- * @apiviz.has HyperBoundingBox oneway - - «creates»
+ * @apiviz.has ModifiableHyperBoundingBox oneway - - «creates»
  */
 // IMPORTANT NOTE: when editing this class, bear in mind that the dimension
 // numbers start at 1 or 0 depending on the context!
@@ -57,7 +56,7 @@ public final class SpatialUtil {
    */
   public static int assertSameDimensionality(SpatialComparable box1, SpatialComparable box2) {
     final int dim = box1.getDimensionality();
-    if (dim != box2.getDimensionality()) {
+    if(dim != box2.getDimensionality()) {
       throw new IllegalArgumentException("The spatial objects do not have the same dimensionality!");
     }
     return dim;
@@ -72,7 +71,7 @@ public final class SpatialUtil {
   public static double[] getMin(SpatialComparable box) {
     final int dim = box.getDimensionality();
     double[] min = new double[dim];
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       min[i] = box.getMin(i);
     }
     return min;
@@ -87,7 +86,7 @@ public final class SpatialUtil {
   public static double[] getMax(SpatialComparable box) {
     final int dim = box.getDimensionality();
     double[] max = new double[dim];
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       max[i] = box.getMax(i);
     }
     return max;
@@ -102,8 +101,8 @@ public final class SpatialUtil {
    */
   public static boolean intersects(SpatialComparable box1, SpatialComparable box2) {
     final int dim = assertSameDimensionality(box1, box2);
-    for (int i = 0; i < dim; i++) {
-      if (box2.getMax(i) < box1.getMin(i) || box1.getMax(i) < box2.getMin(i)) {
+    for(int i = 0; i < dim; i++) {
+      if(box2.getMax(i) < box1.getMin(i) || box1.getMax(i) < box2.getMin(i)) {
         return false;
       }
     }
@@ -121,8 +120,8 @@ public final class SpatialUtil {
    */
   public static boolean contains(SpatialComparable box1, SpatialComparable box2) {
     final int dim = assertSameDimensionality(box1, box2);
-    for (int i = 0; i < dim; i++) {
-      if (box2.getMin(i) < box1.getMin(i) || box1.getMax(i) < box2.getMax(i)) {
+    for(int i = 0; i < dim; i++) {
+      if(box2.getMin(i) < box1.getMin(i) || box1.getMax(i) < box2.getMax(i)) {
         return false;
       }
     }
@@ -140,12 +139,12 @@ public final class SpatialUtil {
    */
   public static boolean contains(SpatialComparable box, double[] point) {
     final int dim = box.getDimensionality();
-    if (dim != point.length) {
+    if(dim != point.length) {
       throw new IllegalArgumentException("This HyperBoundingBox and the given point need same dimensionality");
     }
 
-    for (int i = 0; i < dim; i++) {
-      if (box.getMin(i) > point[i] || box.getMax(i) < point[i]) {
+    for(int i = 0; i < dim; i++) {
+      if(box.getMin(i) > point[i] || box.getMax(i) < point[i]) {
         return false;
       }
     }
@@ -161,9 +160,9 @@ public final class SpatialUtil {
   public static double volume(SpatialComparable box) {
     final int dim = box.getDimensionality();
     double vol = 1.;
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       double delta = box.getMax(i) - box.getMin(i);
-      if (delta == 0.) {
+      if(delta == 0.) {
         return 0.;
       }
       vol *= delta;
@@ -181,7 +180,7 @@ public final class SpatialUtil {
   public static double volumeUnion(SpatialComparable box1, SpatialComparable box2) {
     final int dim = assertSameDimensionality(box1, box2);
     double volume = 1.;
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       final double min = Math.min(box1.getMin(i), box2.getMin(i));
       final double max = Math.max(box1.getMax(i), box2.getMax(i));
       volume *= (max - min);
@@ -199,9 +198,9 @@ public final class SpatialUtil {
   public static double volumeScaled(SpatialComparable box, double scale) {
     final int dim = box.getDimensionality();
     double vol = 1.;
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       double delta = box.getMax(i) - box.getMin(i);
-      if (delta == 0.) {
+      if(delta == 0.) {
         return 0.;
       }
       vol *= delta * scale;
@@ -220,7 +219,7 @@ public final class SpatialUtil {
   public static double volumeUnionScaled(SpatialComparable box1, SpatialComparable box2, double scale) {
     final int dim = assertSameDimensionality(box1, box2);
     double volume = 1.;
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       final double min = Math.min(box1.getMin(i), box2.getMin(i));
       final double max = Math.max(box1.getMax(i), box2.getMax(i));
       volume *= (max - min) * scale;
@@ -239,7 +238,7 @@ public final class SpatialUtil {
     final int dim = assertSameDimensionality(exist, addit);
     double v1 = 1.;
     double v2 = 1.;
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       final double emin = exist.getMin(i);
       final double emax = exist.getMax(i);
       final double amin = addit.getMin(i);
@@ -265,7 +264,7 @@ public final class SpatialUtil {
     final int dim = assertSameDimensionality(exist, addit);
     double v1 = 1.;
     double v2 = 1.;
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       final double emin = exist.getMin(i);
       final double emax = exist.getMax(i);
       final double amin = addit.getMin(i);
@@ -288,7 +287,7 @@ public final class SpatialUtil {
   public static double perimeter(SpatialComparable box) {
     final int dim = box.getDimensionality();
     double perimeter = 0.;
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       perimeter += box.getMax(i) - box.getMin(i);
     }
     return perimeter;
@@ -310,7 +309,7 @@ public final class SpatialUtil {
     // the overlap volume
     double overlap = 1.;
 
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       // The maximal value of that overlap box in the current
       // dimension is the minimum of the max values.
       omax = Math.min(box1.getMax(i), box2.getMax(i));
@@ -318,7 +317,7 @@ public final class SpatialUtil {
       omin = Math.max(box1.getMin(i), box2.getMin(i));
 
       // if omax <= omin in any dimension, the overlap box has a volume of zero
-      if (omax <= omin) {
+      if(omax <= omin) {
         return 0.;
       }
 
@@ -345,7 +344,7 @@ public final class SpatialUtil {
     double vol1 = 1.;
     double vol2 = 1.;
 
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       final double box1min = box1.getMin(i);
       final double box1max = box1.getMax(i);
       final double box2min = box2.getMin(i);
@@ -355,7 +354,7 @@ public final class SpatialUtil {
       final double omin = Math.max(box1min, box2min);
 
       // if omax <= omin in any dimension, the overlap box has a volume of zero
-      if (omax <= omin) {
+      if(omax <= omin) {
         return 0.;
       }
 
@@ -381,7 +380,7 @@ public final class SpatialUtil {
     double[] min = new double[dim];
     double[] max = new double[dim];
 
-    for (int i = 0; i < dim; i++) {
+    for(int i = 0; i < dim; i++) {
       min[i] = Math.min(box1.getMin(i), box2.getMin(i));
       max[i] = Math.max(box1.getMax(i), box2.getMax(i));
     }
@@ -395,17 +394,17 @@ public final class SpatialUtil {
    * @param mbr2 the second MBR
    * @return the union of the two specified MBRs
    */
-  public static HyperBoundingBox unionTolerant(SpatialComparable mbr1, SpatialComparable mbr2) {
-    if (mbr1 == null && mbr2 == null) {
+  public static ModifiableHyperBoundingBox unionTolerant(SpatialComparable mbr1, SpatialComparable mbr2) {
+    if(mbr1 == null && mbr2 == null) {
       return null;
     }
-    if (mbr1 == null) {
+    if(mbr1 == null) {
       // Clone - intentionally
-      return new HyperBoundingBox(mbr2);
+      return new ModifiableHyperBoundingBox(mbr2);
     }
-    if (mbr2 == null) {
+    if(mbr2 == null) {
       // Clone - intentionally
-      return new HyperBoundingBox(mbr1);
+      return new ModifiableHyperBoundingBox(mbr1);
     }
     return union(mbr1, mbr2);
   }
@@ -429,14 +428,14 @@ public final class SpatialUtil {
       final E first = getter.get(data, 0);
       dim = first.getDimensionality();
       mbr = new double[2 * dim];
-      for (int d = 0; d < dim; d++) {
+      for(int d = 0; d < dim; d++) {
         mbr[d] = first.getMin(d);
         mbr[dim + d] = first.getMax(d);
       }
     } // Remaining entries
-    for (int i = 1; i < num; i++) {
+    for(int i = 1; i < num; i++) {
       E next = getter.get(data, i);
-      for (int d = 0; d < dim; d++) {
+      for(int d = 0; d < dim; d++) {
         mbr[d] = Math.min(mbr[d], next.getMin(d));
         mbr[dim + d] = Math.max(mbr[dim + d], next.getMax(d));
       }
@@ -445,6 +444,31 @@ public final class SpatialUtil {
   }
 
   /**
+   * Calculate the intersection of the two MBRs or <code>null</code> if they do
+   * not intersect. <em>Note</em>: if the given MBRs intersect in only one point
+   * of any dimension, this method still returns a result!
+   * 
+   * @param box1 the first MBR
+   * @param box2 the second MBR
+   * @return the union of the two specified MBRs
+   */
+  public static ModifiableHyperBoundingBox intersection(final SpatialComparable box1, final SpatialComparable box2) {
+    final int dim = assertSameDimensionality(box1, box2);
+
+    double[] min = new double[dim];
+    double[] max = new double[dim];
+
+    for(int i = 0; i < dim; i++) {
+      min[i] = Math.max(box1.getMin(i), box2.getMin(i));
+      max[i] = Math.min(box1.getMax(i), box2.getMax(i));
+      if(min[i] > max[i]) {
+        return null;
+      }
+    }
+    return new ModifiableHyperBoundingBox(min, max);
+  }
+
+  /**
    * Returns the centroid of this SpatialComparable.
    * 
    * @param obj Spatial object to process
@@ -453,7 +477,7 @@ public final class SpatialUtil {
   public static double[] centroid(SpatialComparable obj) {
     final int dim = obj.getDimensionality();
     double[] centroid = new double[dim];
-    for (int d = 0; d < dim; d++) {
+    for(int d = 0; d < dim; d++) {
       centroid[d] = (obj.getMax(d) + obj.getMin(d)) * .5;
     }
     return centroid;
@@ -467,14 +491,14 @@ public final class SpatialUtil {
    * @return true when the boxes are equal
    */
   public static boolean equals(SpatialComparable box1, SpatialComparable box2) {
-    if (box1.getDimensionality() != box2.getDimensionality()) {
+    if(box1.getDimensionality() != box2.getDimensionality()) {
       return false;
     }
-    for (int i = 0; i < box1.getDimensionality(); i++) {
-      if (box1.getMin(i) != box2.getMin(i)) {
+    for(int i = 0; i < box1.getDimensionality(); i++) {
+      if(box1.getMin(i) != box2.getMin(i)) {
         return false;
       }
-      if (box1.getMax(i) != box2.getMax(i)) {
+      if(box1.getMax(i) != box2.getMax(i)) {
         return false;
       }
     }