Line data Source code
1 : /*
2 : * Copyright (c) 2010-2015: G-CSC, Goethe University Frankfurt
3 : * Author: Sebastian Reiter
4 : *
5 : * This file is part of UG4.
6 : *
7 : * UG4 is free software: you can redistribute it and/or modify it under the
8 : * terms of the GNU Lesser General Public License version 3 (as published by the
9 : * Free Software Foundation) with the following additional attribution
10 : * requirements (according to LGPL/GPL v3 §7):
11 : *
12 : * (1) The following notice must be displayed in the Appropriate Legal Notices
13 : * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14 : *
15 : * (2) The following notice must be displayed at a prominent place in the
16 : * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17 : *
18 : * (3) The following bibliography is recommended for citation and must be
19 : * preserved in all covered files:
20 : * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21 : * parallel geometric multigrid solver on hierarchically distributed grids.
22 : * Computing and visualization in science 16, 4 (2013), 151-164"
23 : * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24 : * flexible software system for simulating pde based models on high performance
25 : * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26 : *
27 : * This program is distributed in the hope that it will be useful,
28 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 : * GNU Lesser General Public License for more details.
31 : */
32 :
33 : #ifndef __H__LIB_GRID__POLYCHAIN_UTIL_IMPL__
34 : #define __H__LIB_GRID__POLYCHAIN_UTIL_IMPL__
35 :
36 : #include "geom_obj_util/vertex_util.h"
37 :
38 : namespace ug
39 : {
40 :
41 : ////////////////////////////////////////////////////////////////////////
42 : template <class TEdgeIterator>
43 : size_t
44 0 : GetPolyChainType(Grid& grid, TEdgeIterator edgesBegin,
45 : TEdgeIterator edgesEnd,
46 : Grid::edge_traits::callback cbEdgeIsInPolyChain)
47 : {
48 : // if the chain is empty, there's nothing to do
49 0 : if(edgesBegin == edgesEnd)
50 : return PCT_EMPTY;
51 :
52 : // check for each vertex to how many chain-edges it is connected
53 : size_t numBnd = 0;
54 : bool irregular = false;
55 :
56 0 : for(TEdgeIterator iter = edgesBegin; iter != edgesEnd; ++iter)
57 : {
58 0 : for(size_t i = 0; i < 2; ++i){
59 0 : Vertex* v = (*iter)->vertex(i);
60 :
61 : size_t counter = 0;
62 0 : for(Grid::AssociatedEdgeIterator aiter = grid.associated_edges_begin(v);
63 0 : aiter != grid.associated_edges_end(v); ++aiter)
64 : {
65 0 : if(cbEdgeIsInPolyChain(*aiter))
66 0 : ++counter;
67 : }
68 :
69 0 : if(counter == 0){
70 0 : throw(UGError("cbEdgeIsInPolyChain does not evaluate to true for "
71 : "edge between edgesBegin and edgesEnd."));
72 : }
73 :
74 0 : if(counter == 1)
75 0 : ++numBnd;
76 0 : else if(counter > 2)
77 : irregular = true;
78 : }
79 : }
80 :
81 : // prepare the return value
82 : size_t type = PCT_UNKNOWN;
83 :
84 0 : if(numBnd == 0)
85 : type = PCT_CLOSED;
86 0 : else if(numBnd < 3)
87 : type = PCT_OPEN;
88 : else
89 : type = PCT_SEPARATED;
90 :
91 0 : if(irregular)
92 0 : type |= PCT_IRREGULAR;
93 :
94 : return type;
95 : }
96 :
97 : ////////////////////////////////////////////////////////////////////////
98 : template <class TEdgeIterator>
99 : std::pair<Vertex*, Edge*>
100 0 : GetFirstSectionOfPolyChain(Grid& grid, TEdgeIterator edgesBegin,
101 : TEdgeIterator edgesEnd,
102 : Grid::edge_traits::callback cbEdgeIsInPolyChain)
103 : {
104 0 : if(edgesBegin == edgesEnd)
105 0 : return std::make_pair<Vertex*, Edge*>(NULL, NULL);
106 :
107 : // since we want to prefer vertices with local edge index 0, we'll first iterate
108 : // over the local indices of the edges
109 0 : for(size_t locInd = 0; locInd < 2; ++locInd){
110 : // iterate through all edges.
111 0 : for(TEdgeIterator iter = edgesBegin; iter != edgesEnd; ++iter)
112 : {
113 : Edge* curEdge = *iter;
114 0 : Vertex* curVrt = curEdge->vertex(locInd);
115 :
116 : // if curVrt is a boundary vertex of the given chain, then we're done.
117 0 : if(IsBoundaryVertex1D(grid, curVrt, cbEdgeIsInPolyChain)){
118 : return std::make_pair(curVrt, curEdge);
119 : }
120 : }
121 : }
122 :
123 0 : return std::make_pair((*edgesBegin)->vertex(0), *edgesBegin);
124 : }
125 :
126 : template <class TEdgeIter>
127 0 : bool CreatePolyChain(std::vector<Vertex*>& polyChainOut, Grid& grid,
128 : TEdgeIter edgesBegin, TEdgeIter edgesEnd)
129 : {
130 : polyChainOut.clear();
131 :
132 0 : grid.begin_marking();
133 :
134 : // mark and count edges
135 : /*
136 : int numEdges = 0; // unused
137 : */
138 0 : for(TEdgeIter iter = edgesBegin; iter != edgesEnd; ++iter){
139 0 : grid.mark(*iter);
140 : /*
141 : ++numEdges; // s. the counter above and the check below
142 : */
143 : }
144 :
145 : //TODO: handle open chains.
146 0 : Edge* actEdge = *edgesBegin;
147 0 : Vertex* actVrt = actEdge->vertex(1);
148 0 : polyChainOut.push_back(actEdge->vertex(0));
149 0 : grid.mark(actEdge->vertex(0));
150 0 : polyChainOut.push_back(actEdge->vertex(1));
151 0 : grid.mark(actEdge->vertex(1));
152 :
153 : bool bRunning = true;
154 0 : while(bRunning){
155 : bRunning = false;
156 : // find a connected unmarked vertex
157 0 : Grid::AssociatedEdgeIterator assEdgesEnd = grid.associated_edges_end(actVrt);
158 0 : for(Grid::AssociatedEdgeIterator eIter = grid.associated_edges_begin(actVrt);
159 0 : eIter != assEdgesEnd; ++eIter)
160 : {
161 0 : Edge* e = *eIter;
162 0 : if(grid.is_marked(e)){
163 : // check whether the connected vertex is unmarked
164 0 : Vertex* cv = GetConnectedVertex(e, actVrt);
165 0 : if(!grid.is_marked(cv)){
166 : // push it to the chain and mark it.
167 : grid.mark(cv);
168 0 : polyChainOut.push_back(cv);
169 : // we're done with actVrt. cv will be the new actVrt
170 : actVrt = cv;
171 : bRunning = true;
172 0 : break;
173 : }
174 : }
175 : }
176 : }
177 :
178 0 : grid.end_marking();
179 : /*
180 : if(polyChainOut.size() != numEdges) // s. the commented counter above
181 : return false;
182 : */
183 0 : return true;
184 : }
185 :
186 : }// end of namespace
187 :
188 : #endif
|
