proj home

Files   Classes   Functions   Hierarchy  

bsptreeD2< PT, PD, INDX > Class Template Reference

Binary Space Partition tree 2D. More...

#include <bsptreeD2.h>

Inheritance diagram for bsptreeD2< PT, PD, INDX >:
Collaboration diagram for bsptreeD2< PT, PD, INDX >:

List of all members.

Public Member Functions

boolc empty () const
 Are there no halfspaces in the bsp tree?
 bsptreeD2 ()
 Construct with a root node and two leafs.
void addroot (halfspaceD2< PT, PD > const &h)
 First halfspace put in the tree.
void addleft (INDX const mv, INDX const mvbitlength, halfspaceD2< PT, PD > const &h)
 Insert a halfspace left of mv halfspace.
void addright (INDX const mv, INDX const mvbitlength, halfspaceD2< PT, PD > const &h)
 Insert a halfspace right of mv halfspace.
void find (INDX &i, PT const &pt)
 Find the region given the point.
template<typename treeindexedD2iterINDX >
void clip (PD &t0, PD &t1, PT const &La, PT const &Lm, treeindexedD2iterINDX const &i1)
 Clip the line with the half-spaces.
istream & serializeInverse (istream &istr)
 Read in half-spaces to build the tree.
void find (linechoppedindexed< PT, PD, INDX > &L, PT const &p0, PT const &p1)
 The half-spaces chop the line segment from p0 to p1 into a list of line segments where intersection ocurres.
boolc validhalfspaces (INDX &errorh, INDX &errorhparent)
 Each half-space must intersect its parent.
void visibility (vector< INDX > &vnds, PT const &p0) const
template<>
double tmin
template<>
double tmax

Public Attributes

treeindexedD2< INDX > tree
 The tree is the bsp tree with indexes to the other data structures.
vector< halfspaceD2< PT, PD > > vi
 The half-spaces have the same index as their corresponding nodes.

Static Public Attributes

static PD tmin
 Large in size to represent an infinite line.
static PD tmax
 Large in size to represent an infinite line.

Detailed Description

template<typename PT, typename PD, typename INDX>
class bsptreeD2< PT, PD, INDX >

Binary Space Partition tree 2D.

Definition at line 21 of file bsptreeD2.h.

Constructor & Destructor Documentation

template<typename PT , typename PD , typename INDX >
bsptreeD2< PT, PD, INDX >::bsptreeD2 (  )  [inline]

Construct with a root node and two leafs.

Definition at line 579 of file bsptreeD2.h.

References bsptreeD2< PT, PD, INDX >::vi.

00580 {
00581   vi.push_back( halfspaceD2<PT,PD>() );
00582 }

Member Function Documentation

template<typename PT, typename PD, typename INDX>
void bsptreeD2< PT, PD, INDX >::addleft ( INDX const   mv,
INDX const   mvbitlength,
halfspaceD2< PT, PD > const &  h 
) [inline]

Insert a halfspace left of mv halfspace.

Definition at line 187 of file bsptreeD2.h.

Referenced by bsptree001::bspbuild().

00192 {
00193   tree.move(mv,mvbitlength);
00194   tree.addleft();
00195   vi.push_back(h);
00196 }

template<typename PT, typename PD, typename INDX>
void bsptreeD2< PT, PD, INDX >::addright ( INDX const   mv,
INDX const   mvbitlength,
halfspaceD2< PT, PD > const &  h 
) [inline]

Insert a halfspace right of mv halfspace.

Definition at line 200 of file bsptreeD2.h.

Referenced by bsptree001::bspbuild().

00205 {
00206   tree.move(mv,mvbitlength);
00207   tree.addright();
00208   vi.push_back(h);
00209 }

template<typename PT, typename PD, typename INDX >
void bsptreeD2< PT, PD, INDX >::addroot ( halfspaceD2< PT, PD > const &  h  )  [inline]

First halfspace put in the tree.

Definition at line 178 of file bsptreeD2.h.

References bsptreeD2< PT, PD, INDX >::vi.

Referenced by bsptree001::bspbuild().

00179 {
00180   assert(vi.size()==1);
00181 
00182   vi.push_back(h);
00183 }

