Developer Documentation
Loading...
Searching...
No Matches
DBSCAN_test.cc
1/*===========================================================================*\
2 * *
3 * OpenFlipper *
4 * Copyright (c) 2001-2015, RWTH-Aachen University *
5 * Department of Computer Graphics and Multimedia *
6 * All rights reserved. *
7 * www.openflipper.org *
8 * *
9 *---------------------------------------------------------------------------*
10 * This file is part of OpenFlipper. *
11 *---------------------------------------------------------------------------*
12 * *
13 * Redistribution and use in source and binary forms, with or without *
14 * modification, are permitted provided that the following conditions *
15 * are met: *
16 * *
17 * 1. Redistributions of source code must retain the above copyright notice, *
18 * this list of conditions and the following disclaimer. *
19 * *
20 * 2. Redistributions in binary form must reproduce the above copyright *
21 * notice, this list of conditions and the following disclaimer in the *
22 * documentation and/or other materials provided with the distribution. *
23 * *
24 * 3. Neither the name of the copyright holder nor the names of its *
25 * contributors may be used to endorse or promote products derived from *
26 * this software without specific prior written permission. *
27 * *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39 * *
40\*===========================================================================*/
41
42
43#include <gtest/gtest.h>
44
45#include <vector>
46#include <map>
47
48#include <cmath>
49#include <cstring>
50
51#include "../../Algorithm/DBSCANT.hh"
52
53namespace {
54const char * const test1_map[] = {
55 " ",
56 " . b b . ",
57 " ",
58 " a b ",
59 " ",
60 " ",
61 " a b b b ",
62 " aa b b b ",
63 " aaaa . . b b b bbb b ",
64 " aa b b ",
65 " a a a a ",
66 " a a a a a a ",
67 " a a a ",
68 " ",
69 " aaa ",
70 " ",
71 " ",
72 " ",
73 " . a a a . cc ",
74 " cc ",
75 " .. ",
76 " . ",
77 " ",
78 0 };
79
80const char * const test2_map[] = { "aaaaAAaaaa", 0 };
81
82class Point {
83 public:
84 Point(double x, double y, char classifier, double weight = 1.0) : x(x), y(y), weight(weight), classifier(classifier) {}
85
86 double length() const {
87 return std::sqrt(x*x + y*y);
88 }
89
90 Point operator- (const Point &rhs) const {
91 return Point(x-rhs.x, y-rhs.y, classifier, weight);
92 }
93
94 double dist(const Point &rhs) const {
95 return operator-(rhs).length();
96 }
97
98 class DistanceFunc {
99 public:
100 double operator() (const Point &a, const Point &b) const {
101 return a.dist(b);
102 }
103 };
104
105 class WeightFunc {
106 public:
107 double operator() (const Point &a) const {
108 return a.weight;
109 }
110 };
111
112 double x, y, weight;
113 char classifier;
114};
115
116template<class OSTREAM>
117OSTREAM &operator<< (OSTREAM &stream, Point* point) {
118 return stream << "(" << point->x << ", " << point->y << ", " << point->weight << ", " << "'" << point->classifier << "'" << ")";
119}
120
121template<class OUTPUT_ITERATOR>
122void parse_points(const char * const * input, OUTPUT_ITERATOR points_out, double uc_weight = 1.0, double lc_weight = 1.0) {
123 int y = 0;
124 for (; *input != 0; ++input, ++y) {
125 int x = 0;
126 for (const char *it = *input; *it != 0; ++it, ++x) {
127 if (!isspace(*it)) {
128 const double weight = islower(*it) ? lc_weight : uc_weight;
129 *points_out++ = Point(x, y, *it, weight);
130 }
131 }
132 }
133}
134
135testing::AssertionResult checkClusterConsistency(const std::vector<Point> &points, const std::vector<int> &cluster_map) {
136 std::map<int, char> cluster_2_classifier;
137
138 std::vector<int>::const_iterator cluster_it = cluster_map.begin();
139 for (std::vector<Point>::const_iterator point_it = points.begin(), point_it_end = points.end();
140 point_it != point_it_end; ++point_it, ++cluster_it) {
141
142 std::map<int, char>::const_iterator map_it = cluster_2_classifier.find(*cluster_it);
143 if (map_it == cluster_2_classifier.end()) {
144 cluster_2_classifier[*cluster_it] = point_it->classifier;
145
146 if (point_it->classifier == '.' && *cluster_it != 0) {
147 return testing::AssertionFailure() << "Noise point " << &(*point_it) << " was mapped to non-noise cluster " << *cluster_it << ".";
148 }
149
150 if (*cluster_it == 0 && point_it->classifier != '.') {
151 return testing::AssertionFailure() << "Non-noise point " << &(*point_it) << " was mapped to noise cluster (0).";
152 }
153 } else {
154 if (map_it->second != point_it->classifier) {
155 return testing::AssertionFailure() << "Point " << &(*point_it) << " was mapped to cluster '" << map_it->second << "'.";
156 }
157 }
158 }
159
160 return testing::AssertionSuccess() << "All points were mapped to clusters as expected.";
161}
162
163template<class II_1, class II_2>
164testing::AssertionResult checkCollectionEquivalence(II_1 first1, II_1 last1, II_2 first2, II_2 last2) {
165 for (int index = 0; first1 != last1 && first2 != last2; ++first1, ++first2, ++index) {
166 if (*first1 != *first2)
167 return testing::AssertionFailure() << "Mismatch in element " << index << ".";
168 }
169
170 if (first1 != last1)
171 return testing::AssertionFailure() << "Second collection longer than first one.";
172
173 if (first2 != last2)
174 return testing::AssertionFailure() << "First collection longer than second one.";
175
176 return testing::AssertionSuccess() << "Collections are equivalent.";
177}
178
179TEST(DBSCAN, manual_test_1) {
180 std::vector<Point> points;
181 parse_points(test1_map, std::back_inserter(points));
182 std::vector<int> clusters;
183
184 EXPECT_EQ(3,
185 ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
186 std::back_inserter(clusters), 4.0001, 3.0));
187 EXPECT_TRUE(checkClusterConsistency(points, clusters));
188
189 // Call both versions of DBSCAN.
190 EXPECT_EQ(3,
191 ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
192 std::back_inserter(clusters), 4.0001, 3.0,
193 ACG::Algorithm::_DBSCAN_PRIVATE::constant_1<std::vector<Point>::iterator::value_type>()));
194 EXPECT_TRUE(checkClusterConsistency(points, clusters));
195}
196
197TEST(DBSCAN, manual_test_2_a) {
198 std::vector<Point> points;
199 parse_points(test2_map, std::back_inserter(points), 1.0, 1.0);
200 std::vector<int> clusters;
201 EXPECT_EQ(1,
202 ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
203 std::back_inserter(clusters), 1.01, 1.2, Point::WeightFunc()));
204
205 const int expected[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
206 EXPECT_TRUE(checkCollectionEquivalence(clusters.begin(), clusters.end(), expected, expected + 10));
207}
208
209TEST(DBSCAN, manual_test_2_b) {
210 std::vector<Point> points;
211 parse_points(test2_map, std::back_inserter(points), 1.0, .5);
212 std::vector<int> clusters;
213 EXPECT_EQ(1,
214 ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
215 std::back_inserter(clusters), 1.01, 1.2, Point::WeightFunc()));
216
217 const int expected[] = { 0, 0, 1, 1, 1, 1, 1, 1, 0, 0 };
218 EXPECT_TRUE(checkCollectionEquivalence(clusters.begin(), clusters.end(), expected, expected + 10));
219}
220
221}
ACG::Algorithm::_DBSCAN_PRIVATE::constant_1
Definition DBSCANT_impl.hh:50