Developer Documentation

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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