eg_octree.ex.c

Go to the documentation of this file.
00001 /* EGlib "Efficient General Library" provides some basic structures and
00002  * algorithms commons in many optimization algorithms.
00003  *
00004  * Copyright (C) 2005 Daniel Espinoza
00005  * 
00006  * This library is free software; you can redistribute it and/or modify it
00007  * under the terms of the GNU Lesser General Public License as published by the
00008  * Free Software Foundation; either version 2.1 of the License, or (at your
00009  * option) any later version.
00010  *
00011  * This library is distributed in the hope that it will be useful, but 
00012  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
00013  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
00014  * License for more details.
00015  *
00016  * You should have received a copy of the GNU Lesser General Public License
00017  * along with this library; if not, write to the Free Software Foundation,
00018  * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
00019  * */
00020 /** @file 
00021  * @ingroup EGeOctree */
00022 /** @addtogroup EGeOctree */
00023 /** @{ */
00024 /* ========================================================================= */
00025 /** @brief This program reads from a file with at least three columns the
00026  * following information:
00027  * max_x max_y max_z n (everything else discarded in the line in every line)
00028  * x_0 y_0 z_0
00029  * x_1 y_1 z_1
00030  *   ...  
00031  * x_n y_n z_n
00032  *
00033  * store the structure in an octree, and show different forms of traversing it.
00034  * */
00035 /* ========================================================================= */
00036 #include "EGlib.h"
00037 
00038 /* ========================================================================= */
00039 /** @brief display the usage message for this program */
00040 void oct_usage (char *program)
00041 {
00042   fprintf (stdout, "Usage: %s [options]\n", program);
00043   fprintf (stdout, "Options:\n");
00044   fprintf (stdout, "     -f n   file name.\n");
00045 
00046 }
00047 
00048 /* ========================================================================= */
00049 /** @brief parse the input argumenbts for the program */
00050 int oct_parseargs (int argc,
00051                    char **argv,
00052                    char **file_name)
00053 {
00054   int c;
00055   while ((c = getopt (argc, argv, "f:")) != EOF)
00056   {
00057     switch (c)
00058     {
00059     case 'f':
00060       *file_name = optarg;
00061       break;
00062     default:
00063       oct_usage (argv[0]);
00064       return 1;
00065     }
00066   }
00067   /* reporting the options */
00068   if (!*file_name)
00069   {
00070     oct_usage (argv[0]);
00071     return 1;
00072   }
00073   fprintf (stdout, "Parsed Options:\n");
00074   fprintf (stdout, "input         : %s\n", *file_name);
00075   return 0;
00076 }
00077 
00078 /* ========================================================================= */
00079 /** @brief main function */
00080 int main (int argc,
00081           char **argv)
00082 {
00083   unsigned max_x, max_y, max_z, n, i;
00084   int rval = 0;
00085   char *file_name = 0,
00086     str1[1024], *argv1[128];
00087   int argc1;
00088   EGioFile_t *file = 0;
00089   EGrandState_t seed;
00090   EGeOctdata_t*alldata = 0, *cur, *next;
00091   EGeOctree_t oct;
00092 
00093   /* Parse command line input to get 'file name' and 'd'. */
00094   EGlib_info();
00095   EGlib_version();
00096   rval = oct_parseargs (argc, argv, &file_name);
00097   CHECKRVALG (rval, CLEANUP);
00098   /* set signal and limits */
00099   EGsigSet(rval,CLEANUP);
00100   EGsetLimits(3600.0,4294967295UL);
00101 
00102   /* Read the objects to sort from the file */
00103   file = EGioOpen (file_name, "r");
00104   TEST (!file, "unable to open file %s", file_name);
00105   EGioGets(str1,1024,file);
00106   EGioNParse(str1,128," ","%#",&argc1,argv1);
00107   TESTG((rval=(argc1<4)),CLEANUP,"Expected at least four tokens, found %d",
00108         argc1);
00109   max_x = (unsigned)atoi(argv1[0]);
00110   max_y = (unsigned)atoi(argv1[1]);
00111   max_z = (unsigned)atoi(argv1[2]);
00112   n = (unsigned)atoi(argv1[3]);
00113   alldata = EGsMalloc(EGeOctdata_t,n);
00114   rval = EGeOctinit(&oct, (uint16_t)max_x, (uint16_t)max_y, (uint16_t)max_z, 0, EGeOctalloc, EGeOctfree);
00115   CHECKRVALG(rval,CLEANUP);
00116   /* we add all elements */
00117   for( i = 0 ; i < n ; i++)
00118   {
00119     do{
00120       EGioGets(str1,1024,file);
00121       EGioNParse(str1,128," ","%#",&argc1,argv1);
00122     } while(!EGioEof(file) && !argc1);
00123     TESTG((rval=(argc1<3)),CLEANUP,"Expected at least three tokens, found %d",
00124             argc1);
00125     alldata[i].x = (uint16_t)atoi(argv1[0]);
00126     alldata[i].y = (uint16_t)atoi(argv1[1]);
00127     alldata[i].z = (uint16_t)atoi(argv1[2]);
00128     rval = EGeOctaddleaf(&oct,alldata+i);
00129     CHECKRVALG(rval,CLEANUP);
00130   }
00131   /* now we iterate through all nodes at depth 3 */
00132   cur = (EGeOctdata_t*)oct.root;
00133   while(cur)
00134   {
00135     if(cur->depth == 3U)
00136     {
00137       fprintf(stdout,"Branch %p {%5u,%5u,%5u,%2u,%1u,%1u,%p}\n", cur,
00138               cur->x, cur->y, cur->z, cur->depth, cur->key, cur->nson,
00139               cur->up);
00140       next = EGeOctbrother(cur);
00141       if(!next) next = EGeOctcousin(cur);
00142     }
00143     else
00144     {
00145       next = EGeOctson(cur);
00146       if(!next) next = EGeOctbrother(cur);
00147       if(!next) next = EGeOctcousin(cur);
00148     }
00149     cur = next;
00150   }
00151   /* now we randomly find points in the grid */
00152   EGrandInit(&seed);
00153   for( i = 0 ; i < 50 ; i++)
00154   {
00155     max_x = (unsigned)EGrandInt(&seed,0,oct.max_x);
00156     max_y = (unsigned)EGrandInt(&seed,0,oct.max_y);
00157     max_z = (unsigned)EGrandInt(&seed,0,oct.max_z);
00158     cur = EGeOctfind(&oct, 0, max_x, max_y, max_z);
00159     if(cur)
00160       fprintf(stdout,"Found %p {%5u,%5u,%5u,%2u,%1u,%1u,%p}\n", cur,
00161               cur->x, cur->y, cur->z, cur->depth, cur->key, cur->nson,
00162               cur->up);
00163     else
00164       fprintf(stdout,"Not Found {%5u,%5u,%5u}\n",max_x, max_y, max_z);
00165   }
00166   /* find aproximate branches at level 2 */
00167   for( i = 0 ; i < 50 ; i++)
00168   {
00169     max_x = (unsigned)EGrandInt(&seed,0,oct.max_x);
00170     max_y = (unsigned)EGrandInt(&seed,0,oct.max_y);
00171     max_z = (unsigned)EGrandInt(&seed,0,oct.max_z);
00172     cur = EGeOctfind(&oct, 2, max_x, max_y, max_z);
00173     if(cur)
00174       fprintf(stdout,"Aprox Found %p {%5u,%5u,%5u,%2u,%1u,%1u,%p}\n", cur,
00175               cur->x, cur->y, cur->z, cur->depth, cur->key, cur->nson,
00176               cur->up);
00177     else
00178       fprintf(stdout,"Aprox Not Found {%5u,%5u,%5u}\n",max_x, max_y, max_z);
00179   }
00180 
00181   /* now we select a point and delete it */
00182   for( i =0 ; i < 100 ; i++)
00183   {
00184     argc1 = EGrandInt(&seed,0,((int)n)-1);
00185     fprintf(stdout,"Delete leaf %d\n",argc1);
00186     rval = EGeOctdelleaf(&oct,alldata+argc1);
00187     CHECKRVALG(rval,CLEANUP);
00188   }
00189   /* Liberating allocated memory */
00190 CLEANUP:
00191   if(file) EGioClose(file);
00192   EGeOctclear(&oct);
00193   if(alldata) EGfree(alldata);
00194   return rval;
00195 }
00196 
00197 /* ========================================================================= */
00198 /** @} */
00199