K-d tree: Difference between revisions
Content added Content deleted
m (Made the code compilable on gcc and g++ versions 4.8, the thisn is a bit ugly though.) |
m (Made the code compilable on gcc and g++ versions 4.8, code looks better now hopefully) |
||
| Line 55: | Line 55: | ||
return d; |
return d; |
||
} |
} |
||
inline void swap(struct kd_node_t *x, struct kd_node_t *y) { |
|||
double tmp[MAX_DIM]; |
|||
memcpy(tmp, x->x, sizeof(tmp)); |
|||
memcpy(x->x, y->x, sizeof(tmp)); |
|||
memcpy(y->x, tmp, sizeof(tmp)); |
|||
} |
|||
} |
|||
| Line 149: | Line 149: | ||
{{2, 3}}, {{5, 4}}, {{9, 6}}, {{4, 7}}, {{8, 1}}, {{7, 2}} |
{{2, 3}}, {{5, 4}}, {{9, 6}}, {{4, 7}}, {{8, 1}}, {{7, 2}} |
||
}; |
}; |
||
struct kd_node_t |
struct kd_node_t testNode = {{9, 2}}; |
||
struct kd_node_t *root, *found, *million; |
struct kd_node_t *root, *found, *million; |
||
double best_dist; |
double best_dist; |
||
| Line 157: | Line 157: | ||
visited = 0; |
visited = 0; |
||
found = 0; |
found = 0; |
||
nearest(root, & |
nearest(root, &testNode, 0, 2, &found, &best_dist); |
||
printf(">> WP tree\nsearching for (%g, %g)\n" |
printf(">> WP tree\nsearching for (%g, %g)\n" |
||
"found (%g, %g) dist %g\nseen %d nodes\n\n", |
"found (%g, %g) dist %g\nseen %d nodes\n\n", |
||
testNode.x[0], testNode.x[1], |
|||
found->x[0], found->x[1], sqrt(best_dist), visited); |
found->x[0], found->x[1], sqrt(best_dist), visited); |
||
| Line 169: | Line 169: | ||
root = make_tree(million, N, 0, 3); |
root = make_tree(million, N, 0, 3); |
||
rand_pt( |
rand_pt(testNode); |
||
visited = 0; |
visited = 0; |
||
found = 0; |
found = 0; |
||
nearest(root, & |
nearest(root, &testNode, 0, 3, &found, &best_dist); |
||
printf(">> Million tree\nsearching for (%g, %g, %g)\n" |
printf(">> Million tree\nsearching for (%g, %g, %g)\n" |
||
"found (%g, %g, %g) dist %g\nseen %d nodes\n", |
"found (%g, %g, %g) dist %g\nseen %d nodes\n", |
||
testNode.x[0], testNode.x[1], testNode.x[2], |
|||
found->x[0], found->x[1], found->x[2], |
found->x[0], found->x[1], found->x[2], |
||
sqrt(best_dist), visited); |
sqrt(best_dist), visited); |
||
| Line 194: | Line 194: | ||
found = 0; |
found = 0; |
||
visited = 0; |
visited = 0; |
||
rand_pt( |
rand_pt(testNode); |
||
nearest(root, & |
nearest(root, &testNode, 0, 3, &found, &best_dist); |
||
sum += visited; |
sum += visited; |
||
} |
} |
||
| Line 206: | Line 206: | ||
return 0; |
return 0; |
||
} |
} |
||
</lang> |
</lang> |
||
{{out}} |
{{out}} |
||