BVTQ.h
Go to the documentation of this file.
00001 /*************************************************************************\
00002 
00003   Copyright 1999 The University of North Carolina at Chapel Hill.
00004   All Rights Reserved.
00005 
00006   Permission to use, copy, modify and distribute this software and its
00007   documentation for educational, research and non-profit purposes, without
00008   fee, and without a written agreement is hereby granted, provided that the
00009   above copyright notice and the following three paragraphs appear in all
00010   copies.
00011 
00012   IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL BE
00013   LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR
00014   CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE
00015   USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY
00016   OF NORTH CAROLINA HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH
00017   DAMAGES.
00018 
00019   THE UNIVERSITY OF NORTH CAROLINA SPECIFICALLY DISCLAIM ANY
00020   WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
00021   MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE
00022   PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
00023   NORTH CAROLINA HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT,
00024   UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
00025 
00026   The authors may be contacted via:
00027 
00028   US Mail:             E. Larsen
00029                        Department of Computer Science
00030                        Sitterson Hall, CB #3175
00031                        University of N. Carolina
00032                        Chapel Hill, NC 27599-3175
00033 
00034   Phone:               (919)962-1749
00035 
00036   EMail:               geom@cs.unc.edu
00037 
00038 
00039 \**************************************************************************/
00040 
00041 #ifndef PQP_BVTQ_H
00042 #define PQP_BVTQ_H
00043 
00044 #include <stdio.h>
00045 #include <stdlib.h>
00046 #include "PQP_Compile.h"
00047 
00048 inline
00049 int 
00050 LChild(int p)  
00051 { 
00052   return (2*p + 1); 
00053 } 
00054 
00055 inline 
00056 int 
00057 Parent(int c)  
00058 { 
00059   return ((c - 1)/2); 
00060 } 
00061 
00062 struct BVT 
00063 { 
00064   PQP_REAL d;       // distance between the bvs
00065   int b1, b2;       // bv numbers - b1 is from model 1, b2 from model 2
00066   PQP_REAL R[3][3]; // the relative rotation from b1 to b2
00067   PQP_REAL T[3];    // the relative translation from b1 to b2
00068   int pindex;       // the index of the pointer that points to this -
00069                     // needed when filling the hole left by an ExtractMin
00070 };
00071 
00072 class BVTQ 
00073 { 
00074   int size;       // max number of bv tests
00075   int numtests;   // number of bv tests in queue
00076   BVT *bvt;       // an array of bv tests - seems faster than 'new' for each
00077   BVT **bvtp;     // the queue: an array of pointers to elts of bvt
00078 
00079 public:
00080   BVTQ(int sz) 
00081   {
00082     size = sz;              
00083     bvt = new BVT[size];    
00084     bvtp = new BVT*[size];  
00085     numtests = 0;
00086   }
00087   ~BVTQ() { delete [] bvt; delete [] bvtp; }
00088   int Empty() { return (numtests == 0); }
00089   int GetNumTests() { return numtests; }
00090   int GetSize() { return size; }
00091   PQP_REAL MinTest() { return bvtp[0]->d; }
00092   BVT ExtractMinTest();
00093   void AddTest(BVT &);
00094 };
00095 
00096 inline
00097 void 
00098 BVTQ::AddTest(BVT &t)
00099 {
00100   bvtp[numtests] = &bvt[numtests];
00101 
00102   *bvtp[numtests] = t;
00103   bvtp[numtests]->pindex = numtests;
00104   
00105   BVT *temp;
00106   int c = numtests;
00107   int p;
00108   
00109   while ((c != 0) && (bvtp[(p = Parent(c))]->d >= bvtp[c]->d)) 
00110   {
00111     // swap p and c pointers
00112 
00113     temp = bvtp[p];
00114     bvtp[p] = bvtp[c];
00115     bvtp[c] = temp;      
00116 
00117     // the bv tests pointed to by p and c need new indices
00118 
00119     bvtp[p]->pindex = p;
00120     bvtp[c]->pindex = c;
00121 
00122     c = p;
00123   } 
00124   numtests++; 
00125 }
00126 
00127 inline
00128 BVT
00129 BVTQ::ExtractMinTest()
00130 {
00131   // store min test to be extracted
00132 
00133   BVT min_test = *bvtp[0];
00134 
00135   // copy last bvt to the empty space;
00136   // reset the pointer to this moved bvt
00137 
00138   *bvtp[0] = bvt[numtests-1];
00139   bvtp[bvt[numtests-1].pindex] = bvtp[0];
00140 
00141   // copy the last pointer to the first
00142 
00143   bvtp[0] = bvtp[numtests-1];
00144 
00145   numtests--; 
00146 
00147   BVT *temp;
00148   int p = 0; 
00149   int c1,c2,c; 
00150 
00151   while(1) 
00152   {     
00153     c1 = LChild(p); 
00154     c2 = c1+1; 
00155   
00156     if (c1 < numtests) 
00157     { 
00158       if (c2 < numtests) 
00159       {         
00160         // p has both children, promote the minimum 
00161 
00162         if (bvtp[c1]->d < bvtp[c2]->d) c = c1; else c = c2; 
00163 
00164         if (bvtp[c]->d < bvtp[p]->d) 
00165         { 
00166           temp = bvtp[p];
00167           bvtp[p] = bvtp[c];
00168           bvtp[c] = temp; 
00169 
00170           bvtp[p]->pindex = p;
00171           bvtp[c]->pindex = c;
00172 
00173           p = c; 
00174         } 
00175         else 
00176         { 
00177           break; 
00178         } 
00179       } 
00180       else  
00181       {         
00182         // p has only left child 
00183 
00184         if (bvtp[c1]->d < bvtp[p]->d) 
00185         { 
00186           temp = bvtp[p]; 
00187           bvtp[p] = bvtp[c1]; 
00188           bvtp[c1] = temp; 
00189 
00190           bvtp[p]->pindex = p;
00191           bvtp[c1]->pindex = c1;
00192 
00193           p = c1;        
00194         } 
00195         else 
00196         { 
00197           break; 
00198         } 
00199       } 
00200     } 
00201     else 
00202     {   
00203       // p has no children 
00204 
00205       break; 
00206     } 
00207   } 
00208 
00209   return min_test;
00210 }
00211 
00212 #endif
00213 
00214 


jskeus
Author(s): JSK Alumnis
autogenerated on Tue Mar 7 2017 04:04:34