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
36
37/* Types */
38
40typedef struct
41{
42 double minx;
43 double miny;
44 double maxx;
45 double maxy;
47
49typedef struct _CPLQuadTree CPLQuadTree;
50
52typedef void (*CPLQuadTreeGetBoundsFunc)(const void *hFeature,
53 CPLRectObj *pBounds);
55typedef void (*CPLQuadTreeGetBoundsExFunc)(const void *hFeature,
56 void *pUserData,
57 CPLRectObj *pBounds);
59typedef int (*CPLQuadTreeForeachFunc)(void *pElt, void *pUserData);
61typedef void (*CPLQuadTreeDumpFeatureFunc)(const void *hFeature,
62 int nIndentLevel, void *pUserData);
63
64/* Functions */
65
66CPLQuadTree CPL_DLL *CPLQuadTreeCreate(const CPLRectObj *pGlobalBounds,
67 CPLQuadTreeGetBoundsFunc pfnGetBounds);
68CPLQuadTree CPL_DLL *
69CPLQuadTreeCreateEx(const CPLRectObj *pGlobalBounds,
70 CPLQuadTreeGetBoundsExFunc pfnGetBounds, void *pUserData);
71void CPL_DLL CPLQuadTreeDestroy(CPLQuadTree *hQuadtree);
72
73void CPL_DLL CPLQuadTreeSetBucketCapacity(CPLQuadTree *hQuadtree,
74 int nBucketCapacity);
75void CPL_DLL CPLQuadTreeForceUseOfSubNodes(CPLQuadTree *hQuadTree);
76int CPL_DLL CPLQuadTreeGetAdvisedMaxDepth(int nExpectedFeatures);
77void CPL_DLL CPLQuadTreeSetMaxDepth(CPLQuadTree *hQuadtree, int nMaxDepth);
78
79void CPL_DLL CPLQuadTreeInsert(CPLQuadTree *hQuadtree, void *hFeature);
80void CPL_DLL CPLQuadTreeInsertWithBounds(CPLQuadTree *hQuadtree, void *hFeature,
81 const CPLRectObj *psBounds);
82
83void CPL_DLL CPLQuadTreeRemove(CPLQuadTree *hQuadtree, void *hFeature,
84 const CPLRectObj *psBounds);
85
86void CPL_DLL **CPLQuadTreeSearch(const CPLQuadTree *hQuadtree,
87 const CPLRectObj *pAoi, int *pnFeatureCount);
88
89bool CPL_DLL CPLQuadTreeHasMatch(const CPLQuadTree *hQuadtree,
90 const CPLRectObj *pAoi);
91
92void CPL_DLL CPLQuadTreeForeach(const CPLQuadTree *hQuadtree,
93 CPLQuadTreeForeachFunc pfnForeach,
94 void *pUserData);
95
96void CPL_DLL CPLQuadTreeDump(const CPLQuadTree *hQuadtree,
97 CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc,
98 void *pUserData);
99void CPL_DLL CPLQuadTreeGetStats(const CPLQuadTree *hQuadtree,
100 int *pnFeatureCount, int *pnNodeCount,
101 int *pnMaxDepth, int *pnMaxBucketCapacity);
102
104
105#endif
Core portability definitions for CPL.
#define CPL_C_END
Macro to end a block of C symbols.
Definition: cpl_port.h:283
#define CPL_C_START
Macro to start a block of C symbols.
Definition: cpl_port.h:279
CPLQuadTree * CPLQuadTreeCreateEx(const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsExFunc pfnGetBounds, void *pUserData)
Create a new quadtree.
Definition: cpl_quad_tree.cpp:187
void CPLQuadTreeRemove(CPLQuadTree *hQuadtree, void *hFeature, const CPLRectObj *psBounds)
Remove a feature from a quadtree.
Definition: cpl_quad_tree.cpp:442
CPLQuadTree * CPLQuadTreeCreate(const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsFunc pfnGetBounds)
Create a new quadtree.
Definition: cpl_quad_tree.cpp:138
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
void(* CPLQuadTreeGetBoundsExFunc)(const void *hFeature, void *pUserData, CPLRectObj *pBounds)
CPLQuadTreeGetBoundsExFunc.
Definition: cpl_quad_tree.h:55
void CPLQuadTreeInsert(CPLQuadTree *hQuadtree, void *hFeature)
Insert a feature into a quadtree.
Definition: cpl_quad_tree.cpp:330
int(* CPLQuadTreeForeachFunc)(void *pElt, void *pUserData)
CPLQuadTreeForeachFunc.
Definition: cpl_quad_tree.h:59
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
void(* CPLQuadTreeGetBoundsFunc)(const void *hFeature, CPLRectObj *pBounds)
CPLQuadTreeGetBoundsFunc.
Definition: cpl_quad_tree.h:52
void CPLQuadTreeGetStats(const CPLQuadTree *hQuadtree, int *pnFeatureCount, int *pnNodeCount, int *pnMaxDepth, int *pnMaxBucketCapacity)
Get stats.
Definition: cpl_quad_tree.cpp:1123
void CPLQuadTreeDump(const CPLQuadTree *hQuadtree, CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc, void *pUserData)
Dump quad tree.
Definition: cpl_quad_tree.cpp:1090
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
void CPLQuadTreeSetBucketCapacity(CPLQuadTree *hQuadtree, int nBucketCapacity)
Set the maximum capacity of a node of a quadtree.
Definition: cpl_quad_tree.cpp:296
void CPLQuadTreeSetMaxDepth(CPLQuadTree *hQuadtree, int nMaxDepth)
Set the maximum depth of a quadtree.
Definition: cpl_quad_tree.cpp:278
void CPLQuadTreeDestroy(CPLQuadTree *hQuadtree)
Destroy a quadtree.
Definition: cpl_quad_tree.cpp:498
struct _CPLQuadTree CPLQuadTree
Opaque type for a quad tree.
Definition: cpl_quad_tree.h:49
void CPLQuadTreeInsertWithBounds(CPLQuadTree *hQuadtree, void *hFeature, const CPLRectObj *psBounds)
Insert a feature into a quadtree.
Definition: cpl_quad_tree.cpp:359
void(* CPLQuadTreeDumpFeatureFunc)(const void *hFeature, int nIndentLevel, void *pUserData)
CPLQuadTreeDumpFeatureFunc.
Definition: cpl_quad_tree.h:61
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
int CPLQuadTreeGetAdvisedMaxDepth(int nExpectedFeatures)
Returns the optimal depth of a quadtree to hold nExpectedFeatures.
Definition: cpl_quad_tree.cpp:231
Describe a rectangle.
Definition: cpl_quad_tree.h:41
double minx
Minimum x.
Definition: cpl_quad_tree.h:42
double maxy
Maximum y.
Definition: cpl_quad_tree.h:45
double miny
Minimum y.
Definition: cpl_quad_tree.h:43
double maxx
Maximum x.
Definition: cpl_quad_tree.h:44