template<typename PT, typename PD, typename INDX >
template<typename treeindexedD2iterINDX >
void bsptreeD2< PT, PD, INDX >::clip ( PD &  t0,
PD &  t1,
PT const &  La,
PT const &  Lm,
treeindexedD2iterINDX const &  i1 
) [inline]

Clip the line with the half-spaces.

The treeindex iterator contains a path which is travelled as the line is clipped. The last node in the path is not used for clipping.

Definition at line 293 of file bsptreeD2.h.

00300 {
00301   INDX index;
00302   INDX index2;
00303 
00304   uint sz = i1.path.size();
00305 
00306   if (sz<=1)
00307     return;
00308   
00309   --sz;
00310 
00311 //cout << SHOW(t0) << " " SHOW(t1) << " ";
00312 //cout << SHOW(La) << " " << SHOW(Lm) << endl;
00313 
00314   for (uint i=0; i<sz; ++i)
00315   {
00316     //cout << SHOW(i1.path[i]->index) << endl;
00317     index = i1.path[i]->index;
00318     index2 = i1.path[i+1]->index;
00319 //cout << SHOW(index) << endl;
00320 //cout << SHOW(index2) << endl;
00321 
00322     if ( i1.path[i]->isleftinternal(index2) )
00323       vi[index].clip(t0,t1,La,Lm);
00324     else
00325     {
00326       if ( i1.path[i]->isrightinternal(index2) )
00327       {
00328         vi[index].clipNeg(t0,t1,La,Lm);
00329       }
00330       else
00331         assert(false);
00332     }
00333   }
00334 
00335 }

template<typename PT, typename PD, typename INDX>
boolc bsptreeD2< PT, PD, INDX >::empty (  )  const [inline]

Are there no halfspaces in the bsp tree?

Definition at line 40 of file bsptreeD2.h.

00041     { return (vi.size()==1); }

template<typename PT, typename PD, typename INDX>
void bsptreeD2< PT, PD, INDX >::find ( linechoppedindexed< PT, PD, INDX > &  L,
PT const &  p0,
PT const &  p1 
) [inline]

The half-spaces chop the line segment from p0 to p1 into a list of line segments where intersection ocurres.

Definition at line 587 of file bsptreeD2.h.

References linechoppedindexed< PT, PD, INDX >::chain, and linechoppedindexed< PT, PD, INDX >::ln.

00592 {
00593   //<TODO> What is happening?
00594   assert(false);
00595 
00596   L.ln.constructfromendpoints(p0,p1);
00597   L.chain.clear();
00598   L.chain.push_back
00599   ( 
00600     pointindexed< point2<PD>, INDX >( point2<PD>(0.0,1.0), (INDX)0)
00601   ); 
00602 
00603 }

template<typename PT, typename PD , typename INDX>
void bsptreeD2< PT, PD, INDX >::find ( INDX &  i,
PT const &  pt 
) [inline]

Find the region given the point.

tree.current points to region i.

Definition at line 558 of file bsptreeD2.h.

References bsptreeD2< PT, PD, INDX >::tree, and bsptreeD2< PT, PD, INDX >::vi.

Referenced by bsptree001::currentsphere(), and treeindexedD2test::unittest02().

00559 {
00560   tree.reset();
00561 
00562   assert(tree.current!=0);
00563 
00564   while (tree.current->isleaf() == false)
00565   {
00566     assert(tree.current->index < vi.size());
00567     if (vi[tree.current->index].isInside(pt))
00568       tree.moveleft();
00569     else
00570       tree.moveright();
00571   
00572     assert(tree.current!=0);
00573   }
00574 
00575   i = tree.current->index;
00576 }

template<typename PT , typename PD , typename INDX >
istream & bsptreeD2< PT, PD, INDX >::serializeInverse ( istream &  istr  )  [inline]

Read in half-spaces to build the tree.

eg withindexes=1 4 0.0 -1.0 0.0 1.0 0 0 -2.0 1.0 -1.0 1.0 5 1 1.0 -0.5 2.0 -0.5 0 2 4.0 0.0 4.0 1.0 4 3 or without indexes withindexes=0 4 0.0 -1.0 0.0 1.0 -2.0 1.0 -1.0 1.0 1.0 -0.5 2.0 -0.5 4.0 0.0 4.0 1.0

