GDAL

cpl_quad_tree.h
Go to the documentation of this file.
1/**********************************************************************
2 *
3 * Project: CPL - Common Portability Library
4 * Purpose: Implementation of quadtree building and searching functions.
5 * Derived from shapelib and mapserver implementations
6 * Author: Frank Warmerdam, warmerdam@pobox.com
7 * Even Rouault, <even dot rouault at spatialys.com>
8 *
9 ******************************************************************************
10 * Copyright (c) 1999-2008, Frank Warmerdam
11 * Copyright (c) 2008-2014, Even Rouault <even dot rouault at spatialys.com>
12 *
13 * SPDX-License-Identifier: MIT
14 ****************************************************************************/
15
16#ifndef CPL_QUAD_TREE_H_INCLUDED
17#define CPL_QUAD_TREE_H_INCLUDED
18
19#include "cpl_port.h"
20
21#include <stdbool.h>
22
34 CPL_C_START
35
36/* Types */
37
39 typedef struct
40{
41 double minx;
42 double miny;
43 double maxx;
44 double maxy;
45} CPLRectObj;
46
48 typedef struct _CPLQuadTree CPLQuadTree;
49
51 typedef void (*CPLQuadTreeGetBoundsFunc)(const void *hFeature,
52 CPLRectObj *pBounds);
54 typedef void (*CPLQuadTreeGetBoundsExFunc)(const void *hFeature,
55 void *pUserData,
56 CPLRectObj *pBounds);
58 typedef int (*CPLQuadTreeForeachFunc)(void *pElt, void *pUserData);
60 typedef void (*CPLQuadTreeDumpFeatureFunc)(const void *hFeature,
61 int nIndentLevel, void *pUserData);
62
63/* Functions */
64
65 CPLQuadTree CPL_DLL *CPLQuadTreeCreate(const CPLRectObj *pGlobalBounds,
66 CPLQuadTreeGetBoundsFunc pfnGetBounds);
67 CPLQuadTree CPL_DLL *
68 CPLQuadTreeCreateEx(const CPLRectObj *pGlobalBounds,
69 CPLQuadTreeGetBoundsExFunc pfnGetBounds, void *pUserData);
70 void CPL_DLL CPLQuadTreeDestroy(CPLQuadTree *hQuadtree);
71
72 void CPL_DLL CPLQuadTreeSetBucketCapacity(CPLQuadTree *hQuadtree,
73 int nBucketCapacity);
74 void CPL_DLL CPLQuadTreeForceUseOfSubNodes(CPLQuadTree *hQuadTree);
75 int CPL_DLL CPLQuadTreeGetAdvisedMaxDepth(int nExpectedFeatures);
76 void CPL_DLL CPLQuadTreeSetMaxDepth(CPLQuadTree *hQuadtree, int nMaxDepth);
77
78 void CPL_DLL CPLQuadTreeInsert(CPLQuadTree *hQuadtree, void *hFeature);
79 void CPL_DLL CPLQuadTreeInsertWithBounds(CPLQuadTree *hQuadtree, void *hFeature,
80 const CPLRectObj *psBounds);
81
82 void CPL_DLL CPLQuadTreeRemove(CPLQuadTree *hQuadtree, void *hFeature,
83 const CPLRectObj *psBounds);
84
85 void CPL_DLL **CPLQuadTreeSearch(const CPLQuadTree *hQuadtree,
86 const CPLRectObj *pAoi, int *pnFeatureCount);
87
88 bool CPL_DLL CPLQuadTreeHasMatch(const CPLQuadTree *hQuadtree,
89 const CPLRectObj *pAoi);
90
91 void CPL_DLL CPLQuadTreeForeach(const CPLQuadTree *hQuadtree,
92 CPLQuadTreeForeachFunc pfnForeach,
93 void *pUserData);
94
95 void CPL_DLL CPLQuadTreeDump(const CPLQuadTree *hQuadtree,
96 CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc,
97 void *pUserData);
98 void CPL_DLL CPLQuadTreeGetStats(const CPLQuadTree *hQuadtree,
99 int *pnFeatureCount, int *pnNodeCount,
100 int *pnMaxDepth, int *pnMaxBucketCapacity);
101
102 CPL_C_END
103
104#endif
cpl_port.h
Core portability definitions for CPL.
CPL_C_END
#define CPL_C_END
Macro to end a block of C symbols.
Definition cpl_port.h:289
CPL_C_START
#define CPL_C_START
Macro to start a block of C symbols.
Definition cpl_port.h:285
CPLQuadTreeCreateEx
CPLQuadTree * CPLQuadTreeCreateEx(const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsExFunc pfnGetBounds, void *pUserData)
Create a new quadtree.
Definition cpl_quad_tree.cpp:187
CPLQuadTreeRemove
void CPLQuadTreeRemove(CPLQuadTree *hQuadtree, void *hFeature, const CPLRectObj *psBounds)
Remove a feature from a quadtree.
Definition cpl_quad_tree.cpp:447
CPLQuadTreeCreate
CPLQuadTree * CPLQuadTreeCreate(const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsFunc pfnGetBounds)
Create a new quadtree.
Definition cpl_quad_tree.cpp:138
CPLQuadTreeHasMatch
bool CPLQuadTreeHasMatch(const CPLQuadTree *hQuadtree, const CPLRectObj *pAoi)
Returns whether the quadtree has at least one element whose bounding box intersects the provided area...
Definition cpl_quad_tree.cpp:980
CPLQuadTreeGetBoundsExFunc
void(* CPLQuadTreeGetBoundsExFunc)(const void *hFeature, void *pUserData, CPLRectObj *pBounds)
CPLQuadTreeGetBoundsExFunc.
Definition cpl_quad_tree.h:54
CPLQuadTreeInsert
void CPLQuadTreeInsert(CPLQuadTree *hQuadtree, void *hFeature)
Insert a feature into a quadtree.
Definition cpl_quad_tree.cpp:330
CPLQuadTreeForeachFunc
int(* CPLQuadTreeForeachFunc)(void *pElt, void *pUserData)
CPLQuadTreeForeachFunc.
Definition cpl_quad_tree.h:58
CPLQuadTreeSearch
void ** CPLQuadTreeSearch(const CPLQuadTree *hQuadtree, const CPLRectObj *pAoi, int *pnFeatureCount)
Returns all the elements inserted whose bounding box intersects the provided area of interest.
Definition cpl_quad_tree.cpp:896
CPLQuadTreeGetBoundsFunc
void(* CPLQuadTreeGetBoundsFunc)(const void *hFeature, CPLRectObj *pBounds)
CPLQuadTreeGetBoundsFunc.
Definition cpl_quad_tree.h:51
CPLQuadTreeGetStats
void CPLQuadTreeGetStats(const CPLQuadTree *hQuadtree, int *pnFeatureCount, int *pnNodeCount, int *pnMaxDepth, int *pnMaxBucketCapacity)
Get stats.
Definition cpl_quad_tree.cpp:1128
CPLQuadTreeDump
void CPLQuadTreeDump(const CPLQuadTree *hQuadtree, CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc, void *pUserData)
Dump quad tree.
Definition cpl_quad_tree.cpp:1095
CPLQuadTreeForeach
void CPLQuadTreeForeach(const CPLQuadTree *hQuadtree, CPLQuadTreeForeachFunc pfnForeach, void *pUserData)
Walk through the quadtree and runs the provided function on all the elements.
Definition cpl_quad_tree.cpp:1032
CPLQuadTreeSetBucketCapacity
void CPLQuadTreeSetBucketCapacity(CPLQuadTree *hQuadtree, int nBucketCapacity)
Set the maximum capacity of a node of a quadtree.
Definition cpl_quad_tree.cpp:296
CPLQuadTreeSetMaxDepth
void CPLQuadTreeSetMaxDepth(CPLQuadTree *hQuadtree, int nMaxDepth)
Set the maximum depth of a quadtree.
Definition cpl_quad_tree.cpp:278
CPLQuadTreeDestroy
void CPLQuadTreeDestroy(CPLQuadTree *hQuadtree)
Destroy a quadtree.
Definition cpl_quad_tree.cpp:503
CPLQuadTree
struct _CPLQuadTree CPLQuadTree
Opaque type for a quad tree.
Definition cpl_quad_tree.h:48
CPLQuadTreeInsertWithBounds
void CPLQuadTreeInsertWithBounds(CPLQuadTree *hQuadtree, void *hFeature, const CPLRectObj *psBounds)
Insert a feature into a quadtree.
Definition cpl_quad_tree.cpp:359
CPLQuadTreeDumpFeatureFunc
void(* CPLQuadTreeDumpFeatureFunc)(const void *hFeature, int nIndentLevel, void *pUserData)
CPLQuadTreeDumpFeatureFunc.
Definition cpl_quad_tree.h:60
CPLQuadTreeForceUseOfSubNodes
void CPLQuadTreeForceUseOfSubNodes(CPLQuadTree *hQuadTree)
Force the quadtree to insert as much as possible a feature whose bbox spread over multiple subnodes i...
Definition cpl_quad_tree.cpp:314
CPLQuadTreeGetAdvisedMaxDepth
int CPLQuadTreeGetAdvisedMaxDepth(int nExpectedFeatures)
Returns the optimal depth of a quadtree to hold nExpectedFeatures.
Definition cpl_quad_tree.cpp:231
CPLRectObj
Describe a rectangle.
Definition cpl_quad_tree.h:40
CPLRectObj::minx
double minx
Minimum x.
Definition cpl_quad_tree.h:41
CPLRectObj::maxy
double maxy
Maximum y.
Definition cpl_quad_tree.h:44
CPLRectObj::miny
double miny
Minimum y.
Definition cpl_quad_tree.h:42
CPLRectObj::maxx
double maxx
Maximum x.
Definition cpl_quad_tree.h:43