Loading [MathJax]/extensions/tex2jax.js
ug4
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
polychain_util_impl.hpp
Go to the documentation of this file.
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
37
38namespace ug
39{
40
42template <class TEdgeIterator>
43size_t
44GetPolyChainType(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 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 for(TEdgeIterator iter = edgesBegin; iter != edgesEnd; ++iter)
57 {
58 for(size_t i = 0; i < 2; ++i){
59 Vertex* v = (*iter)->vertex(i);
60
61 size_t counter = 0;
63 aiter != grid.associated_edges_end(v); ++aiter)
64 {
65 if(cbEdgeIsInPolyChain(*aiter))
66 ++counter;
67 }
68
69 if(counter == 0){
70 throw(UGError("cbEdgeIsInPolyChain does not evaluate to true for "
71 "edge between edgesBegin and edgesEnd."));
72 }
73
74 if(counter == 1)
75 ++numBnd;
76 else if(counter > 2)
77 irregular = true;
78 }
79 }
80
81// prepare the return value
82 size_t type = PCT_UNKNOWN;
83
84 if(numBnd == 0)
85 type = PCT_CLOSED;
86 else if(numBnd < 3)
87 type = PCT_OPEN;
88 else
89 type = PCT_SEPARATED;
90
91 if(irregular)
92 type |= PCT_IRREGULAR;
93
94 return type;
95}
96
98template <class TEdgeIterator>
99std::pair<Vertex*, Edge*>
100GetFirstSectionOfPolyChain(Grid& grid, TEdgeIterator edgesBegin,
101 TEdgeIterator edgesEnd,
102 Grid::edge_traits::callback cbEdgeIsInPolyChain)
103{
104 if(edgesBegin == edgesEnd)
105 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 for(size_t locInd = 0; locInd < 2; ++locInd){
110 // iterate through all edges.
111 for(TEdgeIterator iter = edgesBegin; iter != edgesEnd; ++iter)
112 {
113 Edge* curEdge = *iter;
114 Vertex* curVrt = curEdge->vertex(locInd);
115
116 // if curVrt is a boundary vertex of the given chain, then we're done.
117 if(IsBoundaryVertex1D(grid, curVrt, cbEdgeIsInPolyChain)){
118 return std::make_pair(curVrt, curEdge);
119 }
120 }
121 }
122
123 return std::make_pair((*edgesBegin)->vertex(0), *edgesBegin);
124}
125
126template <class TEdgeIter>
127bool CreatePolyChain(std::vector<Vertex*>& polyChainOut, Grid& grid,
128 TEdgeIter edgesBegin, TEdgeIter edgesEnd)
129{
130 polyChainOut.clear();
131
132 grid.begin_marking();
133
134// mark and count edges
135/*
136 int numEdges = 0; // unused
137*/
138 for(TEdgeIter iter = edgesBegin; iter != edgesEnd; ++iter){
139 grid.mark(*iter);
140 /*
141 ++numEdges; // s. the counter above and the check below
142 */
143 }
144
145//TODO: handle open chains.
146 Edge* actEdge = *edgesBegin;
147 Vertex* actVrt = actEdge->vertex(1);
148 polyChainOut.push_back(actEdge->vertex(0));
149 grid.mark(actEdge->vertex(0));
150 polyChainOut.push_back(actEdge->vertex(1));
151 grid.mark(actEdge->vertex(1));
152
153 bool bRunning = true;
154 while(bRunning){
155 bRunning = false;
156 // find a connected unmarked vertex
157 Grid::AssociatedEdgeIterator assEdgesEnd = grid.associated_edges_end(actVrt);
159 eIter != assEdgesEnd; ++eIter)
160 {
161 Edge* e = *eIter;
162 if(grid.is_marked(e)){
163 // check whether the connected vertex is unmarked
164 Vertex* cv = GetConnectedVertex(e, actVrt);
165 if(!grid.is_marked(cv)){
166 // push it to the chain and mark it.
167 grid.mark(cv);
168 polyChainOut.push_back(cv);
169 // we're done with actVrt. cv will be the new actVrt
170 actVrt = cv;
171 bRunning = true;
172 break;
173 }
174 }
175 }
176 }
177
178 grid.end_marking();
179/*
180 if(polyChainOut.size() != numEdges) // s. the commented counter above
181 return false;
182*/
183 return true;
184}
185
186}// end of namespace
187
188#endif
Base-class for edges.
Definition grid_base_objects.h:397
virtual Vertex * vertex(size_t index) const
Definition grid_base_objects.h:366
Manages the elements of a grid and their interconnection.
Definition grid.h:132
EdgeContainer::iterator AssociatedEdgeIterator
used to iterate over associated edges of vertices, faces and volumes
Definition grid.h:249
void end_marking()
ends a marking sequence. Call this method when you're done with marking.
Definition grid.cpp:1285
AssociatedEdgeIterator associated_edges_begin(Vertex *vrt)
DO NOT INVOKE! Subject to change.
Definition grid.cpp:882
bool is_marked(GridObject *obj) const
returns true if the object is marked, false if not.
Definition grid_impl.hpp:843
AssociatedEdgeIterator associated_edges_end(Vertex *vrt)
DO NOT INVOKE! Subject to change.
Definition grid.cpp:892
void mark(GridObject *obj)
marks the object. Calls are only valid between calls to Grid::begin_marking and Grid::end_marking.
Definition grid_impl.hpp:773
void begin_marking()
begin marking.
Definition grid.cpp:1262
Instances of this class or of derived classes are thrown if errors arise.
Definition error.h:104
Base-class for all vertex-types.
Definition grid_base_objects.h:231
size_t GetPolyChainType(Grid &grid, TEdgeIterator edgesBegin, TEdgeIterator edgesEnd, Grid::edge_traits::callback cbEdgeIsInPolyChain)
returns an or combination of constants enumerated in PolyChainTypes.
Definition polychain_util_impl.hpp:44
std::pair< Vertex *, Edge * > GetFirstSectionOfPolyChain(Grid &grid, TEdgeIterator edgesBegin, TEdgeIterator edgesEnd, Grid::edge_traits::callback cbEdgeIsInPolyChain)
Returns the start-vertex and start-edge of a polygonal chain.
Definition polychain_util_impl.hpp:100
bool CreatePolyChain(std::vector< Vertex * > &polyChainOut, Grid &grid, TEdgeIter edgesBegin, TEdgeIter edgesEnd)
given a list of edges, this method collects associated vertices in a polychain
Definition polychain_util_impl.hpp:127
@ PCT_OPEN
Definition polychain_util.h:53
@ PCT_EMPTY
Definition polychain_util.h:56
@ PCT_SEPARATED
Definition polychain_util.h:54
@ PCT_CLOSED
Definition polychain_util.h:52
@ PCT_IRREGULAR
Definition polychain_util.h:55
@ PCT_UNKNOWN
Definition polychain_util.h:51
bool IsBoundaryVertex1D(Grid &grid, Vertex *v, Grid::edge_traits::callback cbConsiderEdge)
returns whether a vertex lies on the boundary of a polygonal chain.
Definition vertex_util.cpp:504
Vertex * GetConnectedVertex(Edge *e, Vertex *v)
returns the vertex that is connected to v via e.
Definition vertex_util.cpp:78
the ug namespace
boost::function< bool(base_object *)> callback
callback type for the elements base type.
Definition grid.h:150