1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
// This file is part of libigl, a simple c++ geometry processing library.
//
// Copyright (C) 2014 Alec Jacobson <alecjacobson@gmail.com>
//
// This Source Code Form is subject to the terms of the Mozilla Public License
// v. 2.0. If a copy of the MPL was not distributed with this file, You can
// obtain one at http://mozilla.org/MPL/2.0/.
#include "partition.h"
#include "mat_min.h"
IGL_INLINE void igl::partition(
const Eigen::MatrixXd & W,
const int k,
Eigen::Matrix<int,Eigen::Dynamic,1> & G,
Eigen::Matrix<int,Eigen::Dynamic,1> & S,
Eigen::Matrix<double,Eigen::Dynamic,1> & D)
{
// number of mesh vertices
int n = W.rows();
// Resize output
G.resize(n);
S.resize(k);
// "Randomly" choose first seed
// Pick a vertex farthest from 0
int s;
(W.array().square().matrix()).rowwise().sum().maxCoeff(&s);
S(0) = s;
// Initialize distance to closest seed
D = ((W.rowwise() - W.row(s)).array().square()).matrix().rowwise().sum();
G.setZero();
// greedily choose the remaining k-1 seeds
for(int i = 1;i<k;i++)
{
// Find maximum in D
D.maxCoeff(&s);
S(i) = s;
// distance to this seed
Eigen::Matrix<double,Eigen::Dynamic,1> Ds =
((W.rowwise() - W.row(s)).array().square()).matrix().rowwise().sum();
// Concatenation of D and Ds: DDs = [D Ds];
Eigen::Matrix<double,Eigen::Dynamic,Eigen::Dynamic> DDs;
// Make space for two columns
DDs.resize(D.rows(),2);
DDs.col(0) = D;
DDs.col(1) = Ds;
// Update D
// get minimum of old D and distance to this seed, C == 1 if new distance
// was smaller
Eigen::Matrix<int,Eigen::Dynamic,1> C;
igl::mat_min(DDs,2,D,C);
G = (C.array() ==0).select(G,i);
}
}
|
