| 95 | } |
| 96 | |
| 97 | void DBSCANFilter::filter(PointView& view) |
| 98 | { |
| 99 | // Construct KDFlexIndex for radius search. |
| 100 | KDFlexIndex kdfi(view, m_dimIdList); |
| 101 | kdfi.build(); |
| 102 | |
| 103 | // First pass through point cloud precomputes neighbor indices and |
| 104 | // initializes ClusterID to -2. |
| 105 | std::vector<PointIdList> neighbors(view.size()); |
| 106 | for (PointId idx = 0; idx < view.size(); ++idx) |
| 107 | { |
| 108 | neighbors[idx] = kdfi.radius(idx, m_eps); |
| 109 | view.setField(Id::ClusterID, idx, -2); |
| 110 | } |
| 111 | |
| 112 | // Second pass through point cloud performs DBSCAN clustering. |
| 113 | int64_t cluster_label = 0; |
| 114 | for (PointId idx = 0; idx < view.size(); ++idx) |
| 115 | { |
| 116 | // Point has already been labeled, so move on to next. |
| 117 | if (view.getFieldAs<int64_t>(Id::ClusterID, idx) != -2) |
| 118 | continue; |
| 119 | |
| 120 | // Density of the neighborhood does not meet minimum number of points |
| 121 | // constraint, label as noise. |
| 122 | if (neighbors[idx].size() < m_minPoints) |
| 123 | { |
| 124 | view.setField(Id::ClusterID, idx, -1); |
| 125 | continue; |
| 126 | } |
| 127 | |
| 128 | // Initialize some bookkeeping to track which neighbors have been |
| 129 | // considered for addition to the current cluster. |
| 130 | std::unordered_set<PointId> neighbors_next(neighbors[idx].begin(), |
| 131 | neighbors[idx].end()); |
| 132 | std::unordered_set<PointId> neighbors_visited; |
| 133 | neighbors_visited.insert(idx); |
| 134 | |
| 135 | // Unlabeled point encountered; assign cluster label. |
| 136 | view.setField(Id::ClusterID, idx, cluster_label); |
| 137 | |
| 138 | // Consider all neighbors. |
| 139 | while (!neighbors_next.empty()) |
| 140 | { |
| 141 | // Select first neighbor and move it to the visited set. |
| 142 | PointId p = *neighbors_next.begin(); |
| 143 | neighbors_next.erase(neighbors_next.begin()); |
| 144 | neighbors_visited.insert(p); |
| 145 | |
| 146 | // Reassign cluster label to neighbor previously marked as noise. |
| 147 | if (view.getFieldAs<int64_t>(Id::ClusterID, p) == -1) |
| 148 | view.setField(Id::ClusterID, p, cluster_label); |
| 149 | |
| 150 | // Neighbor has already been labeled, so move on to next. |
| 151 | if (view.getFieldAs<int64_t>(Id::ClusterID, p) != -2) |
| 152 | continue; |
| 153 | |
| 154 | // Assign cluster label to neighbor. |