1 /********************************************************************** 2 * $Id: cpl_quad_tree.h 355b41831cd2685c85d1aabe5b95665a2c6e99b7 2019-06-19 17:07:04 +0200 Even Rouault $ 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 * Permission is hereby granted, free of charge, to any person obtaining a 15 * copy of this software and associated documentation files (the "Software"), 16 * to deal in the Software without restriction, including without limitation 17 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 18 * and/or sell copies of the Software, and to permit persons to whom the 19 * Software is furnished to do so, subject to the following conditions: 20 * 21 * The above copyright notice and this permission notice shall be included 22 * in all copies or substantial portions of the Software. 23 * 24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 25 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 26 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 27 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 28 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 29 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 30 * DEALINGS IN THE SOFTWARE. 31 ****************************************************************************/ 32 33 #ifndef CPL_QUAD_TREE_H_INCLUDED 34 #define CPL_QUAD_TREE_H_INCLUDED 35 36 #include "cpl_port.h" 37 38 /** 39 * \file cpl_quad_tree.h 40 * 41 * Quad tree implementation. 42 * 43 * A quadtree is a tree data structure in which each internal node 44 * has up to four children. Quadtrees are most often used to partition 45 * a two dimensional space by recursively subdividing it into four 46 * quadrants or regions 47 */ 48 49 CPL_C_START 50 51 /* Types */ 52 53 /** Describe a rectangle */ 54 typedef struct { 55 double minx; /**< Minimum x */ 56 double miny; /**< Minimum y */ 57 double maxx; /**< Maximum x */ 58 double maxy; /**< Maximum y */ 59 } CPLRectObj; 60 61 /** Opaque type for a quad tree */ 62 typedef struct _CPLQuadTree CPLQuadTree; 63 64 /** CPLQuadTreeGetBoundsFunc */ 65 typedef void (*CPLQuadTreeGetBoundsFunc)(const void* hFeature, CPLRectObj* pBounds); 66 /** CPLQuadTreeForeachFunc */ 67 typedef int (*CPLQuadTreeForeachFunc)(void* pElt, void* pUserData); 68 /** CPLQuadTreeDumpFeatureFunc */ 69 typedef void (*CPLQuadTreeDumpFeatureFunc)(const void* hFeature, int nIndentLevel, void* pUserData); 70 71 /* Functions */ 72 73 CPLQuadTree CPL_DLL *CPLQuadTreeCreate(const CPLRectObj* pGlobalBounds, 74 CPLQuadTreeGetBoundsFunc pfnGetBounds); 75 void CPL_DLL CPLQuadTreeDestroy(CPLQuadTree *hQuadtree); 76 77 void CPL_DLL CPLQuadTreeSetBucketCapacity(CPLQuadTree *hQuadtree, 78 int nBucketCapacity); 79 int CPL_DLL CPLQuadTreeGetAdvisedMaxDepth(int nExpectedFeatures); 80 void CPL_DLL CPLQuadTreeSetMaxDepth(CPLQuadTree *hQuadtree, 81 int nMaxDepth); 82 83 void CPL_DLL CPLQuadTreeInsert(CPLQuadTree *hQuadtree, 84 void* hFeature); 85 void CPL_DLL CPLQuadTreeInsertWithBounds(CPLQuadTree *hQuadtree, 86 void* hFeature, 87 const CPLRectObj* psBounds); 88 89 void CPL_DLL **CPLQuadTreeSearch(const CPLQuadTree *hQuadtree, 90 const CPLRectObj* pAoi, 91 int* pnFeatureCount); 92 93 void CPL_DLL CPLQuadTreeForeach(const CPLQuadTree *hQuadtree, 94 CPLQuadTreeForeachFunc pfnForeach, 95 void* pUserData); 96 97 void CPL_DLL CPLQuadTreeDump(const CPLQuadTree *hQuadtree, 98 CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc, 99 void* pUserData); 100 void CPL_DLL CPLQuadTreeGetStats(const CPLQuadTree *hQuadtree, 101 int* pnFeatureCount, 102 int* pnNodeCount, 103 int* pnMaxDepth, 104 int* pnMaxBucketCapacity); 105 106 CPL_C_END 107 108 #endif 109