1 #ifndef SLA_CLUSTERING_HPP
2 #define SLA_CLUSTERING_HPP
3
4 #include <vector>
5
6 #include <libslic3r/Point.hpp>
7 #include <libslic3r/SLA/SpatIndex.hpp>
8
9 namespace Slic3r { namespace sla {
10
11 using ClusterEl = std::vector<unsigned>;
12 using ClusteredPoints = std::vector<ClusterEl>;
13
14 // Clustering a set of points by the given distance.
15 ClusteredPoints cluster(const std::vector<unsigned>& indices,
16 std::function<Vec3d(unsigned)> pointfn,
17 double dist,
18 unsigned max_points);
19
20 ClusteredPoints cluster(const Eigen::MatrixXd& points,
21 double dist,
22 unsigned max_points);
23
24 ClusteredPoints cluster(
25 const std::vector<unsigned>& indices,
26 std::function<Vec3d(unsigned)> pointfn,
27 std::function<bool(const PointIndexEl&, const PointIndexEl&)> predicate,
28 unsigned max_points);
29
30 // This function returns the position of the centroid in the input 'clust'
31 // vector of point indices.
32 template<class DistFn, class PointFn>
cluster_centroid(const ClusterEl & clust,PointFn pointfn,DistFn df)33 long cluster_centroid(const ClusterEl &clust, PointFn pointfn, DistFn df)
34 {
35 switch(clust.size()) {
36 case 0: /* empty cluster */ return -1;
37 case 1: /* only one element */ return 0;
38 case 2: /* if two elements, there is no center */ return 0;
39 default: ;
40 }
41
42 // The function works by calculating for each point the average distance
43 // from all the other points in the cluster. We create a selector bitmask of
44 // the same size as the cluster. The bitmask will have two true bits and
45 // false bits for the rest of items and we will loop through all the
46 // permutations of the bitmask (combinations of two points). Get the
47 // distance for the two points and add the distance to the averages.
48 // The point with the smallest average than wins.
49
50 // The complexity should be O(n^2) but we will mostly apply this function
51 // for small clusters only (cca 3 elements)
52
53 std::vector<bool> sel(clust.size(), false); // create full zero bitmask
54 std::fill(sel.end() - 2, sel.end(), true); // insert the two ones
55 std::vector<double> avgs(clust.size(), 0.0); // store the average distances
56
57 do {
58 std::array<size_t, 2> idx;
59 for(size_t i = 0, j = 0; i < clust.size(); i++)
60 if(sel[i]) idx[j++] = i;
61
62 double d = df(pointfn(clust[idx[0]]),
63 pointfn(clust[idx[1]]));
64
65 // add the distance to the sums for both associated points
66 for(auto i : idx) avgs[i] += d;
67
68 // now continue with the next permutation of the bitmask with two 1s
69 } while(std::next_permutation(sel.begin(), sel.end()));
70
71 // Divide by point size in the cluster to get the average (may be redundant)
72 for(auto& a : avgs) a /= clust.size();
73
74 // get the lowest average distance and return the index
75 auto minit = std::min_element(avgs.begin(), avgs.end());
76 return long(minit - avgs.begin());
77 }
78
79
80 }} // namespace Slic3r::sla
81
82 #endif // CLUSTERING_HPP
83