PhoenixGraph  01.0.0
Set of tools to simplify graph manipulation
Loading...
Searching...
No Matches
PNTreeLightNode_impl.h
Go to the documentation of this file.
1/***************************************
2 Auteur : Pierre Aubert
3 Mail : pierre.aubert@lapp.in2p3.fr
4 Licence : CeCILL-C
5****************************************/
6
7#ifndef __PNTREE_LIGHT_NODE_H_IMPL__
8#define __PNTREE_LIGHT_NODE_H_IMPL__
9
10#include <string.h>
11#include <math.h>
12
13#include "pstatic_computation.h"
14
15#include "PNTreeLightNode.h"
16
18template<typename T, typename U, unsigned char N>
22
24
26template<typename T, typename U, unsigned char N>
30
32template<typename T, typename U, unsigned char N>
36
38
41template<typename T, unsigned char N>
42void makeHalfSize(T childSize[N], const T parentSize[N]){
43 for(unsigned char i(0lu); i < N; ++i){
44 childSize[i] = parentSize[i]/2.f;
45 }
46}
47
49
53template<typename T, unsigned char N>
54bool checkSizeLimitLight(const T halfSizeChild[N], T sizeLimit){
55 for(unsigned char i(0); i < N; ++i){
56 if(halfSizeChild[i] < sizeLimit) return false;
57 }
58 return true;
59}
60
62
69template<typename T, typename U, unsigned char N>
70bool PNTreeLightNode<T, U, N>::addElement(T * posData, U * data, const T pos[N], const T size[N], T sizeLimit){
71 if(!checkSizeLimitLight<T, N>(size, sizeLimit)){
72 return false;
73 }
74 if(p_tableChildren == NULL){
75 if(p_data == NULL){ //The cell is empty
76 p_data = data;
77 p_posData = posData;
78 return true;
79 }else{ //There is a data in the cell
80 if(!split(pos, size, sizeLimit)) return false;
81 return addElement(posData, data, pos, size, sizeLimit);
82 }
83 }else{ //There are children
84 T childPos[N];
85 PNTreeLightNode<T, U, N> * child = getChildFromPos(childPos, posData, pos, size);
86 if(child == NULL){
87 return false;
88 }else{
89 T childSize[N];
90 makeHalfSize<T,N>(childSize, size);
91 return child->addElement(posData, data, childPos, childSize, sizeLimit);
92 }
93 }
94}
95
97
102template<typename T, typename U, unsigned char N>
103bool PNTreeLightNode<T, U, N>::saveGnuplotData(const std::string & fileName, T pos[N], T size[N]){
104 if(fileName == "") return false;
105 std::ofstream fs;
106 fs.open(fileName);
107 if(!fs.is_open()){return false;}
108 bool b = saveGnuplotData(fs, 0, pos, size);
109 fs.close();
110 return b;
111}
112
114
120template<typename T, typename U, unsigned char N>
121bool PNTreeLightNode<T, U, N>::saveGnuplotData(std::ofstream & fs, T height, T pos[N], T size[N]){
122 if(N == 2){
123 fs << pos[0] << "\t" << pos[1] << "\t" << height << std::endl;
124 fs << (pos[0] + size[0]) << "\t" << pos[1] << "\t" << height << std::endl;
125 fs << (pos[0] + size[0]) << "\t" << (pos[1] + size[1]) << "\t" << height << std::endl;
126 fs << pos[0] << "\t" << (pos[1] + size[1]) << "\t" << height << std::endl;
127 fs << pos[0] << "\t" << pos[1] << "\t" << height << std::endl;
128 }else if(N == 3){
129 T px0(pos[0]), px1(pos[0] + size[0]);
130 T py0(pos[1]), py1(pos[1] + size[1]);
131 T pz0(pos[2]), pz1(pos[2] + size[2]);
132
133 //lower quad
134 fs << px0 << "\t" << py0 << "\t" << pz0 << std::endl;
135 fs << px1 << "\t" << py0 << "\t" << pz0 << std::endl;
136 fs << px1 << "\t" << py1 << "\t" << pz0 << std::endl;
137 fs << px0 << "\t" << py1 << "\t" << pz0 << std::endl;
138 fs << px0 << "\t" << py0 << "\t" << pz0 << std::endl;
139 fs << std::endl;
140 //upper quad
141 fs << px0 << "\t" << py0 << "\t" << pz1 << std::endl;
142 fs << px1 << "\t" << py0 << "\t" << pz1 << std::endl;
143 fs << px1 << "\t" << py1 << "\t" << pz1 << std::endl;
144 fs << px0 << "\t" << py1 << "\t" << pz1 << std::endl;
145 fs << px0 << "\t" << py0 << "\t" << pz1 << std::endl;
146 fs << std::endl;
147 //Lines on Oz axis
148 fs << px0 << "\t" << py0 << "\t" << pz0 << std::endl;
149 fs << px0 << "\t" << py0 << "\t" << pz1 << std::endl;
150 fs << std::endl;
151 fs << px0 << "\t" << py1 << "\t" << pz0 << std::endl;
152 fs << px0 << "\t" << py1 << "\t" << pz1 << std::endl;
153 fs << std::endl;
154 fs << px1 << "\t" << py1 << "\t" << pz0 << std::endl;
155 fs << px1 << "\t" << py1 << "\t" << pz1 << std::endl;
156 fs << std::endl;
157 fs << px1 << "\t" << py0 << "\t" << pz0 << std::endl;
158 fs << px1 << "\t" << py0 << "\t" << pz1 << std::endl;
159 }
160 fs << std::endl;
161 if(p_tableChildren != NULL){
162 T childSize[N], posChild[N];
163 makeHalfSize<T,N>(childSize, size);
164 for(unsigned char i(0); i < PPower<2, N>::Value; ++i){
165 for(unsigned char k(0); k < N; ++k){
166 posChild[k] = pos[k] + ((i >> k) & 1)*childSize[k];
167 }
168 p_tableChildren[i].saveGnuplotData(fs, height + 1, posChild, childSize);
169 }
170 }
171 return true;
172}
173
175template<typename T, typename U, unsigned char N>
176void PNTreeLightNode<T, U, N>::clear(){
177 if(p_tableChildren != NULL){
178 for(unsigned char i(0); i < PPower<2, N>::Value; ++i){
179 PNTreeLightNode<T, U, N> * child = &(p_tableChildren[i]);
180 child->clear();
181 }
182 delete [] p_tableChildren;
183 p_tableChildren = NULL;
184 }
185 p_data = NULL;
186}
187
189
194template<typename T, typename U, unsigned char N>
195const U * PNTreeLightNode<T, U, N>::getLastData(const T * posData, const T pos[N], const T size[N]) const{
196 if(p_tableChildren == NULL){
197 if(p_data == NULL) return NULL;
198 else return p_data;
199 }else{
200 T childPos[N];
201 const PNTreeLightNode<T, U, N> * child = getChildFromPos(childPos, posData, pos, size);
202 if(child == NULL) return NULL;
203 else{
204 T childSize[N];
205 makeHalfSize<T,N>(childSize, size);
206 return child->getLastData(posData, pos, childSize);
207 }
208 }
209}
210
212
216template<typename T, unsigned char N>
217T getDistanceFromData(const T posA[N], const T posB[N]){
218 T res = 0.0, x;
219 for(unsigned char i(0); i < N; ++i){
220 x = posA[i] - posB[i];
221 res += x*x;
222 }
223 return sqrt(res);
224}
225
227
231template<unsigned char N>
232unsigned int getNeighbourCellIndex(unsigned char indexChild[N], unsigned char currentChildIndex[N]){
233 unsigned int index(0u), base(1u), tmp;
234 for(unsigned char i(N); i < N; ++i){
235 tmp = 0u;
236 if(indexChild[i] > currentChildIndex[i]){
237 tmp = 2u;
238 }else if(indexChild[i] == currentChildIndex[i]){
239 tmp = 1u;
240 }
241 index += base*tmp;
242 base *= 3u;
243 }
244 return index;
245}
246
248
257template<typename T, typename U, unsigned char N>
258bool PNTreeLightNode<T, U, N>::getCloserData(U*& closerData, T & distFromCloserData, bool * tabIsNeighbourChecked, unsigned int nbNeighbour,
259 const T * posData, const T pos[N], const T size[N]) const
260{
261 if(p_tableChildren == NULL){ //If the node has no child
262 if(p_data == NULL) return false; //If the node has no data
263 else{ //If the node has data
264 if(closerData == NULL){
265 closerData = p_data;
266 distFromCloserData = getDistanceFromData<T,N>(p_posData, posData);
267 return true;
268 }else{
269 T dist = getDistanceFromData<T,N>(p_posData, posData);
270 if(dist < distFromCloserData){
271 distFromCloserData = dist;
272 closerData = p_data;
273 }
274 return false;
275 }
276 }
277 }else{ //If the node has children
278 T childPos[N];
279 const PNTreeLightNode<T, U, N> * child = getChildFromPos(childPos, posData, pos, size);
280 if(child == NULL) return false;
281 else{
282 T childSize[N];
283 makeHalfSize<T,N>(childSize, size);
284 bool b = child->getCloserData(closerData, distFromCloserData, tabIsNeighbourChecked, nbNeighbour, posData, childPos, childSize);
285 if(b) return true;
286 else{
287 unsigned char indexChild[N], currentChildIndex[N];
288 T currentChildPos[N];
289 getIndexOfChildFromPos(indexChild, posData, pos, size);
290 unsigned char fullIndexChild(getFullIndexChild(indexChild));
291
292 for(unsigned char i(0); i < PPower<2, N>::Value; ++i){
293 if(i == fullIndexChild) continue;
294 for(unsigned char j(0); j < N; ++j){
295 currentChildIndex[j] = (i >> j) & 1;
296 currentChildPos[j] = pos[j] + ((T)currentChildIndex[j])*childSize[j];
297 }
298 unsigned int indexCurrentNeighbour(getNeighbourCellIndex<N>(indexChild, currentChildIndex));
299 //If the neighbours is already checked, skip it
300 if(tabIsNeighbourChecked[indexCurrentNeighbour]) continue;
301 //If the neighbours is not check yet, check it and write it in the tabIsNeighbourChecked
302 tabIsNeighbourChecked[indexCurrentNeighbour] = true;
303 if(child->getCloserData(closerData, distFromCloserData, tabIsNeighbourChecked, nbNeighbour,
304 posData, currentChildPos, childSize))
305 {
306 return true;
307 }
308 }
309 if(isNeighbourSearchFinised(tabIsNeighbourChecked, nbNeighbour)) return true;
310 return false;
311 }
312 }
313 }
314}
315
317
323template<typename T, typename U, unsigned char N>
324const PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getChildFromPos(T childPos[N], const T * posData, const T pos[N], const T size[N]) const{
325 if(p_tableChildren == NULL) return NULL;
326 unsigned char posChild(0), base(1);
327 bool cond;
328 for(unsigned char j(0); j < N; ++j){
329 cond = ((posData[j] - pos[j]) > size[j]*0.5);
330 childPos[j] = pos[j] + cond*size[j]*0.5;
331 posChild += cond*base;
332 base *= 2; //on poura faire du décalage de bit plus tard
333 }
334 if(posChild >= PPower<2, N>::Value) return NULL;
335 else return &(p_tableChildren[posChild]);
336}
337
339
345template<typename T, typename U, unsigned char N>
346PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getChildFromPos(T childPos[N], const T * posData, const T pos[N], const T size[N]){
347 if(p_tableChildren == NULL) return NULL;
348 unsigned char posChild(0), base(1);
349 bool cond;
350 for(unsigned char j(0); j < N; ++j){
351 cond = ((posData[j] - pos[j]) > size[j]*0.5);
352 childPos[j] = pos[j] + cond*size[j]*0.5;
353 posChild += cond*base;
354 base *= 2; //on poura faire du décalage de bit plus tard
355 }
356 if(posChild >= PPower<2, N>::Value) return NULL;
357 else{
358// std::cerr << "PNTreeLightNode<T, U, N>::getChildFromPos : posChild = " << ((int)posChild) << std::endl;
359 return &(p_tableChildren[posChild]);
360 }
361}
362
364
369template<typename T, typename U, unsigned char N>
370void PNTreeLightNode<T, U, N>::getIndexOfChildFromPos(unsigned char index[N], const T * posData, const T pos[N], const T size[N]) const{
371 if(p_tableChildren == NULL) return;
372 for(unsigned char j(0lu); j < N; ++j){
373 index[j] = ((posData[j] - pos[j]) > size[j]*0.5);
374 }
375}
376
378
383template<typename T, typename U, unsigned char N>
384void PNTreeLightNode<T, U, N>::getIndexOfChildFromPos(unsigned char index[N], T * posData, T pos[N], T size[N]){
385 if(p_tableChildren == NULL) return;
386 for(unsigned char j(0); j < N; ++j){
387 index[j] = ((posData[j] - pos[j]) > size[j]*0.5);
388 }
389}
390
392
395template<typename T, typename U, unsigned char N>
396unsigned char PNTreeLightNode<T, U, N>::getFullIndexChild(unsigned char index[N]) const{
397 unsigned char posChild(0), base(1);
398 for(unsigned char j(0); j < N; ++j){
399 posChild += (index[j])*base;
400 base *= 2; //on poura faire du décalage de bit plus tard
401 }
402 return posChild;
403}
404
406
408template<typename T, typename U, unsigned char N>
409const T * PNTreeLightNode<T, U, N>::getDataPos() const{return p_posData;}
410
412
414template<typename T, typename U, unsigned char N>
415T * PNTreeLightNode<T, U, N>::getDataPos(){return p_posData;}
416
418
420template<typename T, typename U, unsigned char N>
421const PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getTabChildren() const{return p_tableChildren;}
422
424
426template<typename T, typename U, unsigned char N>
427PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getTabChildren(){return p_tableChildren;}
428
430
433template<typename T, typename U, unsigned char N>
434const PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getChild(unsigned char childId) const{
435 if(p_tableChildren == NULL || childId >= PPower<2, N>::Value) return NULL;
436 return &(p_tableChildren[childId]);
437}
438
440
443template<typename T, typename U, unsigned char N>
444PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getChild(unsigned char childId){
445 if(p_tableChildren == NULL || childId >= PPower<2, N>::Value) return NULL;
446 return &(p_tableChildren[childId]);
447}
448
450
452template<typename T, typename U, unsigned char N>
456
458
463template<typename T, typename U, unsigned char N>
464bool PNTreeLightNode<T, U, N>::split(const T pos[N], const T size[N], T sizeLimit){
465 if(p_tableChildren != NULL || p_data == NULL){
466 std::cerr << "PNTreeLightNode<T, U, N>::split() : current node already split" << std::endl;
467 return false;
468 }
469// std::cerr << "PNTreeLightNode<T, U, N>::split() : begin" << std::endl;
470 T halfSizeChild[N];
471 makeHalfSize<T, N>(halfSizeChild, size);
472 if(!checkSizeLimitLight<T, N>(halfSizeChild, sizeLimit)){
473// std::cerr << "PNTreeLightNode<T, U, N>::split : can't split more, child sizes less than " << sizeLimit << std::endl;
474 return false;
475 }
476 unsigned char nbChildren(PPower<2, N>::Value);
477 p_tableChildren = new PNTreeLightNode<T, U, N>[nbChildren];
478 for(unsigned char i(0); i < nbChildren; ++i){
479 PNTreeLightNode<T, U, N> * child = &(p_tableChildren[i]);
480 child->p_tableChildren = NULL;
481 child->p_data = NULL;
482 child->p_posData = NULL;
483 }
484// std::cerr << "PNTreeLightNode<T, U, N>::split : replace child" << std::endl;
485 T childPos[N];
486 PNTreeLightNode<T, U, N> * child = getChildFromPos(childPos, p_posData, pos, size);
487 bool b = true;;
488 if(child == NULL) return false;
489 else{
490 b = child->addElement(p_posData, p_data, childPos, halfSizeChild, sizeLimit);
491 }
492 p_data = NULL;
493 p_posData = NULL;
494 return b;
495}
496
498template<typename T, typename U, unsigned char N>
504
505
506
507
508
509#endif
510
511
512
isNeighbourSearchFinised
bool isNeighbourSearchFinised(const bool *tabIsNeighbourChecked, unsigned int nbNeighbour)
Says is the neighbours search is finised.
Definition PNTreeLightNode.cpp:15
getNeighbourCellIndex
unsigned int getNeighbourCellIndex(unsigned char indexChild[N], unsigned char currentChildIndex[N])
Get the index of the check neighbours tab.
Definition PNTreeLightNode_impl.h:232
checkSizeLimitLight
bool checkSizeLimitLight(const T halfSizeChild[N], T sizeLimit)
Check the size of the childs of a N Tree.
Definition PNTreeLightNode_impl.h:54
makeHalfSize
void makeHalfSize(T childSize[N], const T parentSize[N])
Get the size of the child.
Definition PNTreeLightNode_impl.h:42
getDistanceFromData
T getDistanceFromData(const T posA[N], const T posB[N])
Get the distance between two points.
Definition PNTreeLightNode_impl.h:217
PNTreeLightNode::~PNTreeLightNode
virtual ~PNTreeLightNode()
Destructeur of PNTreeLightNode.
Definition PNTreeLightNode_impl.h:33
PNTreeLightNode::getIndexOfChildFromPos
void getIndexOfChildFromPos(unsigned char index[N], const T posData[N], const T pos[N], const T size[N]) const
PNTreeLightNode::copyPNTreeLightNode
void copyPNTreeLightNode(const PNTreeLightNode< T, U, N > &other)
Copy function of PNTreeLightNode.
Definition PNTreeLightNode_impl.h:453
PNTreeLightNode::p_tableChildren
PNTreeLightNode< T, U, N > * p_tableChildren
Position of the data in the hyper cube.
Definition PNTreeLightNode.h:68
PNTreeLightNode::getFullIndexChild
unsigned char getFullIndexChild(unsigned char index[N]) const
Get the full index position of a child.
Definition PNTreeLightNode_impl.h:396
PNTreeLightNode::PNTreeLightNode
PNTreeLightNode()
Default constructor of PNTreeLightNode.
Definition PNTreeLightNode_impl.h:19
PNTreeLightNode::getDataPos
const T * getDataPos() const
Returns the data position.
Definition PNTreeLightNode_impl.h:409
PNTreeLightNode::getChild
const PNTreeLightNode< T, U, N > * getChild(unsigned char childId) const
Returns the child of the PNTreeLightNode.
Definition PNTreeLightNode_impl.h:434
PNTreeLightNode::addElement
bool addElement(T *posData, U *data, const T pos[N], const T size[N], const T sizeLimit)
Add an element in the PNTreeLightNode.
Definition PNTreeLightNode_impl.h:70
PNTreeLightNode::split
bool split(const T pos[N], const T size[N], T sizeLimit)
Split the PNTreeLightNode.
Definition PNTreeLightNode_impl.h:464
PNTreeLightNode::initialisationPNTreeLightNode
void initialisationPNTreeLightNode()
Initialisation function of the class PNTreeLightNode.
Definition PNTreeLightNode_impl.h:499
PNTreeLightNode::clear
void clear()
Clear the PNTreeLightNode content.
Definition PNTreeLightNode_impl.h:176
PNTreeLightNode::getCloserData
bool getCloserData(U *&closerData, T &distFromCloserData, bool *tabIsNeighbourChecked, unsigned int nbNeighbour, const T *posData, const T pos[N], const T size[N]) const
Get the closer data from the given position posData.
Definition PNTreeLightNode_impl.h:258
PNTreeLightNode::getTabChildren
const PNTreeLightNode< T, U, N > * getTabChildren() const
Returns the table of children of the PNTreeLightNode.
Definition PNTreeLightNode_impl.h:421
PNTreeLightNode::p_data
U * p_data
Data of the node.
Definition PNTreeLightNode.h:66
PNTreeLightNode::saveGnuplotData
bool saveGnuplotData(const std::string &fileName, T pos[N], T size[N])
Saves the PNTreeLightNode into a txt file for gnuplot.
Definition PNTreeLightNode_impl.h:103
PNTreeLightNode::getLastData
const U * getLastData(const T *posData, const T pos[N], const T size[N]) const
Get the data of the last node in the N tree.
Definition PNTreeLightNode_impl.h:195
PNTreeLightNode::p_posData
T * p_posData
Position of the data in the cell.
Definition PNTreeLightNode.h:64
PNTreeLightNode::getChildFromPos
const PNTreeLightNode< T, U, N > * getChildFromPos(T childPos[N], const T *posData, const T pos[N], const T size[N]) const
Get the child of the PNTreeLightNode with a position.
Definition PNTreeLightNode_impl.h:324
pstatic_computation.h