| 205 | } |
| 206 | |
| 207 | PointIdList farthestPointSampling(PointView& view, point_count_t count) |
| 208 | { |
| 209 | // Construct a KD-tree of the input view. |
| 210 | KD3Index& kdi = view.build3dIndex(); |
| 211 | |
| 212 | // Seed the output view with the first point in the current sorting. |
| 213 | PointId seedId(0); |
| 214 | PointIdList ids(count); |
| 215 | ids[0] = seedId; |
| 216 | |
| 217 | // Compute distances from seedId to all other points. |
| 218 | PointIdList indices(view.size()); |
| 219 | std::vector<double> sqr_dists(view.size()); |
| 220 | kdi.knnSearch(seedId, view.size(), &indices, &sqr_dists); |
| 221 | |
| 222 | // Sort distances by PointId. |
| 223 | std::vector<double> min_dists(view.size()); |
| 224 | for (PointId i = 0; i < view.size(); ++i) |
| 225 | min_dists[indices[i]] = sqr_dists[i]; |
| 226 | |
| 227 | // Proceed until we have m_count points in the output PointView. |
| 228 | for (PointId i = 1; i < count; ++i) |
| 229 | { |
| 230 | // Find the max distance in min_dists, this is the farthest point from |
| 231 | // any point currently in the output PointView. |
| 232 | auto it = std::max_element(min_dists.begin(), min_dists.end()); |
| 233 | |
| 234 | // Record the PointId of the farthest point and add it to the output |
| 235 | // PointView. |
| 236 | PointId idx(it - min_dists.begin()); |
| 237 | ids[i] = idx; |
| 238 | |
| 239 | // Compute distances from idx to all other points. |
| 240 | kdi.knnSearch(idx, view.size(), &indices, &sqr_dists); |
| 241 | |
| 242 | // Update distances. |
| 243 | for (PointId j = 0; j < view.size(); ++j) |
| 244 | { |
| 245 | if (sqr_dists[j] < min_dists[indices[j]]) |
| 246 | min_dists[indices[j]] = sqr_dists[j]; |
| 247 | } |
| 248 | } |
| 249 | |
| 250 | return ids; |
| 251 | } |
| 252 | |
| 253 | } // namespace Segmentation |
| 254 | } // namespace pdal |