blob: 3651bfe031ae20c683219794953b3f4909a6d8e1 (
plain)
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
|
/*********************************************************************
* kd-forest *
* Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com> *
* *
* This program is free software. It comes without any warranty, to *
* the extent permitted by applicable law. You can redistribute it *
* and/or modify it under the terms of the Do What The Fuck You Want *
* To Public License, Version 2, as published by Sam Hocevar. See *
* the COPYING file or http://www.wtfpl.net/ for more details. *
*********************************************************************/
#ifndef KD_FOREST_H
#define KD_FOREST_H
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#define KD_DIMEN 3
// Single node in a k-d tree
typedef struct kd_node_t {
// Node coordinates
double coords[KD_DIMEN];
// Sub-trees
struct kd_node_t *left, *right;
// Used to keep track of which sub-tree a node is in during construction
bool is_left;
// Weak delete support
bool removed;
// Corresponding image position for this node
unsigned int x, y;
} kd_node_t;
kd_node_t *new_kd_node(double coords[KD_DIMEN], unsigned int x, unsigned int y);
// A forest of k-d trees
typedef struct {
// Array of k-d tree roots
kd_node_t **roots;
// Size and capacity of the roots array
unsigned int roots_size, roots_capacity;
// The actual size of this tree
size_t size;
// The size estimate for this tree, counting removed nodes
size_t size_est;
} kd_forest_t;
void kdf_init(kd_forest_t *kdf);
void kdf_destroy(kd_forest_t *kdf);
void kdf_insert(kd_forest_t *kdf, kd_node_t *node);
void kdf_remove(kd_forest_t *kdf, kd_node_t *node);
kd_node_t *kdf_find_nearest(const kd_forest_t *kdf, const double target[KD_DIMEN]);
#endif // KD_FOREST_H
|
