src/mesh/cfMesh/utilities/helperClasses/sortEdgesIntoChains/sortEdgesIntoChains.C

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | cfMesh: A library for mesh generation
   4    \\    /   O peration     |
   5     \\  /    A nd           | Author: Franjo Juretic (franjo.juretic@c-fields.com)
   6      \\/     M anipulation  | Copyright (C) Creative Fields, Ltd.
   7 -------------------------------------------------------------------------------
   8 License
   9     This file is part of cfMesh.
  10
  11     cfMesh is free software; you can redistribute it and/or modify it
  12     under the terms of the GNU General Public License as published by the
  13     Free Software Foundation; either version 3 of the License, or (at your
  14     option) any later version.
  15
  16     cfMesh is distributed in the hope that it will be useful, but WITHOUT
  17     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19     for more details.
  20
  21     You should have received a copy of the GNU General Public License
  22     along with cfMesh.  If not, see <http://www.gnu.org/licenses/>.
  23
  24 Description
  25
  26 \*---------------------------------------------------------------------------*/
  27
  28 #include "sortEdgesIntoChains.H"
  29 #include "helperFunctions.H"
  30 #include "Map.H"
  31
  32 //#define DEBUGSort
  33
  34 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
  35
  36 namespace Foam
  37 {
  38
  39 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
  40
  41 void sortEdgesIntoChains::createNodeLabels()
  42 {
  43     label nPoints(0);
  44     forAll(bEdges_, eI)
  45     {
  46         const edge& e = bEdges_[eI];
  47         if( !newNodeLabel_.found(e.start()) )
  48             newNodeLabel_.insert(e.start(), nPoints++);
  49         if( !newNodeLabel_.found(e.end()) )
  50             newNodeLabel_.insert(e.end(), nPoints++);
  51     }
  52
  53     edgesAtPoint_.setSize(nPoints, DynList<label>());
  54     forAll(bEdges_, eI)
  55     {
  56         const edge& e = bEdges_[eI];
  57         label l = newNodeLabel_[e.start()];
  58         edgesAtPoint_[l].append(eI);
  59
  60         l = newNodeLabel_[e.end()];
  61         edgesAtPoint_[l].append(eI);
  62     }
  63
  64     forAll(edgesAtPoint_, pI)
  65         if( edgesAtPoint_[pI].size() % 2 )
  66             openEdges_ = true;
  67 }
  68
  69 bool sortEdgesIntoChains::findPointsBelongingToTheChain
  70 (
  71     const label currPos,
  72     boolList& chainEdges
  73 ) const
  74 {
  75     # ifdef DEBUGSort
  76     Info << "Finding point belonging to a chain" << endl;
  77     # endif
  78
  79     chainEdges.setSize(bEdges_.size());
  80     chainEdges = false;
  81
  82     if( edgesAtPoint_[currPos].size() != 2 )
  83         return false;
  84
  85     const label commonVrt =
  86         bEdges_[edgesAtPoint_[currPos][0]].commonVertex
  87             (
  88                 bEdges_[edgesAtPoint_[currPos][1]]
  89             );
  90     label prevVrt = bEdges_[edgesAtPoint_[currPos][0]].otherVertex(commonVrt);
  91     label nextVrt = bEdges_[edgesAtPoint_[currPos][1]].otherVertex(commonVrt);
  92     forAll(edgesAtPoint_[currPos], posI)
  93         chainEdges[edgesAtPoint_[currPos][posI]] = true;
  94
  95     # ifdef DEBUGSort
  96     Info << "commonVrt " << commonVrt << endl;
  97     Info << "prevVrt " << prevVrt << endl;
  98     Info << "nextVrt " << nextVrt << endl;
  99     # endif
 100
 101     bool found;
 102     do
 103     {
 104         found = false;
 105
 106         const DynList<label>& vEdges = edgesAtPoint_[newNodeLabel_[prevVrt]];
 107         if( vEdges.size() == 2 )
 108         {
 109             forAll(vEdges, eI)
 110                 if( !chainEdges[vEdges[eI]] )
 111                 {
 112                     found = true;
 113                     chainEdges[vEdges[eI]] = true;
 114                     prevVrt = bEdges_[vEdges[eI]].otherVertex(prevVrt);
 115                 }
 116         }
 117     } while( found );
 118
 119     do
 120     {
 121         found = false;
 122
 123         const DynList<label>& vEdges = edgesAtPoint_[newNodeLabel_[nextVrt]];
 124         if( vEdges.size() == 2 )
 125         {
 126             forAll(vEdges, eI)
 127                 if( !chainEdges[vEdges[eI]] )
 128                 {
 129                     found = true;
 130                     chainEdges[vEdges[eI]] = true;
 131                     nextVrt = bEdges_[vEdges[eI]].otherVertex(nextVrt);
 132                 }
 133         }
 134     } while( found );
 135
 136     if(
 137         (edgesAtPoint_[newNodeLabel_[nextVrt]].size() != 2) &&
 138         (edgesAtPoint_[newNodeLabel_[prevVrt]].size() != 2) &&
 139         (prevVrt != nextVrt)
 140     )
 141     {
 142         chainEdges = false;
 143         return false;
 144     }
 145
 146     # ifdef DEBUGSort
 147     Info << "Chain edges " << chainEdges << endl;
 148     # endif
 149
 150     return true;
 151 }
 152
 153 void sortEdgesIntoChains::shrinkEdges(const boolList& chainEdges)
 154 {
 155     forAll(chainEdges, eI)
 156         if( chainEdges[eI] )
 157         {
 158             const edge& e = bEdges_[eI];
 159             edgesAtPoint_[newNodeLabel_[e.start()]].removeElement
 160             (
 161                 edgesAtPoint_[newNodeLabel_[e.start()]].containsAtPosition(eI)
 162             );
 163
 164             edgesAtPoint_[newNodeLabel_[e.end()]].removeElement
 165             (
 166                 edgesAtPoint_[newNodeLabel_[e.end()]].containsAtPosition(eI)
 167             );
 168         }
 169 }
 170
 171 void sortEdgesIntoChains::createChainFromEdges(const boolList& chainEdges)
 172 {
 173     direction i(0);
 174     forAll(chainEdges, eI)
 175         if( chainEdges[eI] )
 176             ++i;
 177
 178     labelList chainPoints(i);
 179     i = 0;
 180
 181     forAll(chainEdges, eI)
 182         if( chainEdges[eI] )
 183         {
 184             chainPoints[i++] = bEdges_[eI].start();
 185             chainPoints[i++] = bEdges_[eI].end();
 186
 187             # ifdef DEBUGSort
 188             Info << "Init chainPoints " << chainPoints << endl;
 189             # endif
 190
 191             bool found;
 192             do
 193             {
 194                 # ifdef DEBUGSort
 195                 Info << "Iteration " << label(i-1) << endl;
 196                 # endif
 197
 198                 found = false;
 199                 const DynList<label>& pEdges =
 200                     edgesAtPoint_[newNodeLabel_[chainPoints[i-1]]];
 201
 202                 forAll(pEdges, peI)
 203                     if( chainEdges[pEdges[peI]] )
 204                     {
 205                         const label otherPoint =
 206                             bEdges_[pEdges[peI]].otherVertex(chainPoints[i-1]);
 207
 208                         # ifdef DEBUGSort
 209                         Info << "Other point " << otherPoint << endl;
 210                         # endif
 211                         if( otherPoint == -1 )
 212                             continue;
 213                         if( chainPoints[i-2] == otherPoint )
 214                             continue;
 215                         if( chainPoints[0] == otherPoint )
 216                             continue;
 217
 218                         found = true;
 219                         chainPoints[i++] = otherPoint;
 220                     }
 221             } while( found );
 222
 223             createdChains_.append(chainPoints);
 224
 225             break;
 226         }
 227 }
 228
 229 void sortEdgesIntoChains::sortEdges()
 230 {
 231     createNodeLabels();
 232
 233     if( !openEdges_ )
 234     {
 235         boolList chainEdges(bEdges_.size());
 236         forAll(edgesAtPoint_, pI)
 237             if( findPointsBelongingToTheChain(pI, chainEdges) )
 238             {
 239                 createChainFromEdges(chainEdges);
 240
 241                 shrinkEdges(chainEdges);
 242             }
 243     }
 244 }
 245
 246 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *//
 247
 248 sortEdgesIntoChains::sortEdgesIntoChains(const DynList<edge>& bEdges)
 249 :
 250     bEdges_(bEdges),
 251     openEdges_(false),
 252     newNodeLabel_(),
 253     edgesAtPoint_(),
 254     createdChains_()
 255 {
 256     sortEdges();
 257 }
 258
 259 sortEdgesIntoChains::~sortEdgesIntoChains()
 260 {
 261 }
 262
 263 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *//
 264 // Member functions
 265 const DynList<labelList>& sortEdgesIntoChains::sortedChains() const
 266 {
 267     return createdChains_;
 268 }
 269
 270 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *//
 271
 272 } // End namespace Foam
 273
 274 // ************************************************************************* //