Developer Documentation

DBSCANT_impl.hh
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 #include <queue>
43
44 namespace ACG {
45 namespace Algorithm {
46
47 namespace _DBSCAN_PRIVATE {
48
49 template<typename VALUE_TYPE>
50 class constant_1 {
51 public:
52 inline double operator()(VALUE_TYPE it) const {
53 return 1.0;
54 }
55 };
56
57 template<typename INPUT_ITERATOR, typename WEIGHT_FUNC>
58 inline double neighborhoodWeight(INPUT_ITERATOR first, const INPUT_ITERATOR last, WEIGHT_FUNC &weight_func) {
59 double result = 0;
60 for (; first != last; ++first)
61 result += weight_func(**first);
62 return result;
63 }
64
65 /*
66 * Private functions.
67 */
68 template<typename INPUT_ITERATOR, typename DISTANCE_FUNC, typename OUTPUT_ITERATOR>
69 inline
70 void region_query(INPUT_ITERATOR first, const INPUT_ITERATOR last, const INPUT_ITERATOR center,
71 DISTANCE_FUNC &distance_func, OUTPUT_ITERATOR result, const double epsilon) {
72
73 for (; first != last; ++first) {
74 if (center == first) continue;
75 if (distance_func(*center, *first) <= epsilon) {
76 *result++ = first;
77 }
78 }
79 }
80
81
82 template<typename INPUT_ITERATOR, typename DISTANCE_FUNC, typename WEIGHT_FUNC>
83 inline
84 void expand_cluster(INPUT_ITERATOR first, const INPUT_ITERATOR last, const INPUT_ITERATOR center,
85 DISTANCE_FUNC &distance_func, const double epsilon, const double n_min,
86 std::vector<int> &id_cache, const int current_cluster_id, WEIGHT_FUNC &weight_func) {
87
88
89 std::queue<INPUT_ITERATOR> bfq;
90 bfq.push(center);
91
92 id_cache[std::distance(first, center)] = current_cluster_id;
93
94 std::vector<INPUT_ITERATOR> neighborhood; neighborhood.reserve(std::distance(first, last));
95
96 while (!bfq.empty()) {
97
98 INPUT_ITERATOR current_element = bfq.front();
99 bfq.pop();
100
101 /*
102 * Precondition: id_cache[current_idx] > 0
103 */
104
105 neighborhood.clear();
106 region_query(first, last, current_element, distance_func, std::back_inserter(neighborhood), epsilon);
107
108 /*
109 * If the current element is not inside a dense area,
110 * we don't use it as a seed to expand the cluster.
111 */
112 if (neighborhoodWeight(neighborhood.begin(), neighborhood.end(), weight_func) < n_min)
113 continue;
114
115 /*
116 * Push yet unvisited elements onto the queue.
117 */
118 for (typename std::vector<INPUT_ITERATOR>::iterator it = neighborhood.begin(), it_end = neighborhood.end();
119 it != it_end; ++it) {
120 const size_t neighbor_idx = std::distance(first, *it);
121 /*
122 * Is the element classified as non-noise, yet?
123 */
124 if (id_cache[neighbor_idx] <= 0) {
125 /*
126 * Classify it and use it as a seed.
127 */
128 id_cache[neighbor_idx] = current_cluster_id;
129 bfq.push(*it);
130 }
131 }
132 }
133 }
134
135 } /* namespace _DBSCAN_PRIVATE */
136
137 } /* namespace Algorithm */
138 } /* namespace ACG */
ACG
Namespace providing different geometric functions concerning angles.
Definition: BaseObjectData.hh:68
ACG::Algorithm::_DBSCAN_PRIVATE::constant_1
Definition: DBSCANT_impl.hh:50