Anonymous user
K-d tree: Difference between revisions
m
Made the code compilable on gcc and g++ versions 4.8, the thisn is a bit ugly though.
m ({{out}}) |
m (Made the code compilable on gcc and g++ versions 4.8, the thisn is a bit ugly though.) |
||
Line 31:
=={{header|C}}==
Using a Quickselectesque median algorithm. Compared to unbalanced trees (random insertion), it takes slightly longer (maybe half a second or so) to construct a million-node tree, though average look up visits about 1/3 fewer nodes.
<lang c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 39 ⟶ 41:
#define MAX_DIM 3
struct kd_node_t{
};
inline double
dist(struct kd_node_t *a, struct kd_node_t *b, int dim)
{
}
}▼
}
inline void swap(struct kd_node_t *x, struct kd_node_t *y) {
double tmp[MAX_DIM];
}
/* see quickselect method */
struct kd_node_t*
find_median(struct kd_node_t *start, struct kd_node_t *end, int idx)
{
▲ memcpy(tmp, x->x, sizeof(tmp));
▲ memcpy(x->x, y->x, sizeof(tmp));
▲ memcpy(y->x, tmp, sizeof(tmp));
▲ while (1) {
▲ pivot = md->x[idx];
store++;
}
}
▲ for (store = p = start; p < end; p++) {
▲ if (p->x[idx] < pivot) {
▲ if (p != store)
▲ swap(p, store);
▲ swap(store, end - 1);
▲ /* median has duplicate values */
▲ if (store->x[idx] == md->x[idx])
}
▲ return md;
▲ if (store > md) end = store;
▲ else start = store;
}
struct kd_node_t*
make_tree(struct kd_node_t *t, int len, int i, int dim)
{
}
}
Line 112 ⟶ 114:
void nearest(struct kd_node_t *root, struct kd_node_t *nd, int i, int dim,
{
}
}
#define N 1000000
#define rand1()
#define rand_pt(v) { v.x[0] = rand1(); v.x[1] = rand1(); v.x[2] = rand1(); }
int main(void)
{
}
{{out}}
<pre>>> WP tree
|