Revision history [back]

Let's look into pf_sample_set_t type.

typedef struct _pf_sample_set_t {
  // The samples
  int sample_count;
  pf_sample_t *samples;

  // A kdtree encoding the histogram
  pf_kdtree_t *kdtree;

  // Clusters
  int cluster_count, cluster_max_count;
  pf_cluster_t *clusters;

  // Filter statistics
  pf_vector_t mean;
  pf_matrix_t cov;
  int converged; 
} pf_sample_set_t;

Sample particles are stored as an array hold by the pointer, samples, instead of kdtree. The kdtree is for constructing weight histogram of particles. The purposes of this histogram are to provide the number of non-empty bins for KLD-sampling and to calculate mean and covariance values from each cluster. This clustering algorithm for the kdtree histogram seems like a type of density-based clustering algorithms. Nodes connected to each other are labeled as a same cluster where connectivity is determined based on neighbor nodes. In pf_kdtree.c of amcl package, the neighbor node, nnode, of a node is

nkey[0] = node->key[0] + (i / 9) - 1;
nkey[1] = node->key[1] + ((i % 9) / 3) - 1;
nkey[2] = node->key[2] + ((i % 9) % 3) - 1;
nnode = pf_kdtree_find_node(self, self->root, nkey);

where key is the spatial information of a node.