diff options
Diffstat (limited to 'kd-forest.h')
-rw-r--r-- | kd-forest.h | 56 |
1 files changed, 0 insertions, 56 deletions
diff --git a/kd-forest.h b/kd-forest.h deleted file mode 100644 index 3651bfe..0000000 --- a/kd-forest.h +++ /dev/null @@ -1,56 +0,0 @@ -/********************************************************************* - * 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 |