From 8e6ced70cc48dc842b23eaed5c60fb72ae266661 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Tue, 11 Mar 2014 12:42:06 -0400 Subject: Initial commit. --- kd-forest.h | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) create mode 100644 kd-forest.h (limited to 'kd-forest.h') 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 * + * * + * 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 +#include +#include + +#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 -- cgit v1.2.3