Line data Source code
1 : /*
2 : * Copyright (c) 2009-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__KD_TREE__
34 : #define __H__LIB_GRID__KD_TREE__
35 :
36 : #include "lib_grid/grid/grid.h"
37 :
38 : namespace ug
39 : {
40 :
41 : /// \addtogroup lib_grid_algorithms_trees
42 : /// @{
43 :
44 : ////////////////////////////////////////////////////////////////////////////////////////////////
45 : //KDTREE
46 :
47 : ////////////////////////////////////////////////////////////////////////
48 : /// used by KDTreeStatic
49 : class KDVertexDistance
50 : {
51 : public:
52 : KDVertexDistance() {}
53 0 : KDVertexDistance(Vertex* vrt, float nDistSQ) : vertex(vrt), distSQ(nDistSQ) {}
54 :
55 : Vertex* vertex;
56 : number distSQ;
57 : };
58 :
59 : ////////////////////////////////////////////////////////////////////////
60 : /// used by KDTreeStatic
61 : enum KDSplitDimension
62 : {
63 : KDSD_CIRCULAR,
64 : KDSD_LARGEST
65 : };
66 :
67 : typedef std::list<KDVertexDistance> KDVertexDistanceList;
68 :
69 : ////////////////////////////////////////////////////////////////////////
70 : ////////////////////////////////////////////////////////////////////////
71 : // KDTreeStatic
72 : /// organizes vertices in a binary-tree structure. Only for static use!
73 : /**
74 : * A kd-tree allows you to find vertices close to a given position in O(log(n)).
75 : *
76 : * This kd-tree should be only used for static geometry. If you intend to
77 : * add or delete vertices after creation, KDTreeStatic is not suited for your
78 : * needs.
79 : *
80 : * This class should be replaced by a dynamic kd-tree, which is capable of
81 : * dynamic auto-balancing.
82 : */
83 : template <class TPositionAttachment, int numDimensions = 3, class TVector = vector3 >
84 : class KDTreeStatic
85 : {
86 : public:
87 : typedef std::vector<Vertex*> VertexVec;
88 :
89 : class Node
90 : {
91 : public:
92 0 : Node() : m_pvVertices(NULL) {m_pChild[0] = m_pChild[1] = NULL;}
93 0 : ~Node() {clear();}
94 :
95 : void clear();
96 :
97 : Node* m_pChild[2]; // 0: pos, 1: neg
98 : float m_fSplitValue;
99 : int m_iSplitDimension;
100 : VertexVec* m_pvVertices;
101 : };
102 :
103 : // the functions
104 0 : KDTreeStatic() : m_pGrid(NULL) {};
105 :
106 : void clear();
107 :
108 : template <class TVrtIterator>
109 : bool create_from_grid(Grid& grid, TVrtIterator vrtsBegin, TVrtIterator vrtsEnd,
110 : TPositionAttachment& aPos, int maxTreeDepth, int splitThreshold,
111 : KDSplitDimension splitDimension = KDSD_LARGEST);
112 :
113 : template <class TVrtIterator>
114 : bool create_from_grid(Grid& grid, TVrtIterator vrtsBegin, TVrtIterator vrtsEnd,
115 : Grid::VertexAttachmentAccessor<TPositionAttachment> aaPos,
116 : int maxTreeDepth, int splitThreshold,
117 : KDSplitDimension splitDimension = KDSD_LARGEST);
118 :
119 : bool get_neighbourhood(std::vector<Vertex*>& vrtsOut,
120 : typename TPositionAttachment::ValueType& pos, int numClosest);
121 :
122 : bool get_points_in_box(std::vector<Vertex*>& vrtsOut,
123 : const TVector& boxMin, const TVector& boxMax);
124 :
125 : Node* get_root() {return &m_parentNode;}
126 :
127 : void get_leafs(std::vector<Node*>& vLeafsOut);
128 :
129 : protected:
130 : bool get_points_in_box(std::vector<Vertex*>& vrtsOut, Node* pNode,
131 : const TVector& boxMin, const TVector& boxMax);
132 :
133 : void neighbourhood(KDVertexDistanceList& vrtsOut, Node* pNode, TVector& pos, int numClosest);
134 :
135 : template <class TVertexIterator>
136 : bool create_barycentric(TVertexIterator vrts_begin, TVertexIterator vrts_end,
137 : int numVertices, Node* pNode, int actDimension, int maxTreeDepth);
138 :
139 : template <class TVertexIterator>
140 : int get_largest_dimension(TVertexIterator vrts_begin, TVertexIterator vrts_end);
141 :
142 : template <class TVertexIterator>
143 : int get_next_split_dimension(int actSplitDimension, TVertexIterator vrts_begin,
144 : TVertexIterator vrts_end);
145 :
146 : void get_leafs_recursive(std::vector<Node*>& vLeafsOut, Node* pNode);
147 :
148 : // members
149 : Grid* m_pGrid;
150 : Grid::VertexAttachmentAccessor<TPositionAttachment> m_aaPos;
151 : int m_iSplitThreshold;
152 : Node m_parentNode;
153 : KDSplitDimension m_splitDimension; // how is the next split dimension choosen?
154 :
155 : // some helper vars for neighbourhood search
156 : int m_numNeighboursFound;
157 : float m_maxDistSQ;
158 : };
159 :
160 : /// @}
161 :
162 : }// end of namespace
163 :
164 : ////////////////////////////////////////////////////////////////////////
165 : // include implementation
166 : #include "kd_tree_static_impl.hpp"
167 :
168 : #endif
|
