root / trunk / libraries / libjni-readecw-linux / include / NCSQuadTree.h @ 1868
History | View | Annotate | Download (4.58 KB)
1 | 1448 | igbrotru | /********************************************************
|
---|---|---|---|
2 | ** Copyright 1999 Earth Resource Mapping Ltd.
|
||
3 | ** This document contains proprietary source code of
|
||
4 | ** Earth Resource Mapping Ltd, and can only be used under
|
||
5 | ** one of the three licenses as described in the
|
||
6 | ** license.txt file supplied with this distribution.
|
||
7 | ** See separate license.txt file for license details
|
||
8 | ** and conditions.
|
||
9 | **
|
||
10 | ** This software is covered by US patent #6,442,298,
|
||
11 | ** #6,102,897 and #6,633,688. Rights to use these patents
|
||
12 | ** is included in the license agreements.
|
||
13 | **
|
||
14 | ** FILE: NCSQTree.h
|
||
15 | ** CREATED: Thu Feb 25 09:19:00 WST 1999
|
||
16 | ** AUTHOR: Mark Sheridan
|
||
17 | ** PURPOSE: Generic Quad tree class for NCS. User should
|
||
18 | ** inherit directly from this class and supply
|
||
19 | ** the required virtual functions
|
||
20 | ** EDITS:
|
||
21 | *******************************************************/
|
||
22 | |||
23 | #ifndef NCSQUADTREE_H
|
||
24 | #define NCSQUADTREE_H
|
||
25 | |||
26 | #include "NCSTypes.h" |
||
27 | #include "NCSErrors.h" |
||
28 | #include "NCSDefs.h" |
||
29 | #include "NCSMalloc.h" |
||
30 | #include "NCSMutex.h" |
||
31 | #include <math.h> |
||
32 | #if (defined(WIN32) && !defined(_WIN32_WCE))
|
||
33 | #include <crtdbg.h> |
||
34 | #endif
|
||
35 | |||
36 | #define NCSQTreeGetNodeQuad1(pNode) (pNode->nw)
|
||
37 | #define NCSQTreeGetNodeQuad2(pNode) (pNode->ne)
|
||
38 | #define NCSQTreeGetNodeQuad3(pNode) (pNode->se)
|
||
39 | #define NCSQTreeGetNodeQuad4(pNode) (pNode->sw)
|
||
40 | #define NCSQTreeGetNodeData(pNode) (pNode->pData)
|
||
41 | #define NCSQTreeSetNodeData(pNode, pData) \
|
||
42 | pNode->pData = (void *)pData
|
||
43 | |||
44 | typedef struct NCSQTreeNode { |
||
45 | void *pData; // Pointer to generic data pointer |
||
46 | UINT32 nID; // Unique ID of this node
|
||
47 | IEEE8 dWorldX; // World X coordinate of node
|
||
48 | IEEE8 dWorldY; // World Y coordinate of node
|
||
49 | struct NCSQTreeNode *nw; // Pointer to Node in North West |
||
50 | struct NCSQTreeNode *ne; // Pointer to Node in North East |
||
51 | struct NCSQTreeNode *sw; // Pointer to Node in South West |
||
52 | struct NCSQTreeNode *se; // Pointer to Node in South East |
||
53 | } NCSQTreeNode; |
||
54 | |||
55 | typedef enum NCSQTreeAlg{ // The algorithm used to construct the Quad Tree |
||
56 | NCSQTALG_PRKD, // PRKD tree algorithm - NOT YET IMPLEMENTED
|
||
57 | NCSQTALG_PR, // PR tree algorithm
|
||
58 | NCSQTALG_POINT, // Simple point algorithm
|
||
59 | NCSQTALG_KD, // KD tree algorithm - NOT YET IMPLEMENTED
|
||
60 | NCSQTALG_MX, // MX tree algorithm - NOT YET IMPLEMENTED
|
||
61 | NCSQTALG_PMR, // PMR tree algorithm - NOT YET IMPLEMENTED
|
||
62 | NCSQTALG_SIMPLE_EDGES, // Edge algorithm - NOT YET IMPLEMENTED
|
||
63 | NCSQTALG_SIMPLE_GRID // Grid algorithm - NOT YET IMPLEMENTED
|
||
64 | } NCSQTreeAlg; |
||
65 | |||
66 | typedef NCSError (*NCSQTreeNodeFunc)(NCSQTreeNode *pNode, void *pInfo); |
||
67 | |||
68 | class __declspec( dllexport ) CNCSQTree |
||
69 | { |
||
70 | |||
71 | public:
|
||
72 | // Initialisation
|
||
73 | CNCSQTree(); |
||
74 | virtual ~CNCSQTree(); |
||
75 | NCSError InitExtents(NCSCoordSys CSysType, IEEE8 tlx, IEEE8 tly, IEEE8 brx, IEEE8 bry ); |
||
76 | |||
77 | // Node functions
|
||
78 | NCSError Print( void );
|
||
79 | NCSError Draw(void *pDrawInfo);
|
||
80 | void *GetNodeData( NCSQTreeNode *pNode);
|
||
81 | void SetNodeData (NCSQTreeNode *pNode, void *pData); |
||
82 | NCSQTreeNode *FindNode( IEEE8 dWorldX, IEEE8 dWorldY, IEEE8 dRadiusX, IEEE8 dRadiusY ); |
||
83 | |||
84 | // Virtual functions
|
||
85 | virtual NCSError DrawNode(void *pDrawInfo) = 0; |
||
86 | virtual NCSError PrintNode(NCSQTreeNode *pNode) = 0;
|
||
87 | virtual void FreeNodeData( void *pData ); |
||
88 | |||
89 | // Node creation-free
|
||
90 | NCSQTreeNode * FreeNode(NCSQTreeNode *pNode); |
||
91 | NCSQTreeNode * AddNode( void *pNodeData , IEEE8 dWorldX, IEEE8 dWorldY );
|
||
92 | |||
93 | // Algorithm functions
|
||
94 | NCSError SetAlgorithm(NCSQTreeAlg nAlg); |
||
95 | NCSQTreeAlg GetAlgorithm(); |
||
96 | |||
97 | // Tree traversal - use custom traverse function "pFunction".
|
||
98 | NCSError Traverse(NCSQTreeNodeFunc pFunction, void *pData);
|
||
99 | |||
100 | // Miscellaneous routines
|
||
101 | NCSError Balance(void);
|
||
102 | |||
103 | private:
|
||
104 | NCSQTreeNode * DrawInternal( void *pDrawInfo, NCSQTreeNode *pRoot);
|
||
105 | NCSQTreeNode * FindNodeInternal (NCSQTreeNode *pRoot, IEEE8 latitude, IEEE8 longitude); |
||
106 | NCSQTreeNode * AddNodeInternalPR( NCSQTreeNode *pRootNode, void *pData, IEEE8 latitude, IEEE8 longitude, IEEE8 tlx, IEEE8 tly, IEEE8 brx, IEEE8 bry);
|
||
107 | NCSQTreeNode * AddNodeInternalPOINT( NCSQTreeNode *pRootNode, void *pData, IEEE8 latitude, IEEE8 longitude);
|
||
108 | NCSQTreeNode * PrintInternal(NCSQTreeNode *pRoot); |
||
109 | NCSQTreeNode * TraverseNode(NCSQTreeNode *pNode, NCSQTreeNodeFunc pFunction, void *pData);
|
||
110 | NCSQTreeNode * CreateNode(IEEE8 dWorldX, IEEE8 dWorldY, void *pData);
|
||
111 | |||
112 | static NCSError NCSQTreeCalcExtentsFn(NCSQTreeNode *pNode, void *pInfo); |
||
113 | static NCSError NCSQTreeCopyFn(NCSQTreeNode *pNode, void *pInfo); |
||
114 | |||
115 | IEEE8 m_WorldTLX; |
||
116 | IEEE8 m_WorldTLY; |
||
117 | IEEE8 m_WorldBRX; |
||
118 | IEEE8 m_WorldBRY; |
||
119 | INT32 m_NrNodes; |
||
120 | UINT16 m_CurrDrawLevel; |
||
121 | IEEE8 m_RadiusDistanceX; |
||
122 | IEEE8 m_RadiusDistanceY; |
||
123 | |||
124 | NCSQTreeAlg m_nAlgorithm; |
||
125 | NCSQTreeNode * m_pRootNode; |
||
126 | NCSCoordSys m_CoordSys; |
||
127 | NCSQTreeNode *m_pFindNodeResult; |
||
128 | NCSMutex m_TraverseMutex; |
||
129 | }; |
||
130 | |||
131 | #endif |