pf_kdtree.h
1/*
2 * Player - One Hell of a Robot Server
3 * Copyright (C) 2003
4 * Andrew Howard
5 * Brian Gerkey
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 *
21 */
22
23
24/**************************************************************************
25 * Desc: KD tree functions
26 * Author: Andrew Howard
27 * Date: 18 Dec 2002
28 * CVS: $Id$
29 *************************************************************************/
30
31#ifndef PF_KDTREE_H
32#define PF_KDTREE_H
33
34#include <playerconfig.h>
35
36#ifdef INCLUDE_RTKGUI
37#include "rtk.h"
38#endif
39
40
41// Info for a node in the tree
42typedef struct pf_kdtree_node
43{
44 // Depth in the tree
45 int leaf, depth;
46
47 // Pivot dimension and value
48 int pivot_dim;
49 double pivot_value;
50
51 // The key for this node
52 int key[3];
53
54 // The value for this node
55 double value;
56
57 // The cluster label (leaf nodes)
58 int cluster;
59
60 // Child nodes
61 struct pf_kdtree_node *children[2];
62
64
65
66// A kd tree
67typedef struct
68{
69 // Cell size
70 double size[3];
71
72 // The root node of the tree
73 pf_kdtree_node_t *root;
74
75 // The number of nodes in the tree
76 int node_count, node_max_count;
77 pf_kdtree_node_t *nodes;
78
79 // The number of leaf nodes in the tree
80 int leaf_count;
81
83
84
85// Create a tree
86extern pf_kdtree_t *pf_kdtree_alloc(int max_size);
87
88// Destroy a tree
89extern void pf_kdtree_free(pf_kdtree_t *self);
90
91// Clear all entries from the tree
92extern void pf_kdtree_clear(pf_kdtree_t *self);
93
94// Insert a pose into the tree
95extern void pf_kdtree_insert(pf_kdtree_t *self, pf_vector_t pose, double value);
96
97// Cluster the leaves in the tree
98extern void pf_kdtree_cluster(pf_kdtree_t *self);
99
100// Determine the probability estimate for the given pose
101extern double pf_kdtree_get_prob(pf_kdtree_t *self, pf_vector_t pose);
102
103// Determine the cluster label for the given pose
104extern int pf_kdtree_get_cluster(pf_kdtree_t *self, pf_vector_t pose);
105
106
107#ifdef INCLUDE_RTKGUI
108
109// Draw the tree
110extern void pf_kdtree_draw(pf_kdtree_t *self, rtk_fig_t *fig);
111
112#endif
113
114#endif
Definition pf_kdtree.h:43
Definition pf_kdtree.h:68
Definition pf_vector.h:42