gts/kdtree.c

   1 /* GTS - Library for the manipulation of triangulated surfaces
   2  * Copyright (C) 1999 Stéphane Popinet
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 #include <stdlib.h>
  21 #include "gts.h"
  22
  23
  24 static int compare_x (const void * p1, const void * p2) {
  25   GtsPoint
  26     * pp1 = *((gpointer *) p1),
  27     * pp2 = *((gpointer *) p2);
  28   if (pp1->x > pp2->x)
  29     return 1;
  30   return -1;
  31 }
  32
  33 static int compare_y (const void * p1, const void * p2) {
  34   GtsPoint
  35     * pp1 = *((gpointer *) p1),
  36     * pp2 = *((gpointer *) p2);
  37   if (pp1->y > pp2->y)
  38     return 1;
  39   return -1;
  40 }
  41
  42 static int compare_z (const void * p1, const void * p2) {
  43   GtsPoint
  44     * pp1 = *((gpointer *) p1),
  45     * pp2 = *((gpointer *) p2);
  46   if (pp1->z > pp2->z)
  47     return 1;
  48   return -1;
  49 }
  50
  51 /**
  52  * gts_kdtree_new:
  53  * @points: an array of #GtsPoint.
  54  * @compare: always %NULL.
  55  *
  56  * Note that the order of the points in array @points is modified by this
  57  * function.
  58  *
  59  * Returns: a new 3D tree for @points.
  60  */
  61 GNode * gts_kdtree_new (GPtrArray * points,
  62                         int (*compare) (const void *, const void *))
  63 {
  64   guint middle;
  65   GPtrArray array;
  66   GNode * node;
  67   GtsPoint * point;
  68
  69   g_return_val_if_fail (points != NULL, NULL);
  70   g_return_val_if_fail (points->len > 0, NULL);
  71
  72   /* sort the points */
  73   if (compare == compare_x) compare = compare_y;
  74   else if (compare == compare_y) compare = compare_z;
  75   else compare = compare_x;
  76   qsort (points->pdata, points->len, sizeof (gpointer), compare);
  77
  78   middle = (points->len - 1)/2;
  79   point = points->pdata[middle];
  80   node = g_node_new (point);
  81
  82   if (points->len > 1) {
  83     array.len = middle;
  84     if (array.len > 0) {
  85       array.pdata = points->pdata;
  86       g_node_prepend (node, gts_kdtree_new (&array, compare));
  87     }
  88     else
  89       g_node_prepend (node, g_node_new (NULL));
  90
  91     array.len = points->len - middle - 1;
  92     if (array.len > 0) {
  93       array.pdata = &(points->pdata[middle + 1]);
  94       g_node_prepend (node, gts_kdtree_new (&array, compare));
  95     }
  96     else
  97       g_node_prepend (node, g_node_new (NULL));
  98   }
  99
 100   return node;
 101 }
 102
 103 /**
 104  * gts_kdtree_range:
 105  * @tree: a 3D tree.
 106  * @bbox: a #GtsBBox.
 107  * @compare: always %NULL.
 108  *
 109  * Returns: a list of #GtsPoint belonging to @tree which are inside @bbox.
 110  */
 111 GSList * gts_kdtree_range (GNode * tree_3d,
 112                            GtsBBox * bbox,
 113                            int (*compare) (const void *, const void *))
 114 {
 115   GSList * list = NULL;
 116   GtsPoint * p;
 117   gdouble left, right, v;
 118   GNode * node;
 119
 120   g_return_val_if_fail (tree_3d != NULL, NULL);
 121   g_return_val_if_fail (bbox != NULL, NULL);
 122
 123   p = tree_3d->data;
 124   if (p == NULL)
 125     return NULL;
 126
 127   if (gts_bbox_point_is_inside (bbox, p))
 128     list = g_slist_prepend (list, p);
 129
 130   if (compare == compare_x) {
 131     left = bbox->y1; right = bbox->y2; v = p->y;
 132     compare = compare_y;
 133   }
 134   else if (compare == compare_y) {
 135     left = bbox->z1; right = bbox->z2; v = p->z;
 136     compare = compare_z;
 137   }
 138   else {
 139     left = bbox->x1; right = bbox->x2; v = p->x;
 140     compare = compare_x;
 141   }
 142
 143   if ((node = tree_3d->children)) {
 144     if (right >= v)
 145       list = g_slist_concat (list, gts_kdtree_range (node, bbox, compare));
 146     node = node->next;
 147     if (left <= v)
 148       list = g_slist_concat (list, gts_kdtree_range (node, bbox, compare));
 149   }
 150   return list;
 151 }
 152