Definition at line 465 of file bsptreeD2.h.

References bsptreeD2find< PT, PD, INDX >::find(), treeindexedD2node< INDX >::index, treeindexedD2node< INDX >::isleaf(), treeindexedD2node< INDX >::left, bsptreeD2find< PT, PD, INDX >::path, treeindexedD2node< INDX >::right, bsptreeD2< PT, PD, INDX >::tree, and bsptreeD2< PT, PD, INDX >::vi.

Referenced by operator>>().

00466 {
00467   tree.construct();
00468 
00469   bool withindexes;
00470   uint n;
00471   if (serializeInversePre(istr,withindexes,n)==false)
00472     return istr;
00473 
00474   PT p0;
00475   PT p1;
00476 
00477   INDX i0;
00478   INDX i1;
00479 
00480   treeindexedD2node<INDX> * parent;
00481 
00482   istr >> p0;
00483   istr >> p1;
00484   vi.push_back(halfspaceD2<PT,PD>(p0,p1));
00485   if (withindexes)
00486   {
00487     istr >> i0;
00488     istr >> i1;
00489     tree.root->left->index = i0;
00490     tree.root->right->index = i1;
00491   }
00492 
00493   if (n==1)
00494     return istr;
00495 
00496   INDX ifind;
00497 
00498   bsptreeD2find<PT,PD,INDX> bspf(*this);
00499 
00500   for (uint i=1; i<n; ++i)
00501   {
00502     istr >> p0;
00503     istr >> p1;
00504     vi.push_back(halfspaceD2<PT,PD>(p0,p1));
00505 
00506 //cout << SHOW( (stringc)tree ) << endl << endl;
00507 
00508     bspf.find(ifind,p0);
00509     parent = bspf.path[ bspf.path.size()-2 ];
00510     tree.current = parent;
00511     assert(parent!=0);
00512 
00513     if ((ifind==parent->left->index)&&(parent->left->isleaf()))
00514     {
00515       tree.addleft();
00516 
00517       if (withindexes)
00518       {
00519         istr >> i0;
00520         istr >> i1;
00521 
00522         tree.moveleft();
00523         tree.current->left->index=i0;
00524         tree.current->right->index=i1;
00525       }
00526 
00527       continue;
00528     }
00529 
00530     if ((ifind==parent->right->index)&&(parent->right->isleaf()))
00531     {
00532       tree.addright();
00533 
00534       if (withindexes)
00535       {
00536         istr >> i0;
00537         istr >> i1;
00538 
00539         tree.moveright();
00540         tree.current->left->index=i0;
00541         tree.current->right->index=i1;
00542       }
00543 
00544       continue;
00545     }
00546 
00547     assert(false);
00548   }
00549 
00550 //INDX errorh, errorhparent;
00551 //cout << SHOW(validhalfspaces(errorh,errorhparent)) << "  ";
00552 //cout << SHOW(errorh) << " " << SHOW(errorhparent) << endl;
00553 
00554   return istr;
00555 }

template<>
double bsptreeD2< treeindexedD2test::pt2, double, uint >::tmax (  )  [inline]

Definition at line 45 of file treeindexedD2test.cpp.

template<>
double bsptreeD2< treeindexedD2test::pt2, double, uint >::tmin (  )  [inline]

Definition at line 43 of file treeindexedD2test.cpp.

template<typename PT , typename PD , typename INDX>
boolc bsptreeD2< PT, PD, INDX >::validhalfspaces ( INDX &  errorh,
INDX &  errorhparent 
) [inline]

Each half-space must intersect its parent.

Definition at line 385 of file bsptreeD2.h.

References line< PT, PD >::intersects(), halfspaceD2< PT, PD >::p0, and halfspaceD2< PT, PD >::p1.

Referenced by treeindexedD2test::test05().

