GDAL

cpl_quad_tree.h
Go to the documentation of this file.
1/**********************************************************************
2 * $Id$
3 *
4 * Project: CPL - Common Portability Library
5 * Purpose: Implementation of quadtree building and searching functions.
6 * Derived from shapelib and mapserver implementations
7 * Author: Frank Warmerdam, warmerdam@pobox.com
8 * Even Rouault, <even dot rouault at spatialys.com>
9 *
10 ******************************************************************************
11 * Copyright (c) 1999-2008, Frank Warmerdam
12 * Copyright (c) 2008-2014, Even Rouault <even dot rouault at spatialys.com>
13 *
14 * SPDX-License-Identifier: MIT
15 ****************************************************************************/
16
17#ifndef CPL_QUAD_TREE_H_INCLUDED
18#define CPL_QUAD_TREE_H_INCLUDED
19
20#include "cpl_port.h"
21
22#include <stdbool.h>
23
35 CPL_C_START
36
37/* Types */
38
40 typedef struct
41{
42 double minx;
43 double miny;
44 double maxx;
45 double maxy;
46} CPLRectObj;
47
49 typedef struct _CPLQuadTree CPLQuadTree;
50
52 typedef void (*CPLQuadTreeGetBoundsFunc)(const void *hFeature,
53 CPLRectObj *pBounds);
55 typedef void (*CPLQuadTreeGetBoundsExFunc)(const void *hFeature,
56 void *pUserData,
57 CPLRectObj *pBounds);
59 typedef int (*CPLQuadTreeForeachFunc)(void *pElt, void *pUserData);
61 typedef void (*CPLQuadTreeDumpFeatureFunc)(const void *hFeature,
62 int nIndentLevel, void *pUserData);
63
64/* Functions */
65
66 CPLQuadTree CPL_DLL *CPLQuadTreeCreate(const CPLRectObj *pGlobalBounds,
67 CPLQuadTreeGetBoundsFunc pfnGetBounds);
68 CPLQuadTree CPL_DLL *
69 CPLQuadTreeCreateEx(const CPLRectObj *pGlobalBounds,
70 CPLQuadTreeGetBoundsExFunc pfnGetBounds, void *pUserData);
71 void CPL_DLL CPLQuadTreeDestroy(CPLQuadTree *hQuadtree);
72
73 void CPL_DLL CPLQuadTreeSetBucketCapacity(CPLQuadTree *hQuadtree,
74 int nBucketCapacity);
75 void CPL_DLL CPLQuadTreeForceUseOfSubNodes(CPLQuadTree *hQuadTree);
76 int CPL_DLL CPLQuadTreeGetAdvisedMaxDepth(int nExpectedFeatures);
77 void CPL_DLL CPLQuadTreeSetMaxDepth(CPLQuadTree *hQuadtree, int nMaxDepth);
78
79 void CPL_DLL CPLQuadTreeInsert(CPLQuadTree *hQuadtree, void *hFeature);
80 void CPL_DLL CPLQuadTreeInsertWithBounds(CPLQuadTree *hQuadtree, void *hFeature,
81 const CPLRectObj *psBounds);
82
83 void CPL_DLL CPLQuadTreeRemove(CPLQuadTree *hQuadtree, void *hFeature,
84 const CPLRectObj *psBounds);
85
86 void CPL_DLL **CPLQuadTreeSearch(const CPLQuadTree *hQuadtree,
87 const CPLRectObj *pAoi, int *pnFeatureCount);
88
89 bool CPL_DLL CPLQuadTreeHasMatch(const CPLQuadTree *hQuadtree,
90 const CPLRectObj *pAoi);
91
92 void CPL_DLL CPLQuadTreeForeach(const CPLQuadTree *hQuadtree,
93 CPLQuadTreeForeachFunc pfnForeach,
94 void *pUserData);
95
96 void CPL_DLL CPLQuadTreeDump(const CPLQuadTree *hQuadtree,
97 CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc,
98 void *pUserData);
99 void CPL_DLL CPLQuadTreeGetStats(const CPLQuadTree *hQuadtree,
100 int *pnFeatureCount, int *pnNodeCount,
101 int *pnMaxDepth, int *pnMaxBucketCapacity);
102
103 CPL_C_END
104
105#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:283
CPL_C_START
#define CPL_C_START
Macro to start a block of C symbols.
Definition cpl_port.h:279
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:442
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:975
CPLQuadTreeGetBoundsExFunc
void(* CPLQuadTreeGetBoundsExFunc)(const void *hFeature, void *pUserData, CPLRectObj *pBounds)
CPLQuadTreeGetBoundsExFunc.
Definition cpl_quad_tree.h:55
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:59
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:891
CPLQuadTreeGetBoundsFunc
void(* CPLQuadTreeGetBoundsFunc)(const void *hFeature, CPLRectObj *pBounds)
CPLQuadTreeGetBoundsFunc.
Definition cpl_quad_tree.h:52
CPLQuadTreeGetStats
void CPLQuadTreeGetStats(const CPLQuadTree *hQuadtree, int *pnFeatureCount, int *pnNodeCount, int *pnMaxDepth, int *pnMaxBucketCapacity)
Get stats.
Definition cpl_quad_tree.cpp:1123
CPLQuadTreeDump
void CPLQuadTreeDump(const CPLQuadTree *hQuadtree, CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc, void *pUserData)
Dump quad tree.
Definition cpl_quad_tree.cpp:1090
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:1027
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:498
CPLQuadTree
struct _CPLQuadTree CPLQuadTree
Opaque type for a quad tree.
Definition cpl_quad_tree.h:49
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:61
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:41
CPLRectObj::minx
double minx
Minimum x.
Definition cpl_quad_tree.h:42
CPLRectObj::maxy
double maxy
Maximum y.
Definition cpl_quad_tree.h:45
CPLRectObj::miny
double miny
Minimum y.
Definition cpl_quad_tree.h:43
CPLRectObj::maxx
double maxx
Maximum x.
Definition cpl_quad_tree.h:44