lib/kdtree.h

   1 /* kdtree.h
   2    Implementation of 2d kd trees.
   3
   4    Part of the swftools package.
   5
   6    Copyright (c) 2010 Matthias Kramm <kramm@quiss.org>
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  21
  22 #ifndef __kdtree_h__
  23 #define  __kdtree_h__
  24
  25 #ifdef __cplusplus
  26 extern "C" {
  27 #endif
  28
  29 #include <stdint.h>
  30
  31 /*
  32           3
  33           A
  34           |
  35           |
  36    2 <---- ----> 0
  37           |
  38           |
  39           V
  40           1
  41 */
  42
  43 typedef enum {KD_RIGHT=0, KD_DOWN=1, KD_LEFT=2, KD_UP=3} kdtype_t;
  44
  45 typedef struct _kdbbox {
  46     int32_t xmin, ymin, xmax, ymax;
  47 } kdbbox_t;
  48
  49 struct _kdbranch;
  50 struct _kdarea;
  51 typedef struct _kdbranch kdbranch_t;
  52 typedef struct _kdarea kdarea_t;
  53
  54 struct _kdbranch {
  55     kdtype_t type;
  56     kdarea_t*side[2];
  57     int32_t xy;
  58 };
  59
  60 struct _kdarea {
  61     kdarea_t*neighbors[4];
  62     kdbbox_t bbox;
  63     kdbranch_t*split;
  64     void*data;
  65 };
  66
  67 typedef struct _kdtree {
  68     kdarea_t*root;
  69 } kdtree_t;
  70
  71 /* usually a subset of the tree, e.g. caused by
  72    intersecting the tree with a halfplane */
  73 typedef struct _kdarea_list {
  74     struct _kdarea_list*next;
  75     struct _kdarea_list*prev;
  76     kdarea_t*area;
  77 } kdarea_list_t;
  78
  79 kdtree_t* kdtree_new();
  80 void kdarea_destroy(kdarea_t*area);
  81 void kdbranch_destroy(kdbranch_t*b);
  82 void kdtree_destroy(kdtree_t*tree);
  83 kdarea_t* kdtree_find(kdtree_t*tree, int x, int y);
  84 void kdtree_add_box(kdtree_t*tree, int32_t x1, int32_t y1, int32_t x2, int32_t y2, void*data);
  85 void kdtree_print(kdtree_t*tree);
  86
  87 kdarea_t*kdarea_neighbor(kdarea_t*area, int dir, int xy);
  88
  89 #define kdarea_left_neighbor(area, y) (kdarea_neighbor((area), KD_LEFT, (y)))
  90 #define kdarea_right_neighbor(area, y) (kdarea_neighbor((area), KD_RIGHT, (y)))
  91 #define kdarea_top_neighbor(area, x) (kdarea_neighbor((area), KD_TOP, (x)))
  92 #define kdarea_bottom_neighbor(area, x) (kdarea_neighbor((area), KD_BOTTOM, (x)))
  93
  94 #ifdef __cplusplus
  95 }
  96 #endif
  97
  98 #endif