diff options
Diffstat (limited to 'kd-forest.h')
-rw-r--r-- | kd-forest.h | 57 |
1 files changed, 57 insertions, 0 deletions
diff --git a/kd-forest.h b/kd-forest.h new file mode 100644 index 0000000..f10f982 --- /dev/null +++ b/kd-forest.h @@ -0,0 +1,57 @@ +/********************************************************************* + * 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 + int 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; + // State flags + bool added, removed; + + // Corresponding image position for this node + unsigned int x, y; +} kd_node_t; + +void kd_node_init(kd_node_t *node, unsigned int x, unsigned int y); +void kd_node_set_color(kd_node_t *node, uint32_t color); + +// 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(kd_forest_t *kdf, kd_node_t *target); + +#endif // KD_FOREST_H |