00389 {
00390   PT La;
00391   PT Lm;
00392   PT Lb;
00393 
00394   PD t0;
00395   PD t1;
00396 
00397   PD q0;
00398   PD q1;
00399 
00400   for ( treeindexedD2iterinternal<INDX> i1(tree); 
00401     !i1; ++i1 )
00402   {
00403     halfspaceD2<PT,PD> & h1(vi[i1()->index]);
00404 
00405     Lm = h1.p1-h1.p0;
00406     La = h1.p0;
00407     Lb = h1.p1;
00408 
00409     t0 = tmin;
00410     t1 = tmax;
00411 
00412     uint sz = i1.path.size();
00413     if (sz==0)
00414       continue;
00415 
00416     clip(t0,t1,La,Lm,i1);
00417 
00418     line<PT,PD> L1(Lm,La);
00419 
00420 //cout << SHOW(i1()->index) << endl;
00421     errorhparent = i1()->index;
00422 //cout << SHOW(errorhparent) << endl;
00423 
00424     // If the left node is a half-space, test that it
00425     // intersects its parent.
00426     if (i1()->left->isleaf()==false)
00427     {
00428       errorh = i1()->left->index;
00429 
00430       halfspaceD2<PT,PD> & h2(vi[i1()->left->index]);
00431       line<PT,PD> L2(h2.p1-h2.p0,h2.p0);
00432       if (L1.intersects(q0,q1,L2)==false)
00433         return false;
00434       
00435       // Is q0 in [t0,t1]?
00436       if (q0<t0)
00437         return false;
00438 
00439       if (q0>t1)
00440         return false;
00441     }
00442 
00443     if (i1()->right->isleaf()==false)
00444     {
00445       errorh = i1()->right->index;
00446 
00447       halfspaceD2<PT,PD> & h2(vi[i1()->right->index]);
00448       line<PT,PD> L2(h2.p1-h2.p0,h2.p0);
00449       if (L1.intersects(q0,q1,L2)==false)
00450         return false;
00451       
00452       // Is q0 in [t0,t1]?
00453       if (q0<t0)
00454         return false;
00455 
00456       if (q0>t1)
00457         return false;
00458     }
00459   }
00460 
00461   return true;
00462 }

template<typename PT, typename PD , typename INDX>
void bsptreeD2< PT, PD, INDX >::visibility ( vector< INDX > &  vnds,
PT const &  p0 
) const [inline]

Definition at line 214 of file bsptreeD2.h.

00218 {
00219   vnds.clear();
00220 
00221   if (tree.root==0)
00222     return;
00223 
00224   visibility(vnds,tree.root,p0);
00225 }

Member Data Documentation

template<typename PT, typename PD, typename INDX>
PD bsptreeD2< PT, PD, INDX >::tmax [static]

Large in size to represent an infinite line.

Definition at line 28 of file bsptreeD2.h.

template<typename PT, typename PD, typename INDX>
PD bsptreeD2< PT, PD, INDX >::tmin [static]

Large in size to represent an infinite line.

Definition at line 26 of file bsptreeD2.h.

template<typename PT, typename PD, typename INDX>
treeindexedD2<INDX> bsptreeD2< PT, PD, INDX >::tree

The tree is the bsp tree with indexes to the other data structures.

The nodes to the half-spaces and the regions to whatever the client indexes into.

Definition at line 33 of file bsptreeD2.h.

Referenced by bsptreeD2< PT, PD, INDX >::find(), bsptreeD2< PT, PD, INDX >::serializeInverse(), treeindexedD2test::test03(), and treeindexedD2test::unittest02().

template<typename PT, typename PD, typename INDX>
vector< halfspaceD2<PT,PD> > bsptreeD2< PT, PD, INDX >::vi

The half-spaces have the same index as their corresponding nodes.

Definition at line 37 of file bsptreeD2.h.

Referenced by bsptreeD2< PT, PD, INDX >::addroot(), bsptreeD2< PT, PD, INDX >::bsptreeD2(), bsptreeD2< pt2, double, uint >::empty(), bsptreeD2< PT, PD, INDX >::find(), bsptreeD2< PT, PD, INDX >::serializeInverse(), treeindexedD2test::test03(), and treeindexedD2test::unittest02().

The documentation for this class was generated from the following file:
Generated on Fri Mar 4 00:49:51 2011 for Chelton Evans Source by  doxygen 1.5.8