OpenWalnut  1.4.0
WHierarchicalTreeVoxels.cpp
00001 //---------------------------------------------------------------------------
00002 //
00003 // Project: OpenWalnut ( http://www.openwalnut.org )
00004 //
00005 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS
00006 // For more information see http://www.openwalnut.org/copying
00007 //
00008 // This file is part of OpenWalnut.
00009 //
00010 // OpenWalnut is free software: you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as published by
00012 // the Free Software Foundation, either version 3 of the License, or
00013 // (at your option) any later version.
00014 //
00015 // OpenWalnut is distributed in the hope that it will be useful,
00016 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018 // GNU Lesser General Public License for more details.
00019 //
00020 // You should have received a copy of the GNU Lesser General Public License
00021 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>.
00022 //
00023 //---------------------------------------------------------------------------
00024 
00025 #include <algorithm>
00026 #include <iostream>
00027 #include <utility>
00028 #include <vector>
00029 #include <queue>
00030 #include <list>
00031 
00032 #include "WHierarchicalTreeVoxels.h"
00033 
00034 WHierarchicalTreeVoxels::WHierarchicalTreeVoxels() :
00035     WHierarchicalTree()
00036 {
00037 }
00038 
00039 WHierarchicalTreeVoxels::~WHierarchicalTreeVoxels()
00040 {
00041 }
00042 
00043 void WHierarchicalTreeVoxels::addLeaf()
00044 {
00045 }
00046 
00047 void WHierarchicalTreeVoxels::addLeaf( size_t voxelnum )
00048 {
00049     // after a cluster was added no more leafes may be inserted
00050     if( m_leafesLocked )
00051     {
00052         return;
00053     }
00054     m_level.push_back( 0 );
00055     m_parents.push_back( m_clusterCount );
00056     std::vector<size_t> tmp( 1, m_clusterCount );
00057     m_containsLeafes.push_back( tmp );
00058     std::pair<size_t, size_t>tmp2;
00059     m_children.push_back( tmp2 );
00060     m_customData.push_back( 0.0 );
00061     m_colors.push_back( WColor( 0.3, 0.3, 0.3, 1.0 ) );
00062     m_voxelnums.push_back( voxelnum );
00063 
00064     ++m_leafCount;
00065     ++m_clusterCount;
00066 }
00067 
00068 void WHierarchicalTreeVoxels::addCluster( size_t cluster1, size_t cluster2, float customData )
00069 {
00070     m_leafesLocked = true;
00071 
00072     size_t level = std::max( m_level[cluster1], m_level[cluster2] ) + 1;
00073     m_level.push_back( level );
00074 
00075     m_maxLevel = std::max( m_maxLevel, level );
00076 
00077     m_parents.push_back( m_clusterCount );
00078     m_customData.push_back( customData );
00079     m_colors.push_back( WColor( 0.3, 0.3, 0.3, 1.0 ) );
00080 
00081     std::pair<size_t, size_t>childs( cluster1, cluster2 );
00082     m_children.push_back( childs );
00083 
00084     std::vector<size_t>leafes;
00085     leafes.reserve( m_containsLeafes[cluster1].size() + m_containsLeafes[cluster2].size() );
00086     leafes.insert( leafes.end(), m_containsLeafes[cluster1].begin(), m_containsLeafes[cluster1].end() );
00087     leafes.insert( leafes.end(), m_containsLeafes[cluster2].begin(), m_containsLeafes[cluster2].end() );
00088     m_containsLeafes.push_back( leafes );
00089 
00090     m_parents[cluster1] = m_clusterCount;
00091     m_parents[cluster2] = m_clusterCount;
00092 
00093     ++m_clusterCount;
00094 }
00095 
00096 std::vector<size_t> WHierarchicalTreeVoxels::getVoxelsForCluster( size_t cluster )
00097 {
00098     std::vector<size_t>returnVec = getLeafesForCluster( cluster );
00099 
00100     for( size_t i = 0; i < returnVec.size(); ++i )
00101     {
00102         returnVec[i] = m_voxelnums[returnVec[i]];
00103     }
00104     return returnVec;
00105 }
00106 
00107 std::vector< size_t > WHierarchicalTreeVoxels::findClustersForValue( float value )
00108 {
00109     // init
00110     std::list<size_t>worklist;
00111     std::vector<size_t>returnVector;
00112 
00113     if( value < getCustomData( m_clusterCount - 1 ) )
00114     {
00115         worklist.push_back( m_clusterCount - 1 );
00116     }
00117 
00118     while( !worklist.empty() )
00119     {
00120         size_t current = worklist.front();
00121         worklist.pop_front();
00122         if( m_containsLeafes[current].size() > 1 )
00123         {
00124             size_t left = m_children[current].first;
00125             size_t right = m_children[current].second;
00126 
00127             if( value < getCustomData( left ) )
00128             {
00129                 worklist.push_back( left );
00130             }
00131             else
00132             {
00133                 returnVector.push_back( left );
00134             }
00135             if( value < getCustomData( right ) )
00136             {
00137                 worklist.push_back( right );
00138             }
00139             else
00140             {
00141                 returnVector.push_back( right );
00142             }
00143         }
00144     }
00145     return returnVector;
00146 }
00147 
00148 std::vector< size_t >WHierarchicalTreeVoxels::findClustersForBranchLength( float value, size_t minSize )
00149 {
00150     // init
00151     std::list<size_t>worklist;
00152     std::vector<size_t>returnVector;
00153 
00154     std::vector<int>distanceCheckVector( m_clusterCount, 0 );
00155 
00156     for( size_t i = m_leafCount; i < m_clusterCount; ++i )
00157     {
00158         if( ( distanceCheckVector[m_children[i].first] > 0 ) || ( distanceCheckVector[m_children[i].second] > 0 ) )
00159         {
00160             distanceCheckVector[i] = 2;
00161         }
00162         else if( ( ( m_containsLeafes[i].size() >= minSize ) && ( ( m_customData[m_parents[i]] - m_customData[i] ) > value ) ) )
00163         {
00164             distanceCheckVector[i] = 1;
00165             returnVector.push_back( i );
00166         }
00167     }
00168     return returnVector;
00169 }
00170 
00171 std::vector< size_t >WHierarchicalTreeVoxels::findXClusters( size_t root, size_t number )
00172 {
00173     std::vector<size_t>returnVector;
00174 
00175     std::list<size_t>worklist;
00176     worklist.push_back( root );
00177 
00178     while( worklist.size() < number )
00179     {
00180         size_t current = worklist.front();
00181         worklist.pop_front();
00182 
00183         size_t left = m_children[current].first;
00184         size_t right = m_children[current].second;
00185 
00186         worklist.push_back( left );
00187         worklist.push_back( right );
00188 
00189         worklist.sort( compValue( this ) );
00190     }
00191     std::cout << number << " clusters at " << m_customData[worklist.front()] << " energy" << std::endl;
00192 
00193     std::list<size_t>::iterator it;
00194     for( it = worklist.begin(); it != worklist.end(); ++it )
00195     {
00196         size_t current = *it;
00197         returnVector.push_back( current );
00198     }
00199 
00200     return returnVector;
00201 }