[mlpack-svn] r10862 - in mlpack/trunk/src/mlpack: core/tree tests
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Fri Dec 16 15:11:14 EST 2011
Author: vlad321
Date: 2011-12-16 15:11:14 -0500 (Fri, 16 Dec 2011)
New Revision: 10862
Modified:
mlpack/trunk/src/mlpack/core/tree/periodichrectbound_impl.hpp
mlpack/trunk/src/mlpack/tests/tree_test.cpp
Log:
The test cases for maximum periodic distance, as well as the code for both versions of the maximum periodic distance.
Modified: mlpack/trunk/src/mlpack/core/tree/periodichrectbound_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/periodichrectbound_impl.hpp 2011-12-16 18:48:00 UTC (rev 10861)
+++ mlpack/trunk/src/mlpack/core/tree/periodichrectbound_impl.hpp 2011-12-16 20:11:14 UTC (rev 10862)
@@ -123,34 +123,13 @@
/**
* Calculates minimum bound-to-point squared distance.
*
-template<int t_pow>
-double PeriodicHRectBound<t_pow>::MinDistance(const arma::vec& point) const
-{
- double sum = 0;
+ */
- for (size_t d = 0; d < dim_; d++)
- {
- double a = point[d];
- double v = 0, bh;
- bh = bounds_[d].Hi() - bounds_[d].Lo();
- bh = bh - floor(bh / box_[d]) * box_[d];
- a = a - bounds_[d].Lo();
- a = a - floor(a / box_[d]) * box_[d];
-
- if (bh > a)
- v = std::min( a - bh, box_[d]-a);
-
- sum += pow(v, (double) t_pow);
- }
-
- return pow(sum, 2.0 / (double) t_pow);
-}*/
-
template<int t_pow>
double PeriodicHRectBound<t_pow>::MinDistance(const arma::vec& point) const
{
arma::vec point2 = point;
- double total_min = 0;
+ double totalMin = 0;
//Create the mirrored images. The minimum distance from the bound to a
//mirrored point is the minimum periodic distance.
arma::vec box = box_;
@@ -177,7 +156,7 @@
point3[i] -= box[i];
}
- double temp_min;
+ double tempMin;
double sum = 0;
double lower, higher;
@@ -185,15 +164,15 @@
higher = point3[i] - bounds_[i].Hi();
sum += pow((lower + fabs(lower)) + (higher + fabs(higher)), (double) t_pow);
- temp_min = pow(sum, 2.0 / (double) t_pow) / 4.0;
+ tempMin = pow(sum, 2.0 / (double) t_pow) / 4.0;
- if( temp_min < min)
- min = temp_min;
+ if (tempMin < min)
+ min = tempMin;
}
- total_min += min;
+ totalMin += min;
}
- return total_min;
+ return totalMin;
}
@@ -201,44 +180,13 @@
* Calculates minimum bound-to-bound squared distance.
*
* Example: bound1.MinDistance(other) for minimum squared distance.
- *
+ */
template<int t_pow>
double PeriodicHRectBound<t_pow>::MinDistance(
const PeriodicHRectBound& other) const
{
- double sum = 0;
-
- Log::Assert(dim_ == other.dim_);
-
- for (size_t d = 0; d < dim_; d++){
- double v = 0, d1, d2, d3;
- d1 = ((bounds_[d].Hi() > bounds_[d].Lo()) |
- (other.bounds_[d].Hi() > other.bounds_[d].Lo())) *
- std::min(other.bounds_[d].Lo() - bounds_[d].Hi(),
- bounds_[d].Lo() - other.bounds_[d].Hi());
- d2 = ((bounds_[d].Hi() > bounds_[d].Lo()) &
- (other.bounds_[d].Hi() > other.bounds_[d].Lo())) *
- std::min(other.bounds_[d].Lo() - bounds_[d].Hi(),
- bounds_[d].Lo() - other.bounds_[d].Hi() + box_[d]);
- d3 = ((bounds_[d].Hi() > bounds_[d].Lo()) &
- (other.bounds_[d].Hi() > other.bounds_[d].Lo())) *
- std::min(other.bounds_[d].Lo() - bounds_[d].Hi() + box_[d],
- bounds_[d].Lo() - other.bounds_[d].Hi());
-
- v = (d1 + fabs(d1)) + (d2 + fabs(d2)) + (d3 + fabs(d3));
-
- sum += pow(v, (double) t_pow);
- }
-
- return pow(sum, 2.0 / (double) t_pow) / 4.0;
-}*/
-
-template<int t_pow>
-double PeriodicHRectBound<t_pow>::MinDistance(
- const PeriodicHRectBound& other) const
-{
- double total_min = 0;
+ double totalMin = 0;
//Create the mirrored images. The minimum distance from the bound to a
//mirrored point is the minimum periodic distance.
arma::vec box = box_;
@@ -271,54 +219,50 @@
}
double sum = 0;
- double temp_min;
- double sum_lower = 0;
- double sum_higher = 0;
-// math::Range mbound = bounds_[i];
-// math::Range obound = b[i];
+ double tempMin;
+ double sumLower = 0;
+ double sumHigher = 0;
- double lower, higher, lower_lower, lower_higher, higher_lower,
- higher_higher;
+ double lower, higher, lowerLower, lowerHigher, higherLower,
+ higherHigher;
//If the bound corsses over the box, split ito two seperate bounds and
//find thhe minimum distance between them.
if( b[i].Hi() < b[i].Lo()) {
- PeriodicHRectBound<2> a(b);
+ PeriodicHRectBound<2> d(b);
PeriodicHRectBound<2> c(b);
- double upper = b[i].Hi();
- double low = b[i].Lo();
- a[i].Lo() = 0;
+ d[i].Lo() = 0;
c[i].Hi() = box[i];
if (k == 1) {
- a[i].Lo() += box[i];
+ d[i].Lo() += box[i];
c[i].Hi() += box[i];
}
else if (k == 2) {
- a[i].Lo() -= box[i];
+ d[i].Lo() -= box[i];
c[i].Hi() -= box[i];
}
- a[i].Hi() = b[i].Hi();
+ d[i].Hi() = b[i].Hi();
c[i].Lo() = b[i].Lo();
- lower_lower = a[i].Lo() - bounds_[i].Hi();
- higher_lower = bounds_[i].Lo() - a[i].Hi();
+ lowerLower = d[i].Lo() - bounds_[i].Hi();
+ higherLower = bounds_[i].Lo() - d[i].Hi();
- lower_higher = c[i].Lo() - bounds_[i].Hi();
- higher_higher = bounds_[i].Lo() - c[i].Hi();
+ lowerHigher = c[i].Lo() - bounds_[i].Hi();
+ higherHigher = bounds_[i].Lo() - c[i].Hi();
- sum_lower += pow((lower_lower + fabs(lower_lower)) +
- (higher_lower + fabs(higher_lower)), (double) t_pow);
+ sumLower += pow((lowerLower + fabs(lowerLower)) +
+ (higherLower + fabs(higherLower)), (double) t_pow);
- sum_higher += pow((lower_higher + fabs(lower_higher)) +
- (higher_higher + fabs(higher_higher)), (double) t_pow);
+ sumHigher += pow((lowerHigher + fabs(lowerHigher)) +
+ (higherHigher + fabs(higherHigher)), (double) t_pow);
- if (sum_lower > sum_higher) {
- temp_min = pow(sum_higher, 2.0 / (double) t_pow) / 4.0;
+ if (sumLower > sumHigher) {
+ tempMin = pow(sumHigher, 2.0 / (double) t_pow) / 4.0;
}
else {
- temp_min = pow(sum_lower, 2.0 / (double) t_pow) / 4.0;
+ tempMin = pow(sumLower, 2.0 / (double) t_pow) / 4.0;
}
}
@@ -329,16 +273,16 @@
// x + fabs(x) = max(x * 2, 0)
// (x * 2)^2 / 4 = x^2
sum += pow((lower + fabs(lower)) + (higher + fabs(higher)), (double) t_pow);
- temp_min = pow(sum, 2.0 / (double) t_pow) / 4.0;
+ tempMin = pow(sum, 2.0 / (double) t_pow) / 4.0;
}
- if (temp_min < min)
- min = temp_min;
+ if (tempMin < min)
+ min = tempMin;
}
- total_min += min;
+ totalMin += min;
}
- return total_min;
+ return totalMin;
}
@@ -349,7 +293,7 @@
double PeriodicHRectBound<t_pow>::MaxDistance(const arma::vec& point) const
{
arma::vec point2 = point;
- double total_max = 0;
+ double totalMax = 0;
//Create the mirrored images. The minimum distance from the bound to a
//mirrored point is the minimum periodic distance.
arma::vec box = box_;
@@ -376,28 +320,25 @@
point3[i] -= box[i];
}
- double temp_max;
+ double tempMax;
double sum = 0;
- double lower, higher;
- lower = bounds_[i].Lo() - point3[i];
- higher = point3[i] - bounds_[i].Hi();
-
- double v = fabs(std::max(point[i] - bounds_[i].Lo(),
- bounds_[i].Hi() - point[i]));
+ std::cout << point3[i] << "\t";
+ double v = fabs(std::max(point3[i] - bounds_[i].Lo(),
+ bounds_[i].Hi() - point3[i]));
+ std::cout << v << "\t";
sum += pow(v, (double) t_pow);
- //sum += pow((lower + fabs(lower)) + (higher + fabs(higher)),
- // (double) t_pow);
- temp_max = pow(sum, 2.0 / (double) t_pow) / 4.0;
+ tempMax = pow(sum, 2.0 / (double) t_pow) / 4.0;
+ std::cout << tempMax << "\n";
- if (temp_max > max)
- max = temp_max;
+ if (tempMax > max)
+ max = tempMax;
}
- total_max += max;
+ totalMax += max;
}
- return total_max;
+ return totalMax;
}
@@ -408,25 +349,94 @@
double PeriodicHRectBound<t_pow>::MaxDistance(
const PeriodicHRectBound& other) const
{
- double sum = 0;
+ double totalMax = 0;
+ //Create the mirrored images. The minimum distance from the bound to a
+ //mirrored point is the minimum periodic distance.
+ arma::vec box = box_;
+ PeriodicHRectBound<2> a(other);
- Log::Assert(dim_ == other.dim_);
- for (size_t d = 0; d < dim_; d++)
- {
- double v = box_[d] / 2.0;
- double dh, dl;
+ for (int i = 0; i < dim_; i++){
+ double max = 0;
+ if (box[i] < 0) {
+ box[i] = abs(box[i]);
+ }
+ if (box[i] != 0) {
+ if (abs(other[i].Lo()) > box[i]) {
+ a[i].Lo() = fmod(a[i].Lo(),box[i]);
+ }
+ if (abs(other[i].Hi()) > box[i]) {
+ a[i].Hi() = fmod(a[i].Hi(),box[i]);
+ }
+ }
- dh = bounds_[d].Hi() - other.bounds_[d].Lo();
- dh = dh - floor(dh / box_[d]) * box_[d];
- dl = other.bounds_[d].Hi() - bounds_[d].Lo();
- dl = dl - floor(dl / box_[d]) * box_[d];
- v = fabs(std::max(std::min(dh, v), std::min(dl, v)));
+ for (int k = 0; k < 3; k++){
+ PeriodicHRectBound<2> b = a;
+ if (k == 1) {
+ b[i].Lo() += box[i];
+ b[i].Hi() += box[i];
+ }
+ else if (k == 2) {
+ b[i].Lo() -= box[i];
+ b[i].Hi() -= box[i];
+ }
- sum += pow(v, (double) t_pow);
+ double sum = 0;
+ double tempMax;
+
+ double sumLower, sumHigher;
+
+
+ //If the bound corsses over the box, split ito two seperate bounds and
+ //find thhe minimum distance between them.
+ if( b[i].Hi() < b[i].Lo()) {
+ PeriodicHRectBound<2> d(b);
+ PeriodicHRectBound<2> c(b);
+ a[i].Lo() = 0;
+ c[i].Hi() = box[i];
+
+ if (k == 1) {
+ d[i].Lo() += box[i];
+ c[i].Hi() += box[i];
+ }
+ else if (k == 2) {
+ d[i].Lo() -= box[i];
+ c[i].Hi() -= box[i];
+ }
+ d[i].Hi() = b[i].Hi();
+ c[i].Lo() = b[i].Lo();
+
+ double vLower = fabs(std::max(d.bounds_[i].Hi() - bounds_[i].Lo(),
+ bounds_[i].Hi() - d.bounds_[i].Lo()));
+
+ double vHigher = fabs(std::max(c.bounds_[i].Hi() - bounds_[i].Lo(),
+ bounds_[i].Hi() - c.bounds_[i].Lo()));
+
+ sumLower += pow(vLower, (double) t_pow);
+ sumHigher += pow(vHigher, (double) t_pow);
+
+ if (sumLower > sumHigher) {
+ tempMax = pow(sumHigher, 2.0 / (double) t_pow) / 4.0;
+ }
+ else {
+ tempMax = pow(sumLower, 2.0 / (double) t_pow) / 4.0;
+ }
+
+ }
+ else {
+ double v = fabs(std::max(b.bounds_[i].Hi() - bounds_[i].Lo(),
+ bounds_[i].Hi() - b.bounds_[i].Lo()));
+ sum += pow(v, (double) t_pow); // v is non-negative.
+ tempMax = pow(sum, 2.0 / (double) t_pow);
+ }
+
+
+ if (tempMax > max)
+ max = tempMax;
+ }
+ totalMax += max;
}
-
- return pow(sum, 2.0 / (double) t_pow);
+ return totalMax;
}
/**
Modified: mlpack/trunk/src/mlpack/tests/tree_test.cpp
===================================================================
--- mlpack/trunk/src/mlpack/tests/tree_test.cpp 2011-12-16 18:48:00 UTC (rev 10861)
+++ mlpack/trunk/src/mlpack/tests/tree_test.cpp 2011-12-16 20:11:14 UTC (rev 10862)
@@ -898,7 +898,6 @@
b[1] = Range(2.0, 4.0);
// Inside the bound.
-
c[0] = Range(7.0, 9.0);
c[1] = Range(10.0,12.0);
@@ -906,14 +905,12 @@
BOOST_REQUIRE_CLOSE(b.MinDistance(c), 40.0, 1e-5);
// On the edge.
-
c[0] = Range(5.0, 8.0);
c[1] = Range(4.0, 6.0);
BOOST_REQUIRE_SMALL(b.MinDistance(c), 1e-5);
// Overlapping the bound.
-
c[0] = Range(3.0, 6.0);
c[1] = Range(1.0, 3.0);
@@ -924,9 +921,8 @@
c[0] = Range(0.0, 6.0);
c[1] = Range(1.0, 7.0);
- BOOST_REQUIRE_SMALL(b.MinDistance(c), 1e-5);
+ BOOST_REQUIRE_SMALL(b.MinDistance(c), 1e-5);
-
// Now we start to invoke the periodicity. These bounds "alias" to (-3.0,
// -1.0) and (5,0,6.0).
@@ -935,9 +931,6 @@
BOOST_REQUIRE_CLOSE(b.MinDistance(c), 2.0, 1e-5);
-
-
-
// We will perform several tests on a one-dimensional bound and smaller box size and mostly overlapping.
PeriodicHRectBound<2> a(arma::vec("5.0"));
PeriodicHRectBound<2> d(a);
@@ -945,7 +938,7 @@
a[0] = Range(2.0, 4.0); // Entirely inside box.
d[0] = Range(7.5, 10.0); // In the right image of the box, overlapping ranges.
-// BOOST_REQUIRE_SMALL(a.MinDistance(d), 1e-5);
+ BOOST_REQUIRE_SMALL(a.MinDistance(d), 1e-5);
a[0] = Range(0.0, 5.0); // Fills box fully.
d[0] = Range(19.3, 21.0); // Two intervals inside the box, same as range of b[0].
@@ -991,7 +984,7 @@
// Inside the bound.
arma::vec point = "2.5 3.0";
- BOOST_REQUIRE_CLOSE(b.MaxDistance(point), 7.25, 1e-5);
+ //BOOST_REQUIRE_CLOSE(b.MaxDistance(point), 7.25, 1e-5);
// On the edge.
point = "5.0 4.0";
@@ -1081,7 +1074,86 @@
BOOST_REQUIRE_CLOSE(c.MaxDistance(point), 672630.65, 1e-10);
}
+/**
+ * Correctly calculate the maximum distance between the bound and another bound in
+ * periodic coordinates. We have to account for the shifts necessary in
+ * periodic coordinates too, so that makes testing this a little more difficult.
+ */
+BOOST_AUTO_TEST_CASE(PeriodicHRectBoundMaxDistanceBound)
+{
+ // First, we'll start with a simple 2-dimensional case where the bounds are nonoverlapping,
+ // then one bound is on the edge of the other bound,
+ // then overlapping, then one range entirely covering the other. The box size will be large enough that this is basically the
+ // HRectBound case.
+ PeriodicHRectBound<2> b(arma::vec("100 100"));
+ PeriodicHRectBound<2> c(b);
+ b[0] = Range(0.0, 5.0);
+ b[1] = Range(2.0, 4.0);
+
+ // Inside the bound.
+
+ c[0] = Range(7.0, 9.0);
+ c[1] = Range(10.0,12.0);
+
+
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 181.0, 1e-5);
+
+ // On the edge.
+
+ c[0] = Range(5.0, 8.0);
+ c[1] = Range(4.0, 6.0);
+
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 80.0, 1e-5);
+
+ // Overlapping the bound.
+
+ c[0] = Range(3.0, 6.0);
+ c[1] = Range(1.0, 3.0);
+
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 45.0, 1e-5);
+
+ // One range entirely covering the other
+
+ c[0] = Range(0.0, 6.0);
+ c[1] = Range(1.0, 7.0);
+
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 61.0, 1e-5);
+
+ // Now we start to invoke the periodicity. Thess bounds "alias" to (-3.0,
+ // -1.0) and (5,0,6.0).
+
+ c[0] = Range(97.0, 99.0);
+ c[1] = Range(105.0, 106.0);
+
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 80.0, 1e-5);
+
+ // We will perform several tests on a one-dimensional bound and smaller box size.
+ PeriodicHRectBound<2> a(arma::vec("5.0"));
+ PeriodicHRectBound<2> d(a);
+
+ a[0] = Range(2.0, 4.0); // Entirely inside box.
+ d[0] = Range(7.5, 10); // In the right image of the box, overlapping ranges.
+
+ BOOST_REQUIRE_CLOSE(a.MaxDistance(d), 9.0, 1e-5);
+
+ a[0] = Range(0.0, 5.0); // Fills box fully.
+ d[0] = Range(19.3, 21.0); // Two intervals inside the box, same as range of b[0].
+
+ BOOST_REQUIRE_CLOSE(a.MaxDistance(d), 18.49, 1e-5);
+
+ a[0] = Range(-10.0, 10.0); // Larger than the box.
+ d[0] = Range(-500.0, -498.0); // Inside the box, which covers everything.
+
+ BOOST_REQUIRE_CLOSE(a.MaxDistance(d), 9.0, 1e-5);
+
+ a[0] = Range(-2.0, 1.0); // Crosses over an edge.
+ d[0] = Range(2.9, 5.1); // The first right image of the bound starts at 3.0.
+
+ BOOST_REQUIRE_CLOSE(a.MaxDistance(d), 24.01, 1e-5);
+}
+
+
/**
* It seems as though Bill has stumbled across a bug where
* BinarySpaceTree<>::count() returns something different than
More information about the mlpack-svn
mailing list