1 files changed, 202 insertions, 12 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 f3bd030f..731c021a 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) 2011
+ Copyright (C) 2012
  Ludwig-Maximilians-Universität München
  Lehr- und Forschungseinheit für Datenbanksysteme
  ELKI Development Team
@@ -24,6 +24,9 @@ package de.lmu.ifi.dbs.elki.data.spatial;
  */
 
 import de.lmu.ifi.dbs.elki.data.HyperBoundingBox;
+import de.lmu.ifi.dbs.elki.data.ModifiableHyperBoundingBox;
+import de.lmu.ifi.dbs.elki.logging.LoggingConfiguration;
+import de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike.ArrayAdapter;
 
 /**
  * Utility class with spatial functions.
@@ -76,7 +79,7 @@ public final class SpatialUtil {
   public static boolean intersects(SpatialComparable box1, SpatialComparable box2) {
     final int dim = box1.getDimensionality();
     if(dim != box2.getDimensionality()) {
-      throw new IllegalArgumentException("The spatial objects do not have the same dimensionality!");
+      throw new IllegalArgumentException("The spatial objects do not have the same dimensionality: " + box1.getDimensionality() + " " + box2.getDimensionality());
     }
     boolean intersect = true;
     for(int i = 1; i <= dim; i++) {
@@ -146,19 +149,138 @@ public final class SpatialUtil {
     double vol = 1;
     final int dim = box.getDimensionality();
     for(int i = 1; i <= dim; i++) {
-      vol *= box.getMax(i) - box.getMin(i);
+      double delta = box.getMax(i) - box.getMin(i);
+      if(delta == 0.0) {
+        return 0.0;
+      }
+      vol *= delta;
+    }
+    return vol;
+  }
+
+  /**
+   * Compute the volume (area) of the union of two MBRs
+   * 
+   * @param r1 First object
+   * @param r2 Second object
+   * @return Volume of union
+   */
+  public static double volumeUnion(SpatialComparable r1, SpatialComparable r2) {
+    final int dim1 = r1.getDimensionality();
+    final int dim2 = r2.getDimensionality();
+    assert (!LoggingConfiguration.DEBUG || dim1 == dim2) : "Computing union with different dimensionality: " + dim1 + " vs. " + dim2;
+    double volume = 1.0;
+    for(int i = 1; i <= dim1; i++) {
+      final double min = Math.min(r1.getMin(i), r2.getMin(i));
+      final double max = Math.max(r1.getMax(i), r2.getMax(i));
+      volume *= (max - min);
+    }
+    return volume;
+  }
+
+  /**
+   * Computes the volume of this SpatialComparable
+   * 
+   * @param scale Scaling factor
+   * @return the volume of this SpatialComparable
+   */
+  public static double volumeScaled(SpatialComparable box, double scale) {
+    double vol = 1;
+    final int dim = box.getDimensionality();
+    for(int i = 1; i <= dim; i++) {
+      double delta = box.getMax(i) - box.getMin(i);
+      if(delta == 0.0) {
+        return 0.0;
+      }
+      vol *= delta * scale;
     }
     return vol;
   }
 
   /**
+   * Compute the volume (area) of the union of two MBRs
+   * 
+   * @param r1 First object
+   * @param r2 Second object
+   * @param scale Scaling factor
+   * @return Volume of union
+   */
+  public static double volumeUnionScaled(SpatialComparable r1, SpatialComparable r2, double scale) {
+    final int dim1 = r1.getDimensionality();
+    final int dim2 = r2.getDimensionality();
+    assert (!LoggingConfiguration.DEBUG || dim1 == dim2) : "Computing union with different dimensionality: " + dim1 + " vs. " + dim2;
+    double volume = 1.0;
+    for(int i = 1; i <= dim1; i++) {
+      final double min = Math.min(r1.getMin(i), r2.getMin(i));
+      final double max = Math.max(r1.getMax(i), r2.getMax(i));
+      volume *= (max - min) * scale;
+    }
+    return volume;
+  }
+
+  /**
+   * Compute the enlargement obtained by adding an object to an existing object.
+   * 
+   * @param exist Existing rectangle
+   * @param addit Additional rectangle
+   * @return Enlargement factor
+   */
+  public static double enlargement(SpatialComparable exist, SpatialComparable addit) {
+    final int dim1 = exist.getDimensionality();
+    final int dim2 = addit.getDimensionality();
+    assert (!LoggingConfiguration.DEBUG || dim1 == dim2) : "Computing union with different dimensionality: " + dim1 + " vs. " + dim2;
+    double v1 = 1.0;
+    double v2 = 1.0;
+    for(int i = 1; i <= dim1; i++) {
+      final double emin = exist.getMin(i);
+      final double emax = exist.getMax(i);
+      final double amin = addit.getMin(i);
+      final double amax = addit.getMax(i);
+
+      final double min = Math.min(emin, amin);
+      final double max = Math.max(emax, amax);
+      v1 *= (max - min);
+      v2 *= (emax - emin);
+    }
+    return v2 - v1;
+  }
+
+  /**
+   * Compute the enlargement obtained by adding an object to an existing object.
+   * 
+   * @param exist Existing rectangle
+   * @param addit Additional rectangle
+   * @param scale Scaling helper
+   * @return Enlargement factor
+   */
+  public static double enlargementScaled(SpatialComparable exist, SpatialComparable addit, double scale) {
+    final int dim1 = exist.getDimensionality();
+    final int dim2 = addit.getDimensionality();
+    assert (!LoggingConfiguration.DEBUG || dim1 == dim2) : "Computing union with different dimensionality: " + dim1 + " vs. " + dim2;
+    double v1 = 1.0;
+    double v2 = 1.0;
+    for(int i = 1; i <= dim1; i++) {
+      final double emin = exist.getMin(i);
+      final double emax = exist.getMax(i);
+      final double amin = addit.getMin(i);
+      final double amax = addit.getMax(i);
+
+      final double min = Math.min(emin, amin);
+      final double max = Math.max(emax, amax);
+      v1 *= (max - min) * scale;
+      v2 *= (emax - emin) * scale;
+    }
+    return v2 - v1;
+  }
+
+  /**
    * Computes the perimeter of this SpatialComparable.
    * 
    * @return the perimeter of this SpatialComparable
    */
   public static double perimeter(SpatialComparable box) {
-    double perimeter = 0;
     final int dim = box.getDimensionality();
+    double perimeter = 0;
     for(int i = 1; i <= dim; i++) {
       perimeter += box.getMax(i) - box.getMin(i);
     }
@@ -166,15 +288,13 @@ public final class SpatialUtil {
   }
 
   /**
-   * Computes the volume of the overlapping box between two SpatialComparables
-   * and return the relation between the volume of the overlapping box and the
-   * volume of both SpatialComparable.
+   * Computes the volume of the overlapping box between two SpatialComparables.
    * 
    * @param box1 the first SpatialComparable
    * @param box2 the second SpatialComparable
-   * @return the overlap volume in relation to the singular volumes.
+   * @return the overlap volume.
    */
-  public static double relativeOverlap(SpatialComparable box1, SpatialComparable box2) {
+  public static double overlap(SpatialComparable box1, SpatialComparable box2) {
     final int dim = box1.getDimensionality();
     if(dim != box2.getDimensionality()) {
       throw new IllegalArgumentException("This HyperBoundingBox and the given HyperBoundingBox need same dimensionality");
@@ -201,7 +321,49 @@ public final class SpatialUtil {
       overlap *= omax - omin;
     }
 
-    return overlap / (volume(box1) + volume(box2));
+    return overlap;
+  }
+
+  /**
+   * Computes the volume of the overlapping box between two SpatialComparables
+   * and return the relation between the volume of the overlapping box and the
+   * volume of both SpatialComparable.
+   * 
+   * @param box1 the first SpatialComparable
+   * @param box2 the second SpatialComparable
+   * @return the overlap volume in relation to the singular volumes.
+   */
+  public static double relativeOverlap(SpatialComparable box1, SpatialComparable box2) {
+    final int dim = box1.getDimensionality();
+    if(dim != box2.getDimensionality()) {
+      throw new IllegalArgumentException("This HyperBoundingBox and the given HyperBoundingBox need same dimensionality");
+    }
+
+    // the overlap volume
+    double overlap = 1.0;
+    double vol1 = 1.0;
+    double vol2 = 1.0;
+
+    for(int i = 1; i <= dim; i++) {
+      final double box1min = box1.getMin(i);
+      final double box1max = box1.getMax(i);
+      final double box2min = box2.getMin(i);
+      final double box2max = box2.getMax(i);
+
+      final double omax = Math.min(box1max, box2max);
+      final double omin = Math.max(box1min, box2min);
+
+      // if omax <= omin in any dimension, the overlap box has a volume of zero
+      if(omax <= omin) {
+        return 0.0;
+      }
+
+      overlap *= omax - omin;
+      vol1 *= box1max - box1min;
+      vol2 *= box2max - box2min;
+    }
+
+    return overlap / (vol1 + vol2);
   }
 
   /**
@@ -212,7 +374,7 @@ public final class SpatialUtil {
    * @return the union HyperBoundingBox of this HyperBoundingBox and the given
    *         HyperBoundingBox
    */
-  public static HyperBoundingBox union(SpatialComparable box1, SpatialComparable box2) {
+  public static ModifiableHyperBoundingBox union(SpatialComparable box1, SpatialComparable box2) {
     final int dim = box1.getDimensionality();
     if(dim != box2.getDimensionality()) {
       throw new IllegalArgumentException("This HyperBoundingBox and the given HyperBoundingBox need same dimensionality");
@@ -225,7 +387,7 @@ public final class SpatialUtil {
       min[i - 1] = Math.min(box1.getMin(i), box2.getMin(i));
       max[i - 1] = Math.max(box1.getMax(i), box2.getMax(i));
     }
-    return new HyperBoundingBox(min, max);
+    return new ModifiableHyperBoundingBox(min, max);
   }
 
   /**
@@ -251,6 +413,34 @@ public final class SpatialUtil {
   }
 
   /**
+   * Compute the union of a number of objects as a flat MBR (low-level, for
+   * index structures)
+   * 
+   * @param data Object
+   * @param getter Array adapter
+   * @return Flat MBR
+   */
+  public static <E extends SpatialComparable, A> double[] unionFlatMBR(A data, ArrayAdapter<E, ? super A> getter) {
+    final int num = getter.size(data);
+    assert (num > 0) : "Cannot compute MBR of empty set.";
+    final E first = getter.get(data, 0);
+    final int dim = first.getDimensionality();
+    double[] mbr = new double[2 * dim];
+    for(int d = 0; d < dim; d++) {
+      mbr[d] = first.getMin(d + 1);
+      mbr[dim + d] = first.getMax(d + 1);
+    }
+    for(int i = 1; i < num; i++) {
+      E next = getter.get(data, i);
+      for(int d = 0; d < dim; d++) {
+        mbr[d] = Math.min(mbr[d], next.getMin(d + 1));
+        mbr[dim + d] = Math.max(mbr[dim + d], next.getMax(d + 1));
+      }
+    }
+    return mbr;
+  }
+
+  /**
    * Returns the centroid of this SpatialComparable.
    * 
    * @param obj Spatial object to process