Visualization Library v1.0.3A lightweight C++ OpenGL middleware for 2D/3D graphics |
[Download] [Tutorials] [All Classes] [Grouped Classes] |
00001 /**************************************************************************************/ 00002 /* */ 00003 /* Visualization Library */ 00004 /* http://visualizationlibrary.org */ 00005 /* */ 00006 /* Copyright (c) 2005-2010, Michele Bosi */ 00007 /* All rights reserved. */ 00008 /* */ 00009 /* Redistribution and use in source and binary forms, with or without modification, */ 00010 /* are permitted provided that the following conditions are met: */ 00011 /* */ 00012 /* - Redistributions of source code must retain the above copyright notice, this */ 00013 /* list of conditions and the following disclaimer. */ 00014 /* */ 00015 /* - Redistributions in binary form must reproduce the above copyright notice, this */ 00016 /* list of conditions and the following disclaimer in the documentation and/or */ 00017 /* other materials provided with the distribution. */ 00018 /* */ 00019 /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND */ 00020 /* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED */ 00021 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE */ 00022 /* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR */ 00023 /* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES */ 00024 /* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; */ 00025 /* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON */ 00026 /* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT */ 00027 /* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS */ 00028 /* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ 00029 /* */ 00030 /**************************************************************************************/ 00031 00032 #ifndef RingExtractor_INCLUDE_ONCE 00033 #define RingExtractor_INCLUDE_ONCE 00034 00035 #include <vlCore/glsl_math.hpp> 00036 #include <vector> 00037 #include <algorithm> 00038 #include <map> 00039 #include <set> 00040 00041 namespace vl 00042 { 00044 class RingExtractor 00045 { 00046 public: 00047 RingExtractor(Molecule* mol): mMolecule(mol) {} 00048 00049 void setMolecule(Molecule* mol) { mMolecule = mol; } 00050 00051 Molecule* molecule() const { return mMolecule; } 00052 00053 void run() 00054 { 00055 if (!molecule()->atoms().empty()) 00056 { 00057 bootstrap(); 00058 removeDoubles(); 00059 sortCycles(); 00060 keepMinimalCycles(); 00061 keepAromaticCycles(); 00062 /*keepPlanarCycles(0.10f);*/ 00063 } 00064 } 00065 00066 void bootstrap() 00067 { 00068 if (!molecule()->atoms().empty()) 00069 { 00070 molecule()->computeAtomAdjacency(); 00071 for(int i=0; i<molecule()->atomCount(); ++i) 00072 molecule()->atom(i)->setVisited(false); 00073 std::vector< ref<Atom> > current_path; 00074 depthFirstVisit( molecule()->atoms()[0].get(), current_path ); 00075 } 00076 } 00077 00078 void depthFirstVisit(Atom* atom, std::vector< ref<Atom> >& current_path) 00079 { 00080 if ( !atom->visited() || current_path.empty()) 00081 { 00082 atom->setVisited(true); 00083 current_path.push_back(atom); 00084 for(unsigned i=0; i<atom->adjacentAtoms().size(); ++i) 00085 depthFirstVisit( atom->adjacentAtoms()[i], current_path ); 00086 current_path.pop_back(); 00087 atom->setVisited(false); 00088 } 00089 else // cycle found 00090 { 00091 /* condition: atom->visited() && !current_path.empty() */ 00092 00093 for(size_t i = current_path.size()-1; i--; ) 00094 { 00095 if ( current_path[i] == atom ) 00096 { 00097 std::vector< ref<Atom> > cycle; 00098 for(; i<current_path.size(); ++i) 00099 cycle.push_back( current_path[i] ); 00100 if (cycle.size() > 2) 00101 molecule()->cycles().push_back(cycle); 00102 break; 00103 } 00104 } 00105 } 00106 } 00107 00108 void keepAromaticCycles() 00109 { 00110 std::vector< std::vector< ref<Atom> > > kept_cycles; 00111 for(unsigned icycle=0; icycle<molecule()->cycles().size(); ++icycle) 00112 { 00113 int ok = true; 00114 for(unsigned iatom=0; iatom<molecule()->cycle(icycle).size(); ++iatom) 00115 { 00116 int iatom2 = (iatom+1) % molecule()->cycle(icycle).size(); 00117 Atom* atom1 = molecule()->cycle(icycle)[iatom].get(); 00118 Atom* atom2 = molecule()->cycle(icycle)[iatom2].get(); 00119 00120 Bond* bond = molecule()->bond(atom1, atom2); 00121 if (bond && bond->bondType() != BT_Aromatic) 00122 { 00123 ok = false; 00124 break; 00125 } 00126 } 00127 if (ok && molecule()->cycle(icycle).size()) 00128 kept_cycles.push_back(molecule()->cycle(icycle)); 00129 } 00130 molecule()->cycles() = kept_cycles; 00131 } 00132 00133 void sortCycles() 00134 { 00135 for(unsigned icycle=0; icycle<molecule()->cycles().size(); ++icycle) 00136 { 00137 std::vector< ref<Atom> >& cycle = molecule()->cycle(icycle); 00138 for(unsigned iatom=0; iatom<cycle.size()-1; ++iatom) 00139 { 00140 Atom* atom = cycle[iatom].get(); 00141 for(unsigned j=iatom+1; j<cycle.size(); ++j) 00142 { 00143 if (atom->isAtomAdjacent(cycle[j].get())) 00144 { 00145 Atom* tmp = cycle[iatom+1].get(); 00146 cycle[iatom+1] = cycle[j]; 00147 cycle[j] = tmp; 00148 break; 00149 } 00150 } 00151 } 00152 } 00153 } 00154 00155 void keepPlanarCycles(float epsilon) 00156 { 00157 std::vector< std::vector< ref<Atom> > > kept_cycles; 00158 for(unsigned icycle=0; icycle<molecule()->cycles().size(); ++icycle) 00159 { 00160 AABB aabb; 00161 for(unsigned iatom=0; iatom<molecule()->cycle(icycle).size(); ++iatom) 00162 aabb += (vec3)molecule()->cycle(icycle)[iatom]->coordinates(); 00163 fvec3 center = (fvec3)aabb.center(); 00164 00165 fvec3 normal; 00166 for(unsigned iatom=0; iatom<molecule()->cycle(icycle).size(); ++iatom) 00167 { 00168 int iatom2 = (iatom+1) % molecule()->cycle(icycle).size(); 00169 Atom* atom1 = molecule()->cycle(icycle)[iatom].get(); 00170 Atom* atom2 = molecule()->cycle(icycle)[iatom2].get(); 00171 fvec3 v1 = (atom1->coordinates()-center).normalize(); 00172 fvec3 v2 = (atom2->coordinates()-center).normalize(); 00173 normal += cross(v1, v2); 00174 } 00175 normal.normalize(); 00176 00177 int ok = true; 00178 for(unsigned iatom=0; iatom<molecule()->cycle(icycle).size(); ++iatom) 00179 { 00180 fvec3 v1 = molecule()->cycle(icycle)[iatom]->coordinates() - center; 00181 float dist = dot(normal, v1); 00182 if (fabs(dist)>epsilon) 00183 { 00184 ok = false; 00185 break; 00186 } 00187 } 00188 if (ok && molecule()->cycle(icycle).size()) 00189 kept_cycles.push_back(molecule()->cycle(icycle)); 00190 } 00191 molecule()->cycles() = kept_cycles; 00192 } 00193 00194 void removeDoubles() 00195 { 00196 for(unsigned icycle=0; icycle<molecule()->cycles().size(); ++icycle) 00197 std::stable_sort(molecule()->cycle(icycle).begin(), molecule()->cycle(icycle).end()); 00198 std::stable_sort(molecule()->cycles().begin(), molecule()->cycles().end()); 00199 std::vector< std::vector< ref<Atom> > >::iterator new_end = std::unique(molecule()->cycles().begin(), molecule()->cycles().end()); 00200 std::vector< std::vector< ref<Atom> > > unique_cycles; 00201 for(std::vector< std::vector< ref<Atom> > >::iterator it = molecule()->cycles().begin(); it != new_end; ++it) 00202 unique_cycles.push_back(*it); 00203 molecule()->cycles() = unique_cycles; 00204 } 00205 00206 void keepMinimalCycles() 00207 { 00208 std::vector< std::vector< ref<Atom> > > sub_cycles; 00209 00210 std::map<Atom*, bool> my_atom; 00211 for(unsigned j=0; j<molecule()->atoms().size(); ++j) 00212 my_atom[molecule()->atoms()[j].get()] = false; 00213 00214 for(unsigned icycle=0; icycle<molecule()->cycles().size(); ++icycle) 00215 { 00216 // init 00217 for(unsigned j=0; j<molecule()->cycles()[icycle].size(); ++j) 00218 my_atom[ molecule()->cycles()[icycle][j].get() ] = true; 00219 00220 bool is_sup_cycle = false; 00221 for(unsigned j=0; j<molecule()->cycles().size(); ++j) 00222 { 00223 if (j == icycle) 00224 continue; 00225 unsigned shared_atoms = 0; 00226 for(unsigned k=0; k<molecule()->cycles()[j].size(); k++) 00227 shared_atoms += my_atom[ molecule()->cycles()[j][k].get() ] ? 1 : 0; 00228 if ( shared_atoms == molecule()->cycles()[j].size() ) 00229 { 00230 is_sup_cycle = true; 00231 break; 00232 } 00233 } 00234 if (!is_sup_cycle) 00235 sub_cycles.push_back( molecule()->cycles()[icycle] ); 00236 00237 // reset 00238 for(unsigned j=0; j<molecule()->cycles()[icycle].size(); ++j) 00239 my_atom[ molecule()->cycles()[icycle][j].get() ] = false; 00240 } 00241 molecule()->cycles() = sub_cycles; 00242 } 00243 00244 protected: 00245 Molecule* mMolecule; 00246 }; 00247 } 00248 00249 #endif