00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
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
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
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
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 }