Merge lp:~cern-kicad/kicad/bugfix_1249736 into lp:kicad/product
- bugfix_1249736
- Merge into product
Proposed by
Maciej Suminski
Status: | Merged | ||||
---|---|---|---|---|---|
Merged at revision: | 4543 | ||||
Proposed branch: | lp:~cern-kicad/kicad/bugfix_1249736 | ||||
Merge into: | lp:kicad/product | ||||
Diff against target: |
2027 lines (+44/-1791) 4 files modified
common/view/view.cpp (+22/-8) include/geometry/rtree.h (+21/-23) include/rtree.h (+0/-1758) include/view/view_rtree.h (+1/-2) |
||||
To merge this branch: | bzr merge lp:~cern-kicad/kicad/bugfix_1249736 | ||||
Related bugs: |
|
Reviewer | Review Type | Date Requested | Status |
---|---|---|---|
Wayne Stambaugh | Pending | ||
Review via email: mp+197858@code.launchpad.net |
Commit message
Description of the change
Fixes https:/
Removes duplicated rtree.h.
To post a comment you must log in.
Revision history for this message
Wayne Stambaugh (stambaughw) wrote : | # |
Revision history for this message
Maciej Suminski (orsonmmz) wrote : | # |
Hi Wayne,
Yes, it is ready. The main point is to remove duplicate code and fix one corner case.
Regards,
Orson
Revision history for this message
Wayne Stambaugh (stambaughw) wrote : | # |
On 12/10/2013 8:36 AM, Maciej Sumiński wrote:
> Hi Wayne,
>
> Yes, it is ready. The main point is to remove duplicate code and fix one corner case.
>
> Regards,
> Orson
>
Committed in testing branch r4543.
Preview Diff
[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1 | === modified file 'common/view/view.cpp' |
2 | --- common/view/view.cpp 2013-11-27 08:46:59 +0000 |
3 | +++ common/view/view.cpp 2013-12-05 12:52:21 +0000 |
4 | @@ -153,10 +153,12 @@ |
5 | { |
6 | } |
7 | |
8 | - void operator()( VIEW_ITEM* aItem ) |
9 | + bool operator()( VIEW_ITEM* aItem ) |
10 | { |
11 | if( aItem->ViewIsVisible() ) |
12 | m_cont.push_back( VIEW::LAYER_ITEM_PAIR( aItem, m_layer ) ); |
13 | + |
14 | + return true; |
15 | } |
16 | |
17 | Container& m_cont; |
18 | @@ -387,7 +389,7 @@ |
19 | { |
20 | } |
21 | |
22 | - void operator()( VIEW_ITEM* aItem ) |
23 | + bool operator()( VIEW_ITEM* aItem ) |
24 | { |
25 | // Obtain the color that should be used for coloring the item |
26 | const COLOR4D color = painter->GetSettings()->GetColor( aItem, layer ); |
27 | @@ -395,6 +397,8 @@ |
28 | |
29 | if( group >= 0 ) |
30 | gal->ChangeGroupColor( group, color ); |
31 | + |
32 | + return true; |
33 | } |
34 | |
35 | int layer; |
36 | @@ -447,12 +451,14 @@ |
37 | { |
38 | } |
39 | |
40 | - void operator()( VIEW_ITEM* aItem ) |
41 | + bool operator()( VIEW_ITEM* aItem ) |
42 | { |
43 | int group = aItem->getGroup( layer ); |
44 | |
45 | if( group >= 0 ) |
46 | gal->ChangeGroupDepth( group, depth ); |
47 | + |
48 | + return true; |
49 | } |
50 | |
51 | int layer, depth; |
52 | @@ -571,15 +577,17 @@ |
53 | { |
54 | } |
55 | |
56 | - void operator()( VIEW_ITEM* aItem ) |
57 | + bool operator()( VIEW_ITEM* aItem ) |
58 | { |
59 | // Conditions that have te be fulfilled for an item to be drawn |
60 | bool drawCondition = aItem->ViewIsVisible() && |
61 | aItem->ViewGetLOD( currentLayer->id ) < view->m_scale; |
62 | if( !drawCondition ) |
63 | - return; |
64 | + return true; |
65 | |
66 | view->draw( aItem, currentLayer->id ); |
67 | + |
68 | + return true; |
69 | } |
70 | |
71 | const VIEW_LAYER* currentLayer; |
72 | @@ -676,9 +684,11 @@ |
73 | |
74 | struct VIEW::unlinkItem |
75 | { |
76 | - void operator()( VIEW_ITEM* aItem ) |
77 | + bool operator()( VIEW_ITEM* aItem ) |
78 | { |
79 | aItem->m_view = NULL; |
80 | + |
81 | + return true; |
82 | } |
83 | }; |
84 | |
85 | @@ -690,7 +700,7 @@ |
86 | { |
87 | } |
88 | |
89 | - void operator()( VIEW_ITEM* aItem ) |
90 | + bool operator()( VIEW_ITEM* aItem ) |
91 | { |
92 | // Remove previously cached group |
93 | int prevGroup = aItem->getGroup( layer ); |
94 | @@ -712,6 +722,8 @@ |
95 | { |
96 | aItem->setGroup( layer, -1 ); |
97 | } |
98 | + |
99 | + return true; |
100 | } |
101 | |
102 | VIEW* view; |
103 | @@ -792,12 +804,14 @@ |
104 | { |
105 | } |
106 | |
107 | - void operator()( VIEW_ITEM* aItem ) |
108 | + bool operator()( VIEW_ITEM* aItem ) |
109 | { |
110 | if( aItem->storesGroups() ) |
111 | { |
112 | aItem->deleteGroups(); |
113 | } |
114 | + |
115 | + return true; |
116 | } |
117 | |
118 | VIEW* view; |
119 | |
120 | === modified file 'include/geometry/rtree.h' |
121 | --- include/geometry/rtree.h 2013-10-14 14:13:35 +0000 |
122 | +++ include/geometry/rtree.h 2013-12-05 12:52:21 +0000 |
123 | @@ -163,7 +163,7 @@ |
124 | |
125 | /// Calculate Statistics |
126 | |
127 | - Statistics CalcStats( ); |
128 | + Statistics CalcStats(); |
129 | |
130 | /// Remove all entries from tree |
131 | void RemoveAll(); |
132 | @@ -396,7 +396,7 @@ |
133 | bool IsInternalNode() { return m_level > 0; } // Not a leaf, but a internal node |
134 | bool IsLeaf() { return m_level == 0; } // A leaf, contains data |
135 | |
136 | - int m_count; ///< Count |
137 | + int m_count; ///< Count |
138 | int m_level; ///< Leaf is zero, others positive |
139 | Branch m_branch[MAXNODES]; ///< Branch |
140 | }; |
141 | @@ -830,18 +830,18 @@ |
142 | bool RTREE_QUAL::Load( RTFileStream& a_stream ) |
143 | { |
144 | // Write some kind of header |
145 | - int _dataFileId = ('R' << 0) | ('T' << 8) | ('R' << 16) | ('E' << 24); |
146 | - int _dataSize = sizeof(DATATYPE); |
147 | - int _dataNumDims = NUMDIMS; |
148 | - int _dataElemSize = sizeof(ELEMTYPE); |
149 | + int _dataFileId = ('R' << 0) | ('T' << 8) | ('R' << 16) | ('E' << 24); |
150 | + int _dataSize = sizeof(DATATYPE); |
151 | + int _dataNumDims = NUMDIMS; |
152 | + int _dataElemSize = sizeof(ELEMTYPE); |
153 | int _dataElemRealSize = sizeof(ELEMTYPEREAL); |
154 | int _dataMaxNodes = TMAXNODES; |
155 | int _dataMinNodes = TMINNODES; |
156 | |
157 | - int dataFileId = 0; |
158 | - int dataSize = 0; |
159 | - int dataNumDims = 0; |
160 | - int dataElemSize = 0; |
161 | + int dataFileId = 0; |
162 | + int dataSize = 0; |
163 | + int dataNumDims = 0; |
164 | + int dataElemSize = 0; |
165 | int dataElemRealSize = 0; |
166 | int dataMaxNodes = 0; |
167 | int dataMinNodes = 0; |
168 | @@ -932,10 +932,10 @@ |
169 | bool RTREE_QUAL::Save( RTFileStream& a_stream ) |
170 | { |
171 | // Write some kind of header |
172 | - int dataFileId = ('R' << 0) | ('T' << 8) | ('R' << 16) | ('E' << 24); |
173 | - int dataSize = sizeof(DATATYPE); |
174 | - int dataNumDims = NUMDIMS; |
175 | - int dataElemSize = sizeof(ELEMTYPE); |
176 | + int dataFileId = ('R' << 0) | ('T' << 8) | ('R' << 16) | ('E' << 24); |
177 | + int dataSize = sizeof(DATATYPE); |
178 | + int dataNumDims = NUMDIMS; |
179 | + int dataElemSize = sizeof(ELEMTYPE); |
180 | int dataElemRealSize = sizeof(ELEMTYPEREAL); |
181 | int dataMaxNodes = TMAXNODES; |
182 | int dataMinNodes = TMINNODES; |
183 | @@ -1286,27 +1286,27 @@ |
184 | ELEMTYPEREAL increase; |
185 | ELEMTYPEREAL bestIncr = (ELEMTYPEREAL) -1; |
186 | ELEMTYPEREAL area; |
187 | - ELEMTYPEREAL bestArea; |
188 | + ELEMTYPEREAL bestArea = 0; |
189 | int best = 0; |
190 | Rect tempRect; |
191 | |
192 | for( int index = 0; index < a_node->m_count; ++index ) |
193 | { |
194 | Rect* curRect = &a_node->m_branch[index].m_rect; |
195 | - area = CalcRectVolume( curRect ); |
196 | + area = CalcRectVolume( curRect ); |
197 | tempRect = CombineRect( a_rect, curRect ); |
198 | increase = CalcRectVolume( &tempRect ) - area; |
199 | |
200 | if( (increase < bestIncr) || firstTime ) |
201 | { |
202 | - best = index; |
203 | + best = index; |
204 | bestArea = area; |
205 | bestIncr = increase; |
206 | firstTime = false; |
207 | } |
208 | else if( (increase == bestIncr) && (area < bestArea) ) |
209 | { |
210 | - best = index; |
211 | + best = index; |
212 | bestArea = area; |
213 | bestIncr = increase; |
214 | } |
215 | @@ -1594,8 +1594,8 @@ |
216 | |
217 | for( int index = 0; index < a_maxRects; ++index ) |
218 | { |
219 | - a_parVars->m_taken[index] = false; |
220 | - a_parVars->m_partition[index] = -1; |
221 | + a_parVars->m_taken[index] = false; |
222 | + a_parVars->m_partition[index] = -1; |
223 | } |
224 | } |
225 | |
226 | @@ -1622,7 +1622,7 @@ |
227 | &a_parVars->m_branchBuf[indexB].m_rect ); |
228 | waste = CalcRectVolume( &oneRect ) - area[indexA] - area[indexB]; |
229 | |
230 | - if( waste > worst ) |
231 | + if( waste >= worst ) |
232 | { |
233 | worst = waste; |
234 | seed0 = indexA; |
235 | @@ -1856,8 +1856,6 @@ |
236 | } |
237 | |
238 | |
239 | - |
240 | - |
241 | //calculate the minimum distance between a point and a rectangle as defined by Manolopoulos et al. |
242 | //it uses the square distance to avoid the use of ELEMTYPEREAL values, which are slower. |
243 | RTREE_TEMPLATE |
244 | |
245 | === removed file 'include/rtree.h' |
246 | --- include/rtree.h 2013-11-14 18:00:57 +0000 |
247 | +++ include/rtree.h 1970-01-01 00:00:00 +0000 |
248 | @@ -1,1758 +0,0 @@ |
249 | -/* |
250 | - * R-Tree index |
251 | - * |
252 | - * from http://www.superliminal.com/ |
253 | - * |
254 | - * LICENSE : Entirely free for all uses. Enjoy! |
255 | - * |
256 | - * AUTORS |
257 | - * - 1983 Original algorithm and test code by Antonin Guttman and Michael Stonebraker, UC Berkely |
258 | - * - 1994 ANCI C ported from original test code by Melinda Green - melinda@superliminal.com |
259 | - * - 1995 Sphere volume fix for degeneracy problem submitted by Paul Brook |
260 | - * - 2004 Templated C++ port by Greg Douglas |
261 | - * - 2008 Portability issues fixed by Maxence Laurent |
262 | - */ |
263 | - |
264 | -#ifndef RTREE_H |
265 | -#define RTREE_H |
266 | - |
267 | -// NOTE This file compiles under MSVC 6 SP5 and MSVC .Net 2003 it may not work on other compilers without modification. |
268 | - |
269 | -// NOTE These next few lines may be win32 specific, you may need to modify them to compile on other platform |
270 | -#include <stdio.h> |
271 | -#include <math.h> |
272 | -#include <assert.h> |
273 | -#include <stdlib.h> |
274 | - |
275 | -#define ASSERT assert // RTree uses ASSERT( condition ) |
276 | -#ifndef Min |
277 | - #define Min std::min |
278 | -#endif // Min |
279 | -#ifndef Max |
280 | - #define Max std::max |
281 | -#endif // Max |
282 | - |
283 | -// |
284 | -// RTree.h |
285 | -// |
286 | - |
287 | -#define RTREE_TEMPLATE template <class DATATYPE, class ELEMTYPE, int NUMDIMS, \ |
288 | - class ELEMTYPEREAL, int TMAXNODES, int TMINNODES> |
289 | -#define RTREE_SEARCH_TEMPLATE template <class DATATYPE, class ELEMTYPE, int NUMDIMS, \ |
290 | - class ELEMTYPEREAL, int TMAXNODES, int TMINNODES, class VISITOR> |
291 | -#define RTREE_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, \ |
292 | - TMINNODES> |
293 | -#define RTREE_SEARCH_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, \ |
294 | - TMINNODES, VISITOR> |
295 | - |
296 | -#define RTREE_DONT_USE_MEMPOOLS // This version does not contain a fixed memory allocator, fill in lines with EXAMPLE to implement one. |
297 | -#define RTREE_USE_SPHERICAL_VOLUME // Better split classification, may be slower on some systems |
298 | - |
299 | -// Fwd decl |
300 | -class RTFileStream; // File I/O helper class, look below for implementation and notes. |
301 | - |
302 | - |
303 | -/// \class RTree |
304 | -/// Implementation of RTree, a multidimensional bounding rectangle tree. |
305 | -/// Example usage: For a 3-dimensional tree use RTree<Object*, float, 3> myTree; |
306 | -/// |
307 | -/// This modified, templated C++ version by Greg Douglas at Auran (http://www.auran.com) |
308 | -/// |
309 | -/// DATATYPE Referenced data, should be int, void*, obj* etc. no larger than sizeof<void*> and simple type |
310 | -/// ELEMTYPE Type of element such as int or float |
311 | -/// NUMDIMS Number of dimensions such as 2 or 3 |
312 | -/// ELEMTYPEREAL Type of element that allows fractional and large values such as float or double, for use in volume calcs |
313 | -/// |
314 | -/// NOTES: Inserting and removing data requires the knowledge of its constant Minimal Bounding Rectangle. |
315 | -/// This version uses new/delete for nodes, I recommend using a fixed size allocator for efficiency. |
316 | -/// Instead of using a callback function for returned results, I recommend and efficient pre-sized, grow-only memory |
317 | -/// array similar to MFC CArray or STL Vector for returning search query result. |
318 | -/// |
319 | -template <class DATATYPE, class ELEMTYPE, int NUMDIMS, |
320 | - class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2> |
321 | -class RTree |
322 | -{ |
323 | -protected: |
324 | - |
325 | - struct Node; // Fwd decl. Used by other internal structs and iterator |
326 | -public: |
327 | - |
328 | - // These constant must be declared after Branch and before Node struct |
329 | - // Stuck up here for MSVC 6 compiler. NSVC .NET 2003 is much happier. |
330 | - enum { |
331 | - MAXNODES = TMAXNODES, ///< Max elements in node |
332 | - MINNODES = TMINNODES, ///< Min elements in node |
333 | - }; |
334 | -public: |
335 | - |
336 | - RTree(); |
337 | - virtual ~RTree(); |
338 | - |
339 | - /// Insert entry |
340 | - /// \param a_min Min of bounding rect |
341 | - /// \param a_max Max of bounding rect |
342 | - /// \param a_dataId Positive Id of data. Maybe zero, but negative numbers not allowed. |
343 | - void Insert( const ELEMTYPE a_min[NUMDIMS], |
344 | - const ELEMTYPE a_max[NUMDIMS], |
345 | - const DATATYPE& a_dataId ); |
346 | - |
347 | - /// Remove entry |
348 | - /// \param a_min Min of bounding rect |
349 | - /// \param a_max Max of bounding rect |
350 | - /// \param a_dataId Positive Id of data. Maybe zero, but negative numbers not allowed. |
351 | - void Remove( const ELEMTYPE a_min[NUMDIMS], |
352 | - const ELEMTYPE a_max[NUMDIMS], |
353 | - const DATATYPE& a_dataId ); |
354 | - |
355 | - /// Find all within search rectangle |
356 | - /// \param a_min Min of search bounding rect |
357 | - /// \param a_max Max of search bounding rect |
358 | - /// \param a_searchResult Search result array. Caller should set grow size. Function will reset, not append to array. |
359 | - /// \param a_resultCallback Callback function to return result. Callback should return 'true' to continue searching |
360 | - /// \param a_context User context to pass as parameter to a_resultCallback |
361 | - /// \return Returns the number of entries found |
362 | - int Search( const ELEMTYPE a_min[NUMDIMS], |
363 | - const ELEMTYPE a_max[NUMDIMS], |
364 | - bool a_resultCallback( DATATYPE a_data, void* a_context ), |
365 | - void* a_context ); |
366 | - |
367 | - template <class VISITOR> |
368 | - int Search( const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], VISITOR& a_visitor ) |
369 | - { |
370 | - #ifdef _DEBUG |
371 | - |
372 | - for( int index = 0; index<NUMDIMS; ++index ) |
373 | - { |
374 | - ASSERT( a_min[index] <= a_max[index] ); |
375 | - } |
376 | - |
377 | - #endif // _DEBUG |
378 | - |
379 | - Rect rect; |
380 | - |
381 | - for( int axis = 0; axis<NUMDIMS; ++axis ) |
382 | - { |
383 | - rect.m_min[axis] = a_min[axis]; |
384 | - rect.m_max[axis] = a_max[axis]; |
385 | - } |
386 | - |
387 | - |
388 | - // NOTE: May want to return search result another way, perhaps returning the number of found elements here. |
389 | - |
390 | - Search( m_root, &rect, a_visitor ); |
391 | - |
392 | - return 0; |
393 | - } |
394 | - |
395 | - /// Remove all entries from tree |
396 | - void RemoveAll(); |
397 | - |
398 | - /// Count the data elements in this container. This is slow as no internal counter is maintained. |
399 | - int Count(); |
400 | - |
401 | - /// Load tree contents from file |
402 | - bool Load( const char* a_fileName ); |
403 | - |
404 | - /// Load tree contents from stream |
405 | - bool Load( RTFileStream& a_stream ); |
406 | - |
407 | - |
408 | - /// Save tree contents to file |
409 | - bool Save( const char* a_fileName ); |
410 | - |
411 | - /// Save tree contents to stream |
412 | - bool Save( RTFileStream& a_stream ); |
413 | - |
414 | - /// Iterator is not remove safe. |
415 | - class Iterator |
416 | - { |
417 | -private: |
418 | - |
419 | - enum { MAX_STACK = 32 }; // Max stack size. Allows almost n^32 where n is number of branches in node |
420 | - |
421 | - struct StackElement |
422 | - { |
423 | - Node* m_node; |
424 | - int m_branchIndex; |
425 | - }; |
426 | -public: |
427 | - |
428 | - Iterator() { Init(); } |
429 | - |
430 | - ~Iterator() { } |
431 | - |
432 | - /// Is iterator invalid |
433 | - bool IsNull() { return m_tos <= 0; } |
434 | - |
435 | - /// Is iterator pointing to valid data |
436 | - bool IsNotNull() { return m_tos > 0; } |
437 | - |
438 | - /// Access the current data element. Caller must be sure iterator is not NULL first. |
439 | - DATATYPE& operator*() |
440 | - { |
441 | - ASSERT( IsNotNull() ); |
442 | - StackElement& curTos = m_stack[m_tos - 1]; |
443 | - return curTos.m_node->m_branch[curTos.m_branchIndex].m_data; |
444 | - } |
445 | - |
446 | - /// Access the current data element. Caller must be sure iterator is not NULL first. |
447 | - const DATATYPE& operator*() const |
448 | - { |
449 | - ASSERT( IsNotNull() ); |
450 | - StackElement& curTos = m_stack[m_tos - 1]; |
451 | - return curTos.m_node->m_branch[curTos.m_branchIndex].m_data; |
452 | - } |
453 | - |
454 | - /// Find the next data element |
455 | - bool operator++() { return FindNextData(); } |
456 | - |
457 | - /// Get the bounds for this node |
458 | - void GetBounds( ELEMTYPE a_min[NUMDIMS], ELEMTYPE a_max[NUMDIMS] ) |
459 | - { |
460 | - ASSERT( IsNotNull() ); |
461 | - StackElement& curTos = m_stack[m_tos - 1]; |
462 | - Branch& curBranch = curTos.m_node->m_branch[curTos.m_branchIndex]; |
463 | - |
464 | - for( int index = 0; index < NUMDIMS; ++index ) |
465 | - { |
466 | - a_min[index] = curBranch.m_rect.m_min[index]; |
467 | - a_max[index] = curBranch.m_rect.m_max[index]; |
468 | - } |
469 | - } |
470 | - |
471 | -private: |
472 | - |
473 | - /// Reset iterator |
474 | - void Init() { m_tos = 0; } |
475 | - |
476 | - /// Find the next data element in the tree (For internal use only) |
477 | - bool FindNextData() |
478 | - { |
479 | - for( ; ; ) |
480 | - { |
481 | - if( m_tos <= 0 ) |
482 | - { |
483 | - return false; |
484 | - } |
485 | - |
486 | - StackElement curTos = Pop(); // Copy stack top cause it may change as we use it |
487 | - |
488 | - if( curTos.m_node->IsLeaf() ) |
489 | - { |
490 | - // Keep walking through data while we can |
491 | - if( curTos.m_branchIndex + 1 < curTos.m_node->m_count ) |
492 | - { |
493 | - // There is more data, just point to the next one |
494 | - Push( curTos.m_node, curTos.m_branchIndex + 1 ); |
495 | - return true; |
496 | - } |
497 | - |
498 | - // No more data, so it will fall back to previous level |
499 | - } |
500 | - else |
501 | - { |
502 | - if( curTos.m_branchIndex + 1 < curTos.m_node->m_count ) |
503 | - { |
504 | - // Push sibling on for future tree walk |
505 | - // This is the 'fall back' node when we finish with the current level |
506 | - Push( curTos.m_node, curTos.m_branchIndex + 1 ); |
507 | - } |
508 | - |
509 | - // Since cur node is not a leaf, push first of next level to get deeper into the tree |
510 | - Node* nextLevelnode = curTos.m_node->m_branch[curTos.m_branchIndex].m_child; |
511 | - Push( nextLevelnode, 0 ); |
512 | - |
513 | - // If we pushed on a new leaf, exit as the data is ready at TOS |
514 | - if( nextLevelnode->IsLeaf() ) |
515 | - { |
516 | - return true; |
517 | - } |
518 | - } |
519 | - } |
520 | - } |
521 | - |
522 | - /// Push node and branch onto iteration stack (For internal use only) |
523 | - void Push( Node* a_node, int a_branchIndex ) |
524 | - { |
525 | - m_stack[m_tos].m_node = a_node; |
526 | - m_stack[m_tos].m_branchIndex = a_branchIndex; |
527 | - ++m_tos; |
528 | - ASSERT( m_tos <= MAX_STACK ); |
529 | - } |
530 | - |
531 | - /// Pop element off iteration stack (For internal use only) |
532 | - StackElement& Pop() |
533 | - { |
534 | - ASSERT( m_tos > 0 ); |
535 | - --m_tos; |
536 | - return m_stack[m_tos]; |
537 | - } |
538 | - |
539 | - StackElement m_stack[MAX_STACK]; ///< Stack as we are doing iteration instead of recursion |
540 | - int m_tos; ///< Top Of Stack index |
541 | - |
542 | - friend class RTree; // Allow hiding of non-public functions while allowing manipulation by logical owner |
543 | - }; |
544 | - |
545 | - |
546 | - /// Get 'first' for iteration |
547 | - void GetFirst( Iterator& a_it ) |
548 | - { |
549 | - a_it.Init(); |
550 | - Node* first = m_root; |
551 | - |
552 | - while( first ) |
553 | - { |
554 | - if( first->IsInternalNode() && first->m_count > 1 ) |
555 | - { |
556 | - a_it.Push( first, 1 ); // Descend sibling branch later |
557 | - } |
558 | - else if( first->IsLeaf() ) |
559 | - { |
560 | - if( first->m_count ) |
561 | - { |
562 | - a_it.Push( first, 0 ); |
563 | - } |
564 | - |
565 | - break; |
566 | - } |
567 | - |
568 | - first = first->m_branch[0].m_child; |
569 | - } |
570 | - } |
571 | - |
572 | - /// Get Next for iteration |
573 | - void GetNext( Iterator& a_it ) { ++a_it; } |
574 | - |
575 | - /// Is iterator NULL, or at end? |
576 | - bool IsNull( Iterator& a_it ) { return a_it.IsNull(); } |
577 | - |
578 | - /// Get object at iterator position |
579 | - DATATYPE& GetAt( Iterator& a_it ) { return *a_it; } |
580 | -protected: |
581 | - |
582 | - /// Minimal bounding rectangle (n-dimensional) |
583 | - struct Rect |
584 | - { |
585 | - ELEMTYPE m_min[NUMDIMS]; ///< Min dimensions of bounding box |
586 | - ELEMTYPE m_max[NUMDIMS]; ///< Max dimensions of bounding box |
587 | - }; |
588 | - |
589 | - /// May be data or may be another subtree |
590 | - /// The parents level determines this. |
591 | - /// If the parents level is 0, then this is data |
592 | - struct Branch |
593 | - { |
594 | - Rect m_rect; ///< Bounds |
595 | - union |
596 | - { |
597 | - Node* m_child; ///< Child node |
598 | - DATATYPE m_data; ///< Data Id or Ptr |
599 | - }; |
600 | - }; |
601 | - |
602 | - /// Node for each branch level |
603 | - struct Node |
604 | - { |
605 | - bool IsInternalNode() { return m_level > 0; } // Not a leaf, but a internal node |
606 | - bool IsLeaf() { return m_level == 0; } // A leaf, contains data |
607 | - |
608 | - int m_count; ///< Count |
609 | - int m_level; ///< Leaf is zero, others positive |
610 | - Branch m_branch[MAXNODES]; ///< Branch |
611 | - }; |
612 | - |
613 | - /// A link list of nodes for reinsertion after a delete operation |
614 | - struct ListNode |
615 | - { |
616 | - ListNode* m_next; ///< Next in list |
617 | - Node* m_node; ///< Node |
618 | - }; |
619 | - |
620 | - /// Variables for finding a split partition |
621 | - struct PartitionVars |
622 | - { |
623 | - int m_partition[MAXNODES + 1]; |
624 | - int m_total; |
625 | - int m_minFill; |
626 | - int m_taken[MAXNODES + 1]; |
627 | - int m_count[2]; |
628 | - Rect m_cover[2]; |
629 | - ELEMTYPEREAL m_area[2]; |
630 | - |
631 | - Branch m_branchBuf[MAXNODES + 1]; |
632 | - int m_branchCount; |
633 | - Rect m_coverSplit; |
634 | - ELEMTYPEREAL m_coverSplitArea; |
635 | - }; |
636 | - |
637 | - Node* AllocNode(); |
638 | - void FreeNode( Node* a_node ); |
639 | - void InitNode( Node* a_node ); |
640 | - void InitRect( Rect* a_rect ); |
641 | - bool InsertRectRec( Rect* a_rect, |
642 | - const DATATYPE& a_id, |
643 | - Node* a_node, |
644 | - Node** a_newNode, |
645 | - int a_level ); |
646 | - bool InsertRect( Rect* a_rect, const DATATYPE& a_id, Node** a_root, int a_level ); |
647 | - Rect NodeCover( Node* a_node ); |
648 | - bool AddBranch( Branch* a_branch, Node* a_node, Node** a_newNode ); |
649 | - void DisconnectBranch( Node* a_node, int a_index ); |
650 | - int PickBranch( Rect* a_rect, Node* a_node ); |
651 | - Rect CombineRect( Rect* a_rectA, Rect* a_rectB ); |
652 | - void SplitNode( Node* a_node, Branch* a_branch, Node** a_newNode ); |
653 | - ELEMTYPEREAL RectSphericalVolume( Rect* a_rect ); |
654 | - ELEMTYPEREAL RectVolume( Rect* a_rect ); |
655 | - ELEMTYPEREAL CalcRectVolume( Rect* a_rect ); |
656 | - void GetBranches( Node* a_node, Branch* a_branch, PartitionVars* a_parVars ); |
657 | - void ChoosePartition( PartitionVars* a_parVars, int a_minFill ); |
658 | - void LoadNodes( Node* a_nodeA, Node* a_nodeB, PartitionVars* a_parVars ); |
659 | - void InitParVars( PartitionVars* a_parVars, int a_maxRects, int a_minFill ); |
660 | - void PickSeeds( PartitionVars* a_parVars ); |
661 | - void Classify( int a_index, int a_group, PartitionVars* a_parVars ); |
662 | - bool RemoveRect( Rect* a_rect, const DATATYPE& a_id, Node** a_root ); |
663 | - bool RemoveRectRec( Rect* a_rect, |
664 | - const DATATYPE& a_id, |
665 | - Node* a_node, |
666 | - ListNode** a_listNode ); |
667 | - ListNode* AllocListNode(); |
668 | - void FreeListNode( ListNode* a_listNode ); |
669 | - bool Overlap( Rect* a_rectA, Rect* a_rectB ); |
670 | - void ReInsert( Node* a_node, ListNode** a_listNode ); |
671 | - |
672 | - bool Search( Node * a_node, Rect * a_rect, int& a_foundCount, bool a_resultCallback( |
673 | - DATATYPE a_data, |
674 | - void* a_context ), void* a_context ); |
675 | - |
676 | - template <class VISITOR> |
677 | - bool Search( Node* a_node, Rect* a_rect, VISITOR& a_visitor ) |
678 | - { |
679 | - ASSERT( a_node ); |
680 | - ASSERT( a_node->m_level >= 0 ); |
681 | - ASSERT( a_rect ); |
682 | - |
683 | - if( a_node->IsInternalNode() ) // This is an internal node in the tree |
684 | - { |
685 | - for( int index = 0; index < a_node->m_count; ++index ) |
686 | - { |
687 | - if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) ) |
688 | - { |
689 | - if( !Search( a_node->m_branch[index].m_child, a_rect, a_visitor ) ) |
690 | - { |
691 | - return false; // Don't continue searching |
692 | - } |
693 | - } |
694 | - } |
695 | - } |
696 | - else // This is a leaf node |
697 | - { |
698 | - for( int index = 0; index < a_node->m_count; ++index ) |
699 | - { |
700 | - if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) ) |
701 | - { |
702 | - DATATYPE& id = a_node->m_branch[index].m_data; |
703 | - |
704 | - a_visitor( id ); |
705 | - } |
706 | - } |
707 | - } |
708 | - |
709 | - return true; // Continue searching |
710 | - } |
711 | - |
712 | - void RemoveAllRec( Node* a_node ); |
713 | - void Reset(); |
714 | - void CountRec( Node* a_node, int& a_count ); |
715 | - |
716 | - bool SaveRec( Node* a_node, RTFileStream& a_stream ); |
717 | - bool LoadRec( Node* a_node, RTFileStream& a_stream ); |
718 | - |
719 | - Node* m_root; ///< Root of tree |
720 | - ELEMTYPEREAL m_unitSphereVolume; ///< Unit sphere constant for required number of dimensions |
721 | -}; |
722 | - |
723 | - |
724 | -// Because there is not stream support, this is a quick and dirty file I/O helper. |
725 | -// Users will likely replace its usage with a Stream implementation from their favorite API. |
726 | -class RTFileStream |
727 | -{ |
728 | - FILE* m_file; |
729 | -public: |
730 | - |
731 | - |
732 | - RTFileStream() |
733 | - { |
734 | - m_file = NULL; |
735 | - } |
736 | - |
737 | - ~RTFileStream() |
738 | - { |
739 | - Close(); |
740 | - } |
741 | - |
742 | - bool OpenRead( const char* a_fileName ) |
743 | - { |
744 | - m_file = fopen( a_fileName, "rb" ); |
745 | - |
746 | - if( !m_file ) |
747 | - { |
748 | - return false; |
749 | - } |
750 | - |
751 | - return true; |
752 | - } |
753 | - |
754 | - bool OpenWrite( const char* a_fileName ) |
755 | - { |
756 | - m_file = fopen( a_fileName, "wb" ); |
757 | - |
758 | - if( !m_file ) |
759 | - { |
760 | - return false; |
761 | - } |
762 | - |
763 | - return true; |
764 | - } |
765 | - |
766 | - void Close() |
767 | - { |
768 | - if( m_file ) |
769 | - { |
770 | - fclose( m_file ); |
771 | - m_file = NULL; |
772 | - } |
773 | - } |
774 | - |
775 | - template <typename TYPE> |
776 | - size_t Write( const TYPE& a_value ) |
777 | - { |
778 | - ASSERT( m_file ); |
779 | - return fwrite( (void*) &a_value, sizeof(a_value), 1, m_file ); |
780 | - } |
781 | - |
782 | - template <typename TYPE> |
783 | - size_t WriteArray( const TYPE* a_array, int a_count ) |
784 | - { |
785 | - ASSERT( m_file ); |
786 | - return fwrite( (void*) a_array, sizeof(TYPE) * a_count, 1, m_file ); |
787 | - } |
788 | - |
789 | - template <typename TYPE> |
790 | - size_t Read( TYPE& a_value ) |
791 | - { |
792 | - ASSERT( m_file ); |
793 | - return fread( (void*) &a_value, sizeof(a_value), 1, m_file ); |
794 | - } |
795 | - |
796 | - template <typename TYPE> |
797 | - size_t ReadArray( TYPE* a_array, int a_count ) |
798 | - { |
799 | - ASSERT( m_file ); |
800 | - return fread( (void*) a_array, sizeof(TYPE) * a_count, 1, m_file ); |
801 | - } |
802 | -}; |
803 | - |
804 | - |
805 | -RTREE_TEMPLATE RTREE_QUAL::RTree() |
806 | -{ |
807 | - ASSERT( MAXNODES > MINNODES ); |
808 | - ASSERT( MINNODES > 0 ); |
809 | - |
810 | - |
811 | - // We only support machine word size simple data type eg. integer index or object pointer. |
812 | - // Since we are storing as union with non data branch |
813 | - ASSERT( sizeof(DATATYPE) == sizeof(void*) || sizeof(DATATYPE) == sizeof(int) ); |
814 | - |
815 | - // Precomputed volumes of the unit spheres for the first few dimensions |
816 | - const float UNIT_SPHERE_VOLUMES[] = |
817 | - { |
818 | - 0.000000f, 2.000000f, 3.141593f, // Dimension 0,1,2 |
819 | - 4.188790f, 4.934802f, 5.263789f, // Dimension 3,4,5 |
820 | - 5.167713f, 4.724766f, 4.058712f, // Dimension 6,7,8 |
821 | - 3.298509f, 2.550164f, 1.884104f, // Dimension 9,10,11 |
822 | - 1.335263f, 0.910629f, 0.599265f, // Dimension 12,13,14 |
823 | - 0.381443f, 0.235331f, 0.140981f, // Dimension 15,16,17 |
824 | - 0.082146f, 0.046622f, 0.025807f, // Dimension 18,19,20 |
825 | - }; |
826 | - |
827 | - m_root = AllocNode(); |
828 | - m_root->m_level = 0; |
829 | - m_unitSphereVolume = (ELEMTYPEREAL) UNIT_SPHERE_VOLUMES[NUMDIMS]; |
830 | -} |
831 | - |
832 | - |
833 | -RTREE_TEMPLATE |
834 | -RTREE_QUAL::~RTree() { |
835 | - Reset(); // Free, or reset node memory |
836 | -} |
837 | - |
838 | - |
839 | -RTREE_TEMPLATE |
840 | -void RTREE_QUAL::Insert( const ELEMTYPE a_min[NUMDIMS], |
841 | - const ELEMTYPE a_max[NUMDIMS], |
842 | - const DATATYPE& a_dataId ) |
843 | -{ |
844 | -#ifdef _DEBUG |
845 | - |
846 | - for( int index = 0; index<NUMDIMS; ++index ) |
847 | - { |
848 | - ASSERT( a_min[index] <= a_max[index] ); |
849 | - } |
850 | - |
851 | -#endif // _DEBUG |
852 | - |
853 | - Rect rect; |
854 | - |
855 | - for( int axis = 0; axis<NUMDIMS; ++axis ) |
856 | - { |
857 | - rect.m_min[axis] = a_min[axis]; |
858 | - rect.m_max[axis] = a_max[axis]; |
859 | - } |
860 | - |
861 | - InsertRect( &rect, a_dataId, &m_root, 0 ); |
862 | -} |
863 | - |
864 | - |
865 | -RTREE_TEMPLATE |
866 | -void RTREE_QUAL::Remove( const ELEMTYPE a_min[NUMDIMS], |
867 | - const ELEMTYPE a_max[NUMDIMS], |
868 | - const DATATYPE& a_dataId ) |
869 | -{ |
870 | -#ifdef _DEBUG |
871 | - |
872 | - for( int index = 0; index<NUMDIMS; ++index ) |
873 | - { |
874 | - ASSERT( a_min[index] <= a_max[index] ); |
875 | - } |
876 | - |
877 | -#endif // _DEBUG |
878 | - |
879 | - Rect rect; |
880 | - |
881 | - for( int axis = 0; axis<NUMDIMS; ++axis ) |
882 | - { |
883 | - rect.m_min[axis] = a_min[axis]; |
884 | - rect.m_max[axis] = a_max[axis]; |
885 | - } |
886 | - |
887 | - RemoveRect( &rect, a_dataId, &m_root ); |
888 | -} |
889 | - |
890 | - |
891 | -RTREE_TEMPLATE |
892 | -int RTREE_QUAL::Search( const ELEMTYPE a_min[NUMDIMS], |
893 | - const ELEMTYPE a_max[NUMDIMS], |
894 | - bool a_resultCallback( DATATYPE a_data, void* a_context ), |
895 | - void* a_context ) |
896 | -{ |
897 | -#ifdef _DEBUG |
898 | - |
899 | - for( int index = 0; index<NUMDIMS; ++index ) |
900 | - { |
901 | - ASSERT( a_min[index] <= a_max[index] ); |
902 | - } |
903 | - |
904 | -#endif // _DEBUG |
905 | - |
906 | - Rect rect; |
907 | - |
908 | - for( int axis = 0; axis<NUMDIMS; ++axis ) |
909 | - { |
910 | - rect.m_min[axis] = a_min[axis]; |
911 | - rect.m_max[axis] = a_max[axis]; |
912 | - } |
913 | - |
914 | - // NOTE: May want to return search result another way, perhaps returning the number of found elements here. |
915 | - |
916 | - int foundCount = 0; |
917 | - Search( m_root, &rect, foundCount, a_resultCallback, a_context ); |
918 | - |
919 | - return foundCount; |
920 | -} |
921 | - |
922 | - |
923 | -RTREE_TEMPLATE |
924 | -int RTREE_QUAL::Count() |
925 | -{ |
926 | - int count = 0; |
927 | - |
928 | - CountRec( m_root, count ); |
929 | - |
930 | - return count; |
931 | -} |
932 | - |
933 | - |
934 | -RTREE_TEMPLATE |
935 | -void RTREE_QUAL::CountRec( Node* a_node, int& a_count ) |
936 | -{ |
937 | - if( a_node->IsInternalNode() ) // not a leaf node |
938 | - { |
939 | - for( int index = 0; index < a_node->m_count; ++index ) |
940 | - { |
941 | - CountRec( a_node->m_branch[index].m_child, a_count ); |
942 | - } |
943 | - } |
944 | - else // A leaf node |
945 | - { |
946 | - a_count += a_node->m_count; |
947 | - } |
948 | -} |
949 | - |
950 | - |
951 | -RTREE_TEMPLATE |
952 | -bool RTREE_QUAL::Load( const char* a_fileName ) |
953 | -{ |
954 | - RemoveAll(); // Clear existing tree |
955 | - |
956 | - RTFileStream stream; |
957 | - |
958 | - if( !stream.OpenRead( a_fileName ) ) |
959 | - { |
960 | - return false; |
961 | - } |
962 | - |
963 | - bool result = Load( stream ); |
964 | - |
965 | - stream.Close(); |
966 | - |
967 | - return result; |
968 | -}; |
969 | - |
970 | - |
971 | -RTREE_TEMPLATE |
972 | -bool RTREE_QUAL::Load( RTFileStream& a_stream ) |
973 | -{ |
974 | - // Write some kind of header |
975 | - int _dataFileId = ('R' << 0) | ('T' << 8) | ('R' << 16) | ('E' << 24); |
976 | - int _dataSize = sizeof(DATATYPE); |
977 | - int _dataNumDims = NUMDIMS; |
978 | - int _dataElemSize = sizeof(ELEMTYPE); |
979 | - int _dataElemRealSize = sizeof(ELEMTYPEREAL); |
980 | - int _dataMaxNodes = TMAXNODES; |
981 | - int _dataMinNodes = TMINNODES; |
982 | - |
983 | - int dataFileId = 0; |
984 | - int dataSize = 0; |
985 | - int dataNumDims = 0; |
986 | - int dataElemSize = 0; |
987 | - int dataElemRealSize = 0; |
988 | - int dataMaxNodes = 0; |
989 | - int dataMinNodes = 0; |
990 | - |
991 | - a_stream.Read( dataFileId ); |
992 | - a_stream.Read( dataSize ); |
993 | - a_stream.Read( dataNumDims ); |
994 | - a_stream.Read( dataElemSize ); |
995 | - a_stream.Read( dataElemRealSize ); |
996 | - a_stream.Read( dataMaxNodes ); |
997 | - a_stream.Read( dataMinNodes ); |
998 | - |
999 | - bool result = false; |
1000 | - |
1001 | - // Test if header was valid and compatible |
1002 | - if( (dataFileId == _dataFileId) |
1003 | - && (dataSize == _dataSize) |
1004 | - && (dataNumDims == _dataNumDims) |
1005 | - && (dataElemSize == _dataElemSize) |
1006 | - && (dataElemRealSize == _dataElemRealSize) |
1007 | - && (dataMaxNodes == _dataMaxNodes) |
1008 | - && (dataMinNodes == _dataMinNodes) |
1009 | - ) |
1010 | - { |
1011 | - // Recursively load tree |
1012 | - result = LoadRec( m_root, a_stream ); |
1013 | - } |
1014 | - |
1015 | - return result; |
1016 | -} |
1017 | - |
1018 | - |
1019 | -RTREE_TEMPLATE |
1020 | -bool RTREE_QUAL::LoadRec( Node* a_node, RTFileStream& a_stream ) |
1021 | -{ |
1022 | - a_stream.Read( a_node->m_level ); |
1023 | - a_stream.Read( a_node->m_count ); |
1024 | - |
1025 | - if( a_node->IsInternalNode() ) // not a leaf node |
1026 | - { |
1027 | - for( int index = 0; index < a_node->m_count; ++index ) |
1028 | - { |
1029 | - Branch* curBranch = &a_node->m_branch[index]; |
1030 | - |
1031 | - a_stream.ReadArray( curBranch->m_rect.m_min, NUMDIMS ); |
1032 | - a_stream.ReadArray( curBranch->m_rect.m_max, NUMDIMS ); |
1033 | - |
1034 | - curBranch->m_child = AllocNode(); |
1035 | - LoadRec( curBranch->m_child, a_stream ); |
1036 | - } |
1037 | - } |
1038 | - else // A leaf node |
1039 | - { |
1040 | - for( int index = 0; index < a_node->m_count; ++index ) |
1041 | - { |
1042 | - Branch* curBranch = &a_node->m_branch[index]; |
1043 | - |
1044 | - a_stream.ReadArray( curBranch->m_rect.m_min, NUMDIMS ); |
1045 | - a_stream.ReadArray( curBranch->m_rect.m_max, NUMDIMS ); |
1046 | - |
1047 | - a_stream.Read( curBranch->m_data ); |
1048 | - } |
1049 | - } |
1050 | - |
1051 | - return true; // Should do more error checking on I/O operations |
1052 | -} |
1053 | - |
1054 | - |
1055 | -RTREE_TEMPLATE |
1056 | -bool RTREE_QUAL::Save( const char* a_fileName ) |
1057 | -{ |
1058 | - RTFileStream stream; |
1059 | - |
1060 | - if( !stream.OpenWrite( a_fileName ) ) |
1061 | - { |
1062 | - return false; |
1063 | - } |
1064 | - |
1065 | - bool result = Save( stream ); |
1066 | - |
1067 | - stream.Close(); |
1068 | - |
1069 | - return result; |
1070 | -} |
1071 | - |
1072 | - |
1073 | -RTREE_TEMPLATE |
1074 | -bool RTREE_QUAL::Save( RTFileStream& a_stream ) |
1075 | -{ |
1076 | - // Write some kind of header |
1077 | - int dataFileId = ('R' << 0) | ('T' << 8) | ('R' << 16) | ('E' << 24); |
1078 | - int dataSize = sizeof(DATATYPE); |
1079 | - int dataNumDims = NUMDIMS; |
1080 | - int dataElemSize = sizeof(ELEMTYPE); |
1081 | - int dataElemRealSize = sizeof(ELEMTYPEREAL); |
1082 | - int dataMaxNodes = TMAXNODES; |
1083 | - int dataMinNodes = TMINNODES; |
1084 | - |
1085 | - a_stream.Write( dataFileId ); |
1086 | - a_stream.Write( dataSize ); |
1087 | - a_stream.Write( dataNumDims ); |
1088 | - a_stream.Write( dataElemSize ); |
1089 | - a_stream.Write( dataElemRealSize ); |
1090 | - a_stream.Write( dataMaxNodes ); |
1091 | - a_stream.Write( dataMinNodes ); |
1092 | - |
1093 | - // Recursively save tree |
1094 | - bool result = SaveRec( m_root, a_stream ); |
1095 | - |
1096 | - return result; |
1097 | -} |
1098 | - |
1099 | - |
1100 | -RTREE_TEMPLATE |
1101 | -bool RTREE_QUAL::SaveRec( Node* a_node, RTFileStream& a_stream ) |
1102 | -{ |
1103 | - a_stream.Write( a_node->m_level ); |
1104 | - a_stream.Write( a_node->m_count ); |
1105 | - |
1106 | - if( a_node->IsInternalNode() ) // not a leaf node |
1107 | - { |
1108 | - for( int index = 0; index < a_node->m_count; ++index ) |
1109 | - { |
1110 | - Branch* curBranch = &a_node->m_branch[index]; |
1111 | - |
1112 | - a_stream.WriteArray( curBranch->m_rect.m_min, NUMDIMS ); |
1113 | - a_stream.WriteArray( curBranch->m_rect.m_max, NUMDIMS ); |
1114 | - |
1115 | - SaveRec( curBranch->m_child, a_stream ); |
1116 | - } |
1117 | - } |
1118 | - else // A leaf node |
1119 | - { |
1120 | - for( int index = 0; index < a_node->m_count; ++index ) |
1121 | - { |
1122 | - Branch* curBranch = &a_node->m_branch[index]; |
1123 | - |
1124 | - a_stream.WriteArray( curBranch->m_rect.m_min, NUMDIMS ); |
1125 | - a_stream.WriteArray( curBranch->m_rect.m_max, NUMDIMS ); |
1126 | - |
1127 | - a_stream.Write( curBranch->m_data ); |
1128 | - } |
1129 | - } |
1130 | - |
1131 | - return true; // Should do more error checking on I/O operations |
1132 | -} |
1133 | - |
1134 | - |
1135 | -RTREE_TEMPLATE |
1136 | -void RTREE_QUAL::RemoveAll() |
1137 | -{ |
1138 | - // Delete all existing nodes |
1139 | - Reset(); |
1140 | - |
1141 | - m_root = AllocNode(); |
1142 | - m_root->m_level = 0; |
1143 | -} |
1144 | - |
1145 | - |
1146 | -RTREE_TEMPLATE |
1147 | -void RTREE_QUAL::Reset() |
1148 | -{ |
1149 | -#ifdef RTREE_DONT_USE_MEMPOOLS |
1150 | - // Delete all existing nodes |
1151 | - RemoveAllRec( m_root ); |
1152 | -#else // RTREE_DONT_USE_MEMPOOLS |
1153 | - // Just reset memory pools. We are not using complex types |
1154 | - // EXAMPLE |
1155 | -#endif // RTREE_DONT_USE_MEMPOOLS |
1156 | -} |
1157 | - |
1158 | - |
1159 | -RTREE_TEMPLATE |
1160 | -void RTREE_QUAL::RemoveAllRec( Node* a_node ) |
1161 | -{ |
1162 | - ASSERT( a_node ); |
1163 | - ASSERT( a_node->m_level >= 0 ); |
1164 | - |
1165 | - if( a_node->IsInternalNode() ) // This is an internal node in the tree |
1166 | - { |
1167 | - for( int index = 0; index < a_node->m_count; ++index ) |
1168 | - { |
1169 | - RemoveAllRec( a_node->m_branch[index].m_child ); |
1170 | - } |
1171 | - } |
1172 | - |
1173 | - FreeNode( a_node ); |
1174 | -} |
1175 | - |
1176 | - |
1177 | -RTREE_TEMPLATE |
1178 | -typename RTREE_QUAL::Node* RTREE_QUAL::AllocNode() |
1179 | -{ |
1180 | - Node* newNode; |
1181 | - |
1182 | -#ifdef RTREE_DONT_USE_MEMPOOLS |
1183 | - newNode = new Node; |
1184 | -#else // RTREE_DONT_USE_MEMPOOLS |
1185 | - // EXAMPLE |
1186 | -#endif // RTREE_DONT_USE_MEMPOOLS |
1187 | - InitNode( newNode ); |
1188 | - return newNode; |
1189 | -} |
1190 | - |
1191 | - |
1192 | -RTREE_TEMPLATE |
1193 | -void RTREE_QUAL::FreeNode( Node* a_node ) |
1194 | -{ |
1195 | - ASSERT( a_node ); |
1196 | - |
1197 | -#ifdef RTREE_DONT_USE_MEMPOOLS |
1198 | - delete a_node; |
1199 | -#else // RTREE_DONT_USE_MEMPOOLS |
1200 | - // EXAMPLE |
1201 | -#endif // RTREE_DONT_USE_MEMPOOLS |
1202 | -} |
1203 | - |
1204 | - |
1205 | -// Allocate space for a node in the list used in DeletRect to |
1206 | -// store Nodes that are too empty. |
1207 | -RTREE_TEMPLATE |
1208 | -typename RTREE_QUAL::ListNode* RTREE_QUAL::AllocListNode() |
1209 | -{ |
1210 | -#ifdef RTREE_DONT_USE_MEMPOOLS |
1211 | - return new ListNode; |
1212 | -#else // RTREE_DONT_USE_MEMPOOLS |
1213 | - // EXAMPLE |
1214 | -#endif // RTREE_DONT_USE_MEMPOOLS |
1215 | -} |
1216 | - |
1217 | - |
1218 | -RTREE_TEMPLATE |
1219 | -void RTREE_QUAL::FreeListNode( ListNode* a_listNode ) |
1220 | -{ |
1221 | -#ifdef RTREE_DONT_USE_MEMPOOLS |
1222 | - delete a_listNode; |
1223 | -#else // RTREE_DONT_USE_MEMPOOLS |
1224 | - // EXAMPLE |
1225 | -#endif // RTREE_DONT_USE_MEMPOOLS |
1226 | -} |
1227 | - |
1228 | - |
1229 | -RTREE_TEMPLATE |
1230 | -void RTREE_QUAL::InitNode( Node* a_node ) |
1231 | -{ |
1232 | - a_node->m_count = 0; |
1233 | - a_node->m_level = -1; |
1234 | -} |
1235 | - |
1236 | - |
1237 | -RTREE_TEMPLATE |
1238 | -void RTREE_QUAL::InitRect( Rect* a_rect ) |
1239 | -{ |
1240 | - for( int index = 0; index < NUMDIMS; ++index ) |
1241 | - { |
1242 | - a_rect->m_min[index] = (ELEMTYPE) 0; |
1243 | - a_rect->m_max[index] = (ELEMTYPE) 0; |
1244 | - } |
1245 | -} |
1246 | - |
1247 | - |
1248 | -// Inserts a new data rectangle into the index structure. |
1249 | -// Recursively descends tree, propagates splits back up. |
1250 | -// Returns 0 if node was not split. Old node updated. |
1251 | -// If node was split, returns 1 and sets the pointer pointed to by |
1252 | -// new_node to point to the new node. Old node updated to become one of two. |
1253 | -// The level argument specifies the number of steps up from the leaf |
1254 | -// level to insert; e.g. a data rectangle goes in at level = 0. |
1255 | -RTREE_TEMPLATE |
1256 | -bool RTREE_QUAL::InsertRectRec( Rect* a_rect, |
1257 | - const DATATYPE& a_id, |
1258 | - Node* a_node, |
1259 | - Node** a_newNode, |
1260 | - int a_level ) |
1261 | -{ |
1262 | - ASSERT( a_rect && a_node && a_newNode ); |
1263 | - ASSERT( a_level >= 0 && a_level <= a_node->m_level ); |
1264 | - |
1265 | - int index; |
1266 | - Branch branch; |
1267 | - Node* otherNode; |
1268 | - |
1269 | - // Still above level for insertion, go down tree recursively |
1270 | - if( a_node->m_level > a_level ) |
1271 | - { |
1272 | - index = PickBranch( a_rect, a_node ); |
1273 | - |
1274 | - if( !InsertRectRec( a_rect, a_id, a_node->m_branch[index].m_child, &otherNode, a_level ) ) |
1275 | - { |
1276 | - // Child was not split |
1277 | - a_node->m_branch[index].m_rect = |
1278 | - CombineRect( a_rect, &(a_node->m_branch[index].m_rect) ); |
1279 | - return false; |
1280 | - } |
1281 | - else // Child was split |
1282 | - { |
1283 | - a_node->m_branch[index].m_rect = NodeCover( a_node->m_branch[index].m_child ); |
1284 | - branch.m_child = otherNode; |
1285 | - branch.m_rect = NodeCover( otherNode ); |
1286 | - return AddBranch( &branch, a_node, a_newNode ); |
1287 | - } |
1288 | - } |
1289 | - else if( a_node->m_level == a_level ) // Have reached level for insertion. Add rect, split if necessary |
1290 | - { |
1291 | - branch.m_rect = *a_rect; |
1292 | - branch.m_child = (Node*) a_id; |
1293 | - // Child field of leaves contains id of data record |
1294 | - return AddBranch( &branch, a_node, a_newNode ); |
1295 | - } |
1296 | - else |
1297 | - { |
1298 | - // Should never occur |
1299 | - ASSERT( 0 ); |
1300 | - return false; |
1301 | - } |
1302 | -} |
1303 | - |
1304 | - |
1305 | -// Insert a data rectangle into an index structure. |
1306 | -// InsertRect provides for splitting the root; |
1307 | -// returns 1 if root was split, 0 if it was not. |
1308 | -// The level argument specifies the number of steps up from the leaf |
1309 | -// level to insert; e.g. a data rectangle goes in at level = 0. |
1310 | -// InsertRect2 does the recursion. |
1311 | -// |
1312 | -RTREE_TEMPLATE |
1313 | -bool RTREE_QUAL::InsertRect( Rect* a_rect, const DATATYPE& a_id, Node** a_root, int a_level ) |
1314 | -{ |
1315 | - ASSERT( a_rect && a_root ); |
1316 | - ASSERT( a_level >= 0 && a_level <= (*a_root)->m_level ); |
1317 | -#ifdef _DEBUG |
1318 | - |
1319 | - for( int index = 0; index < NUMDIMS; ++index ) |
1320 | - { |
1321 | - ASSERT( a_rect->m_min[index] <= a_rect->m_max[index] ); |
1322 | - } |
1323 | - |
1324 | -#endif // _DEBUG |
1325 | - |
1326 | - Node* newRoot; |
1327 | - Node* newNode; |
1328 | - Branch branch; |
1329 | - |
1330 | - if( InsertRectRec( a_rect, a_id, *a_root, &newNode, a_level ) ) // Root split |
1331 | - { |
1332 | - newRoot = AllocNode(); // Grow tree taller and new root |
1333 | - newRoot->m_level = (*a_root)->m_level + 1; |
1334 | - branch.m_rect = NodeCover( *a_root ); |
1335 | - branch.m_child = *a_root; |
1336 | - AddBranch( &branch, newRoot, NULL ); |
1337 | - branch.m_rect = NodeCover( newNode ); |
1338 | - branch.m_child = newNode; |
1339 | - AddBranch( &branch, newRoot, NULL ); |
1340 | - *a_root = newRoot; |
1341 | - return true; |
1342 | - } |
1343 | - |
1344 | - return false; |
1345 | -} |
1346 | - |
1347 | - |
1348 | -// Find the smallest rectangle that includes all rectangles in branches of a node. |
1349 | -RTREE_TEMPLATE |
1350 | -typename RTREE_QUAL::Rect RTREE_QUAL::NodeCover( Node* a_node ) |
1351 | -{ |
1352 | - ASSERT( a_node ); |
1353 | - |
1354 | - int firstTime = true; |
1355 | - Rect rect; |
1356 | - InitRect( &rect ); |
1357 | - |
1358 | - for( int index = 0; index < a_node->m_count; ++index ) |
1359 | - { |
1360 | - if( firstTime ) |
1361 | - { |
1362 | - rect = a_node->m_branch[index].m_rect; |
1363 | - firstTime = false; |
1364 | - } |
1365 | - else |
1366 | - { |
1367 | - rect = CombineRect( &rect, &(a_node->m_branch[index].m_rect) ); |
1368 | - } |
1369 | - } |
1370 | - |
1371 | - return rect; |
1372 | -} |
1373 | - |
1374 | - |
1375 | -// Add a branch to a node. Split the node if necessary. |
1376 | -// Returns 0 if node not split. Old node updated. |
1377 | -// Returns 1 if node split, sets *new_node to address of new node. |
1378 | -// Old node updated, becomes one of two. |
1379 | -RTREE_TEMPLATE |
1380 | -bool RTREE_QUAL::AddBranch( Branch* a_branch, Node* a_node, Node** a_newNode ) |
1381 | -{ |
1382 | - ASSERT( a_branch ); |
1383 | - ASSERT( a_node ); |
1384 | - |
1385 | - if( a_node->m_count < MAXNODES ) // Split won't be necessary |
1386 | - { |
1387 | - a_node->m_branch[a_node->m_count] = *a_branch; |
1388 | - ++a_node->m_count; |
1389 | - |
1390 | - return false; |
1391 | - } |
1392 | - else |
1393 | - { |
1394 | - ASSERT( a_newNode ); |
1395 | - |
1396 | - SplitNode( a_node, a_branch, a_newNode ); |
1397 | - return true; |
1398 | - } |
1399 | -} |
1400 | - |
1401 | - |
1402 | -// Disconnect a dependent node. |
1403 | -// Caller must return (or stop using iteration index) after this as count has changed |
1404 | -RTREE_TEMPLATE |
1405 | -void RTREE_QUAL::DisconnectBranch( Node* a_node, int a_index ) |
1406 | -{ |
1407 | - ASSERT( a_node && (a_index >= 0) && (a_index < MAXNODES) ); |
1408 | - ASSERT( a_node->m_count > 0 ); |
1409 | - |
1410 | - // Remove element by swapping with the last element to prevent gaps in array |
1411 | - a_node->m_branch[a_index] = a_node->m_branch[a_node->m_count - 1]; |
1412 | - |
1413 | - --a_node->m_count; |
1414 | -} |
1415 | - |
1416 | - |
1417 | -// Pick a branch. Pick the one that will need the smallest increase |
1418 | -// in area to accomodate the new rectangle. This will result in the |
1419 | -// least total area for the covering rectangles in the current node. |
1420 | -// In case of a tie, pick the one which was smaller before, to get |
1421 | -// the best resolution when searching. |
1422 | -RTREE_TEMPLATE |
1423 | -int RTREE_QUAL::PickBranch( Rect* a_rect, Node* a_node ) |
1424 | -{ |
1425 | - ASSERT( a_rect && a_node ); |
1426 | - |
1427 | - bool firstTime = true; |
1428 | - ELEMTYPEREAL increase; |
1429 | - ELEMTYPEREAL bestIncr = (ELEMTYPEREAL) -1; |
1430 | - ELEMTYPEREAL area; |
1431 | - ELEMTYPEREAL bestArea; |
1432 | - int best = 0; // avoid compil complaint about uninitialized |
1433 | - Rect tempRect; |
1434 | - |
1435 | - for( int index = 0; index < a_node->m_count; ++index ) |
1436 | - { |
1437 | - Rect* curRect = &a_node->m_branch[index].m_rect; |
1438 | - area = CalcRectVolume( curRect ); |
1439 | - tempRect = CombineRect( a_rect, curRect ); |
1440 | - increase = CalcRectVolume( &tempRect ) - area; |
1441 | - |
1442 | - if( (increase < bestIncr) || firstTime ) |
1443 | - { |
1444 | - best = index; |
1445 | - bestArea = area; |
1446 | - bestIncr = increase; |
1447 | - firstTime = false; |
1448 | - } |
1449 | - else if( (increase == bestIncr) && (area < bestArea) ) |
1450 | - { |
1451 | - best = index; |
1452 | - bestArea = area; |
1453 | - bestIncr = increase; |
1454 | - } |
1455 | - } |
1456 | - |
1457 | - return best; |
1458 | -} |
1459 | - |
1460 | - |
1461 | -// Combine two rectangles into larger one containing both |
1462 | -RTREE_TEMPLATE |
1463 | -typename RTREE_QUAL::Rect RTREE_QUAL::CombineRect( Rect* a_rectA, Rect* a_rectB ) |
1464 | -{ |
1465 | - ASSERT( a_rectA && a_rectB ); |
1466 | - |
1467 | - Rect newRect; |
1468 | - |
1469 | - for( int index = 0; index < NUMDIMS; ++index ) |
1470 | - { |
1471 | - newRect.m_min[index] = Min( a_rectA->m_min[index], a_rectB->m_min[index] ); |
1472 | - newRect.m_max[index] = Max( a_rectA->m_max[index], a_rectB->m_max[index] ); |
1473 | - } |
1474 | - |
1475 | - return newRect; |
1476 | -} |
1477 | - |
1478 | - |
1479 | -// Split a node. |
1480 | -// Divides the nodes branches and the extra one between two nodes. |
1481 | -// Old node is one of the new ones, and one really new one is created. |
1482 | -// Tries more than one method for choosing a partition, uses best result. |
1483 | -RTREE_TEMPLATE |
1484 | -void RTREE_QUAL::SplitNode( Node* a_node, Branch* a_branch, Node** a_newNode ) |
1485 | -{ |
1486 | - ASSERT( a_node ); |
1487 | - ASSERT( a_branch ); |
1488 | - |
1489 | - // Could just use local here, but member or external is faster since it is reused |
1490 | - PartitionVars localVars; |
1491 | - PartitionVars* parVars = &localVars; |
1492 | - int level; |
1493 | - |
1494 | - // Load all the branches into a buffer, initialize old node |
1495 | - level = a_node->m_level; |
1496 | - GetBranches( a_node, a_branch, parVars ); |
1497 | - |
1498 | - // Find partition |
1499 | - ChoosePartition( parVars, MINNODES ); |
1500 | - |
1501 | - // Put branches from buffer into 2 nodes according to chosen partition |
1502 | - *a_newNode = AllocNode(); |
1503 | - (*a_newNode)->m_level = a_node->m_level = level; |
1504 | - LoadNodes( a_node, *a_newNode, parVars ); |
1505 | - |
1506 | - ASSERT( (a_node->m_count + (*a_newNode)->m_count) == parVars->m_total ); |
1507 | -} |
1508 | - |
1509 | - |
1510 | -// Calculate the n-dimensional volume of a rectangle |
1511 | -RTREE_TEMPLATE |
1512 | -ELEMTYPEREAL RTREE_QUAL::RectVolume( Rect* a_rect ) |
1513 | -{ |
1514 | - ASSERT( a_rect ); |
1515 | - |
1516 | - ELEMTYPEREAL volume = (ELEMTYPEREAL) 1; |
1517 | - |
1518 | - for( int index = 0; index<NUMDIMS; ++index ) |
1519 | - { |
1520 | - volume *= a_rect->m_max[index] - a_rect->m_min[index]; |
1521 | - } |
1522 | - |
1523 | - ASSERT( volume >= (ELEMTYPEREAL) 0 ); |
1524 | - |
1525 | - return volume; |
1526 | -} |
1527 | - |
1528 | - |
1529 | -// The exact volume of the bounding sphere for the given Rect |
1530 | -RTREE_TEMPLATE |
1531 | -ELEMTYPEREAL RTREE_QUAL::RectSphericalVolume( Rect* a_rect ) |
1532 | -{ |
1533 | - ASSERT( a_rect ); |
1534 | - |
1535 | - ELEMTYPEREAL sumOfSquares = (ELEMTYPEREAL) 0; |
1536 | - ELEMTYPEREAL radius; |
1537 | - |
1538 | - for( int index = 0; index < NUMDIMS; ++index ) |
1539 | - { |
1540 | - ELEMTYPEREAL halfExtent = |
1541 | - ( (ELEMTYPEREAL) a_rect->m_max[index] - (ELEMTYPEREAL) a_rect->m_min[index] ) * 0.5f; |
1542 | - sumOfSquares += halfExtent * halfExtent; |
1543 | - } |
1544 | - |
1545 | - radius = (ELEMTYPEREAL) sqrt( sumOfSquares ); |
1546 | - |
1547 | - // Pow maybe slow, so test for common dims like 2,3 and just use x*x, x*x*x. |
1548 | - if( NUMDIMS == 3 ) |
1549 | - { |
1550 | - return radius * radius * radius * m_unitSphereVolume; |
1551 | - } |
1552 | - else if( NUMDIMS == 2 ) |
1553 | - { |
1554 | - return radius * radius * m_unitSphereVolume; |
1555 | - } |
1556 | - else |
1557 | - { |
1558 | - return (ELEMTYPEREAL) (pow( radius, NUMDIMS ) * m_unitSphereVolume); |
1559 | - } |
1560 | -} |
1561 | - |
1562 | - |
1563 | -// Use one of the methods to calculate retangle volume |
1564 | -RTREE_TEMPLATE |
1565 | -ELEMTYPEREAL RTREE_QUAL::CalcRectVolume( Rect* a_rect ) |
1566 | -{ |
1567 | -#ifdef RTREE_USE_SPHERICAL_VOLUME |
1568 | - return RectSphericalVolume( a_rect ); // Slower but helps certain merge cases |
1569 | -#else // RTREE_USE_SPHERICAL_VOLUME |
1570 | - return RectVolume( a_rect ); // Faster but can cause poor merges |
1571 | -#endif // RTREE_USE_SPHERICAL_VOLUME |
1572 | -} |
1573 | - |
1574 | - |
1575 | -// Load branch buffer with branches from full node plus the extra branch. |
1576 | -RTREE_TEMPLATE |
1577 | -void RTREE_QUAL::GetBranches( Node* a_node, Branch* a_branch, PartitionVars* a_parVars ) |
1578 | -{ |
1579 | - ASSERT( a_node ); |
1580 | - ASSERT( a_branch ); |
1581 | - |
1582 | - ASSERT( a_node->m_count == MAXNODES ); |
1583 | - |
1584 | - // Load the branch buffer |
1585 | - for( int index = 0; index < MAXNODES; ++index ) |
1586 | - { |
1587 | - a_parVars->m_branchBuf[index] = a_node->m_branch[index]; |
1588 | - } |
1589 | - |
1590 | - a_parVars->m_branchBuf[MAXNODES] = *a_branch; |
1591 | - a_parVars->m_branchCount = MAXNODES + 1; |
1592 | - |
1593 | - // Calculate rect containing all in the set |
1594 | - a_parVars->m_coverSplit = a_parVars->m_branchBuf[0].m_rect; |
1595 | - |
1596 | - for( int index = 1; index < MAXNODES + 1; ++index ) |
1597 | - { |
1598 | - a_parVars->m_coverSplit = |
1599 | - CombineRect( &a_parVars->m_coverSplit, &a_parVars->m_branchBuf[index].m_rect ); |
1600 | - } |
1601 | - |
1602 | - a_parVars->m_coverSplitArea = CalcRectVolume( &a_parVars->m_coverSplit ); |
1603 | - |
1604 | - InitNode( a_node ); |
1605 | -} |
1606 | - |
1607 | - |
1608 | -// Method #0 for choosing a partition: |
1609 | -// As the seeds for the two groups, pick the two rects that would waste the |
1610 | -// most area if covered by a single rectangle, i.e. evidently the worst pair |
1611 | -// to have in the same group. |
1612 | -// Of the remaining, one at a time is chosen to be put in one of the two groups. |
1613 | -// The one chosen is the one with the greatest difference in area expansion |
1614 | -// depending on which group - the rect most strongly attracted to one group |
1615 | -// and repelled from the other. |
1616 | -// If one group gets too full (more would force other group to violate min |
1617 | -// fill requirement) then other group gets the rest. |
1618 | -// These last are the ones that can go in either group most easily. |
1619 | -RTREE_TEMPLATE |
1620 | -void RTREE_QUAL::ChoosePartition( PartitionVars* a_parVars, int a_minFill ) |
1621 | -{ |
1622 | - ASSERT( a_parVars ); |
1623 | - |
1624 | - ELEMTYPEREAL biggestDiff; |
1625 | - int group, chosen=0, betterGroup=0; |
1626 | - |
1627 | - InitParVars( a_parVars, a_parVars->m_branchCount, a_minFill ); |
1628 | - PickSeeds( a_parVars ); |
1629 | - |
1630 | - while( ( (a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total ) |
1631 | - && ( a_parVars->m_count[0] < (a_parVars->m_total - a_parVars->m_minFill) ) |
1632 | - && ( a_parVars->m_count[1] < (a_parVars->m_total - a_parVars->m_minFill) ) ) |
1633 | - { |
1634 | - biggestDiff = (ELEMTYPEREAL) -1; |
1635 | - |
1636 | - for( int index = 0; index<a_parVars->m_total; ++index ) |
1637 | - { |
1638 | - if( !a_parVars->m_taken[index] ) |
1639 | - { |
1640 | - Rect* curRect = &a_parVars->m_branchBuf[index].m_rect; |
1641 | - Rect rect0 = CombineRect( curRect, &a_parVars->m_cover[0] ); |
1642 | - Rect rect1 = CombineRect( curRect, &a_parVars->m_cover[1] ); |
1643 | - ELEMTYPEREAL growth0 = CalcRectVolume( &rect0 ) - a_parVars->m_area[0]; |
1644 | - ELEMTYPEREAL growth1 = CalcRectVolume( &rect1 ) - a_parVars->m_area[1]; |
1645 | - ELEMTYPEREAL diff = growth1 - growth0; |
1646 | - |
1647 | - if( diff >= 0 ) |
1648 | - { |
1649 | - group = 0; |
1650 | - } |
1651 | - else |
1652 | - { |
1653 | - group = 1; |
1654 | - diff = -diff; |
1655 | - } |
1656 | - |
1657 | - if( diff > biggestDiff ) |
1658 | - { |
1659 | - biggestDiff = diff; |
1660 | - chosen = index; |
1661 | - betterGroup = group; |
1662 | - } |
1663 | - else if( (diff == biggestDiff) |
1664 | - && (a_parVars->m_count[group] < a_parVars->m_count[betterGroup]) ) |
1665 | - { |
1666 | - chosen = index; |
1667 | - betterGroup = group; |
1668 | - } |
1669 | - } |
1670 | - } |
1671 | - |
1672 | - Classify( chosen, betterGroup, a_parVars ); |
1673 | - } |
1674 | - |
1675 | - // If one group too full, put remaining rects in the other |
1676 | - if( (a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total ) |
1677 | - { |
1678 | - if( a_parVars->m_count[0] >= a_parVars->m_total - a_parVars->m_minFill ) |
1679 | - { |
1680 | - group = 1; |
1681 | - } |
1682 | - else |
1683 | - { |
1684 | - group = 0; |
1685 | - } |
1686 | - |
1687 | - for( int index = 0; index<a_parVars->m_total; ++index ) |
1688 | - { |
1689 | - if( !a_parVars->m_taken[index] ) |
1690 | - { |
1691 | - Classify( index, group, a_parVars ); |
1692 | - } |
1693 | - } |
1694 | - } |
1695 | - |
1696 | - ASSERT( (a_parVars->m_count[0] + a_parVars->m_count[1]) == a_parVars->m_total ); |
1697 | - ASSERT( (a_parVars->m_count[0] >= a_parVars->m_minFill) |
1698 | - && (a_parVars->m_count[1] >= a_parVars->m_minFill) ); |
1699 | -} |
1700 | - |
1701 | - |
1702 | -// Copy branches from the buffer into two nodes according to the partition. |
1703 | -RTREE_TEMPLATE |
1704 | -void RTREE_QUAL::LoadNodes( Node* a_nodeA, Node* a_nodeB, PartitionVars* a_parVars ) |
1705 | -{ |
1706 | - ASSERT( a_nodeA ); |
1707 | - ASSERT( a_nodeB ); |
1708 | - ASSERT( a_parVars ); |
1709 | - |
1710 | - for( int index = 0; index < a_parVars->m_total; ++index ) |
1711 | - { |
1712 | - ASSERT( a_parVars->m_partition[index] == 0 || a_parVars->m_partition[index] == 1 ); |
1713 | - |
1714 | - if( a_parVars->m_partition[index] == 0 ) |
1715 | - { |
1716 | - AddBranch( &a_parVars->m_branchBuf[index], a_nodeA, NULL ); |
1717 | - } |
1718 | - else if( a_parVars->m_partition[index] == 1 ) |
1719 | - { |
1720 | - AddBranch( &a_parVars->m_branchBuf[index], a_nodeB, NULL ); |
1721 | - } |
1722 | - } |
1723 | -} |
1724 | - |
1725 | - |
1726 | -// Initialize a PartitionVars structure. |
1727 | -RTREE_TEMPLATE |
1728 | -void RTREE_QUAL::InitParVars( PartitionVars* a_parVars, int a_maxRects, int a_minFill ) |
1729 | -{ |
1730 | - ASSERT( a_parVars ); |
1731 | - |
1732 | - a_parVars->m_count[0] = a_parVars->m_count[1] = 0; |
1733 | - a_parVars->m_area[0] = a_parVars->m_area[1] = (ELEMTYPEREAL) 0; |
1734 | - a_parVars->m_total = a_maxRects; |
1735 | - a_parVars->m_minFill = a_minFill; |
1736 | - |
1737 | - for( int index = 0; index < a_maxRects; ++index ) |
1738 | - { |
1739 | - a_parVars->m_taken[index] = false; |
1740 | - a_parVars->m_partition[index] = -1; |
1741 | - } |
1742 | -} |
1743 | - |
1744 | - |
1745 | -RTREE_TEMPLATE |
1746 | -void RTREE_QUAL::PickSeeds( PartitionVars* a_parVars ) |
1747 | -{ |
1748 | - int seed0 = 0, seed1 = 0; // avoid compil complaint about uninitialized |
1749 | - ELEMTYPEREAL worst, waste; |
1750 | - ELEMTYPEREAL area[MAXNODES + 1]; |
1751 | - |
1752 | - for( int index = 0; index<a_parVars->m_total; ++index ) |
1753 | - { |
1754 | - area[index] = CalcRectVolume( &a_parVars->m_branchBuf[index].m_rect ); |
1755 | - } |
1756 | - |
1757 | - worst = -a_parVars->m_coverSplitArea - 1; |
1758 | - |
1759 | - for( int indexA = 0; indexA < a_parVars->m_total - 1; ++indexA ) |
1760 | - { |
1761 | - for( int indexB = indexA + 1; indexB < a_parVars->m_total; ++indexB ) |
1762 | - { |
1763 | - Rect oneRect = CombineRect( &a_parVars->m_branchBuf[indexA].m_rect, |
1764 | - &a_parVars->m_branchBuf[indexB].m_rect ); |
1765 | - waste = CalcRectVolume( &oneRect ) - area[indexA] - area[indexB]; |
1766 | - |
1767 | - if( waste > worst ) |
1768 | - { |
1769 | - worst = waste; |
1770 | - seed0 = indexA; |
1771 | - seed1 = indexB; |
1772 | - } |
1773 | - } |
1774 | - } |
1775 | - |
1776 | - Classify( seed0, 0, a_parVars ); |
1777 | - Classify( seed1, 1, a_parVars ); |
1778 | -} |
1779 | - |
1780 | - |
1781 | -// Put a branch in one of the groups. |
1782 | -RTREE_TEMPLATE |
1783 | -void RTREE_QUAL::Classify( int a_index, int a_group, PartitionVars* a_parVars ) |
1784 | -{ |
1785 | - ASSERT( a_parVars ); |
1786 | - ASSERT( !a_parVars->m_taken[a_index] ); |
1787 | - |
1788 | - a_parVars->m_partition[a_index] = a_group; |
1789 | - a_parVars->m_taken[a_index] = true; |
1790 | - |
1791 | - if( a_parVars->m_count[a_group] == 0 ) |
1792 | - { |
1793 | - a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect; |
1794 | - } |
1795 | - else |
1796 | - { |
1797 | - a_parVars->m_cover[a_group] = CombineRect( &a_parVars->m_branchBuf[a_index].m_rect, |
1798 | - &a_parVars->m_cover[a_group] ); |
1799 | - } |
1800 | - |
1801 | - a_parVars->m_area[a_group] = CalcRectVolume( &a_parVars->m_cover[a_group] ); |
1802 | - ++a_parVars->m_count[a_group]; |
1803 | -} |
1804 | - |
1805 | - |
1806 | -// Delete a data rectangle from an index structure. |
1807 | -// Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node. |
1808 | -// Returns 1 if record not found, 0 if success. |
1809 | -// RemoveRect provides for eliminating the root. |
1810 | -RTREE_TEMPLATE |
1811 | -bool RTREE_QUAL::RemoveRect( Rect* a_rect, const DATATYPE& a_id, Node** a_root ) |
1812 | -{ |
1813 | - ASSERT( a_rect && a_root ); |
1814 | - ASSERT( *a_root ); |
1815 | - |
1816 | - Node* tempNode; |
1817 | - ListNode* reInsertList = NULL; |
1818 | - |
1819 | - if( !RemoveRectRec( a_rect, a_id, *a_root, &reInsertList ) ) |
1820 | - { |
1821 | - // Found and deleted a data item |
1822 | - // Reinsert any branches from eliminated nodes |
1823 | - while( reInsertList ) |
1824 | - { |
1825 | - tempNode = reInsertList->m_node; |
1826 | - |
1827 | - for( int index = 0; index < tempNode->m_count; ++index ) |
1828 | - { |
1829 | - InsertRect( &(tempNode->m_branch[index].m_rect), |
1830 | - tempNode->m_branch[index].m_data, |
1831 | - a_root, |
1832 | - tempNode->m_level ); |
1833 | - } |
1834 | - |
1835 | - ListNode* remLNode = reInsertList; |
1836 | - reInsertList = reInsertList->m_next; |
1837 | - |
1838 | - FreeNode( remLNode->m_node ); |
1839 | - FreeListNode( remLNode ); |
1840 | - } |
1841 | - |
1842 | - // Check for redundant root (not leaf, 1 child) and eliminate |
1843 | - if( (*a_root)->m_count == 1 && (*a_root)->IsInternalNode() ) |
1844 | - { |
1845 | - tempNode = (*a_root)->m_branch[0].m_child; |
1846 | - |
1847 | - ASSERT( tempNode ); |
1848 | - FreeNode( *a_root ); |
1849 | - *a_root = tempNode; |
1850 | - } |
1851 | - |
1852 | - return false; |
1853 | - } |
1854 | - else |
1855 | - { |
1856 | - return true; |
1857 | - } |
1858 | -} |
1859 | - |
1860 | - |
1861 | -// Delete a rectangle from non-root part of an index structure. |
1862 | -// Called by RemoveRect. Descends tree recursively, |
1863 | -// merges branches on the way back up. |
1864 | -// Returns 1 if record not found, 0 if success. |
1865 | -RTREE_TEMPLATE |
1866 | -bool RTREE_QUAL::RemoveRectRec( Rect* a_rect, |
1867 | - const DATATYPE& a_id, |
1868 | - Node* a_node, |
1869 | - ListNode** a_listNode ) |
1870 | -{ |
1871 | - ASSERT( a_rect && a_node && a_listNode ); |
1872 | - ASSERT( a_node->m_level >= 0 ); |
1873 | - |
1874 | - if( a_node->IsInternalNode() ) // not a leaf node |
1875 | - { |
1876 | - for( int index = 0; index < a_node->m_count; ++index ) |
1877 | - { |
1878 | - if( Overlap( a_rect, &(a_node->m_branch[index].m_rect) ) ) |
1879 | - { |
1880 | - if( !RemoveRectRec( a_rect, a_id, a_node->m_branch[index].m_child, a_listNode ) ) |
1881 | - { |
1882 | - if( a_node->m_branch[index].m_child->m_count >= MINNODES ) |
1883 | - { |
1884 | - // child removed, just resize parent rect |
1885 | - a_node->m_branch[index].m_rect = |
1886 | - NodeCover( a_node->m_branch[index].m_child ); |
1887 | - } |
1888 | - else |
1889 | - { |
1890 | - // child removed, not enough entries in node, eliminate node |
1891 | - ReInsert( a_node->m_branch[index].m_child, a_listNode ); |
1892 | - DisconnectBranch( a_node, index ); // Must return after this call as count has changed |
1893 | - } |
1894 | - |
1895 | - return false; |
1896 | - } |
1897 | - } |
1898 | - } |
1899 | - |
1900 | - return true; |
1901 | - } |
1902 | - else // A leaf node |
1903 | - { |
1904 | - for( int index = 0; index < a_node->m_count; ++index ) |
1905 | - { |
1906 | - if( a_node->m_branch[index].m_child == (Node*) a_id ) |
1907 | - { |
1908 | - DisconnectBranch( a_node, index ); // Must return after this call as count has changed |
1909 | - return false; |
1910 | - } |
1911 | - } |
1912 | - |
1913 | - return true; |
1914 | - } |
1915 | -} |
1916 | - |
1917 | - |
1918 | -// Decide whether two rectangles overlap. |
1919 | -RTREE_TEMPLATE |
1920 | -bool RTREE_QUAL::Overlap( Rect* a_rectA, Rect* a_rectB ) |
1921 | -{ |
1922 | - ASSERT( a_rectA && a_rectB ); |
1923 | - |
1924 | - for( int index = 0; index < NUMDIMS; ++index ) |
1925 | - { |
1926 | - if( a_rectA->m_min[index] > a_rectB->m_max[index] |
1927 | - || a_rectB->m_min[index] > a_rectA->m_max[index] ) |
1928 | - { |
1929 | - return false; |
1930 | - } |
1931 | - } |
1932 | - |
1933 | - return true; |
1934 | -} |
1935 | - |
1936 | - |
1937 | -// Add a node to the reinsertion list. All its branches will later |
1938 | -// be reinserted into the index structure. |
1939 | -RTREE_TEMPLATE |
1940 | -void RTREE_QUAL::ReInsert( Node* a_node, ListNode** a_listNode ) |
1941 | -{ |
1942 | - ListNode* newListNode; |
1943 | - |
1944 | - newListNode = AllocListNode(); |
1945 | - newListNode->m_node = a_node; |
1946 | - newListNode->m_next = *a_listNode; |
1947 | - *a_listNode = newListNode; |
1948 | -} |
1949 | - |
1950 | - |
1951 | -// Search in an index tree or subtree for all data retangles that overlap the argument rectangle. |
1952 | -RTREE_TEMPLATE |
1953 | -bool RTREE_QUAL::Search( Node* a_node, Rect* a_rect, int& a_foundCount, bool a_resultCallback( |
1954 | - DATATYPE a_data, |
1955 | - void* a_context ), void* a_context ) |
1956 | -{ |
1957 | - ASSERT( a_node ); |
1958 | - ASSERT( a_node->m_level >= 0 ); |
1959 | - ASSERT( a_rect ); |
1960 | - |
1961 | - if( a_node->IsInternalNode() ) // This is an internal node in the tree |
1962 | - { |
1963 | - for( int index = 0; index < a_node->m_count; ++index ) |
1964 | - { |
1965 | - if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) ) |
1966 | - { |
1967 | - if( !Search( a_node->m_branch[index].m_child, a_rect, a_foundCount, |
1968 | - a_resultCallback, a_context ) ) |
1969 | - { |
1970 | - return false; // Don't continue searching |
1971 | - } |
1972 | - } |
1973 | - } |
1974 | - } |
1975 | - else // This is a leaf node |
1976 | - { |
1977 | - for( int index = 0; index < a_node->m_count; ++index ) |
1978 | - { |
1979 | - if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) ) |
1980 | - { |
1981 | - DATATYPE& id = a_node->m_branch[index].m_data; |
1982 | - |
1983 | - // NOTE: There are different ways to return results. Here's where to modify |
1984 | - if( &a_resultCallback ) |
1985 | - { |
1986 | - ++a_foundCount; |
1987 | - |
1988 | - if( !a_resultCallback( id, a_context ) ) |
1989 | - { |
1990 | - return false; // Don't continue searching |
1991 | - } |
1992 | - } |
1993 | - } |
1994 | - } |
1995 | - } |
1996 | - |
1997 | - return true; // Continue searching |
1998 | -} |
1999 | - |
2000 | - |
2001 | -#undef RTREE_TEMPLATE |
2002 | -#undef RTREE_QUAL |
2003 | -#undef RTREE_SEARCH_TEMPLATE |
2004 | -#undef RTREE_SEARCH_QUAL |
2005 | - |
2006 | -#endif // RTREE_H |
2007 | |
2008 | === modified file 'include/view/view_rtree.h' |
2009 | --- include/view/view_rtree.h 2013-10-14 14:13:35 +0000 |
2010 | +++ include/view/view_rtree.h 2013-12-05 12:52:21 +0000 |
2011 | @@ -27,7 +27,7 @@ |
2012 | |
2013 | #include <math/box2.h> |
2014 | |
2015 | -#include <rtree.h> |
2016 | +#include <geometry/rtree.h> |
2017 | |
2018 | namespace KIGFX |
2019 | { |
2020 | @@ -76,7 +76,6 @@ |
2021 | * Executes a function object aVisitor for each item whose bounding box intersects |
2022 | * with aBounds. |
2023 | */ |
2024 | - |
2025 | template <class Visitor> |
2026 | void Query( const BOX2I& aBounds, Visitor& aVisitor ) // const |
2027 | { |
On 12/5/2013 7:53 AM, Maciej Sumiński wrote: committers (kicad- testing- committers) /bugs.launchpad .net/kicad/ +bug/1249736 /code.launchpad .net/~cern- kicad/kicad/ bugfix_ 1249736/ +merge/ 197858 /bugs.launchpad .net/kicad/ +bug/1249736 for wx2.9.
> Maciej Sumiński has proposed merging lp:~cern-kicad/kicad/bugfix_1249736 into lp:kicad.
>
> Requested reviews:
> kicad-testing-
> Related bugs:
> Bug #1249736 in KiCad: "pcbnew core dump: on rev. 4448 opening an existing pcb"
> https:/
>
> For more details, see:
> https:/
>
> Fixes https:/
> Removes duplicated rtree.h.
>
Orson,
Is this merge request ready to go? It compiles and doesn't seem to
cause any issues. I'm trying to catch up on the backlog of merge
requests and patches.
Wayne