GDAL
|
00001 /********************************************************************** 00002 * $Id: cpl_quad_tree.h 27044 2014-03-16 23:41:27Z rouault $ 00003 * 00004 * Project: CPL - Common Portability Library 00005 * Purpose: Implementation of quadtree building and searching functions. 00006 * Derived from shapelib and mapserver implementations 00007 * Author: Frank Warmerdam, warmerdam@pobox.com 00008 * Even Rouault, <even dot rouault at mines dash paris dot org> 00009 * 00010 ****************************************************************************** 00011 * Copyright (c) 1999-2008, Frank Warmerdam 00012 * Copyright (c) 2008-2014, Even Rouault <even dot rouault at mines-paris dot org> 00013 * 00014 * Permission is hereby granted, free of charge, to any person obtaining a 00015 * copy of this software and associated documentation files (the "Software"), 00016 * to deal in the Software without restriction, including without limitation 00017 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 00018 * and/or sell copies of the Software, and to permit persons to whom the 00019 * Software is furnished to do so, subject to the following conditions: 00020 * 00021 * The above copyright notice and this permission notice shall be included 00022 * in all copies or substantial portions of the Software. 00023 * 00024 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 00025 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 00026 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 00027 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 00028 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 00029 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 00030 * DEALINGS IN THE SOFTWARE. 00031 ****************************************************************************/ 00032 00033 #ifndef _CPL_QUAD_TREE_H_INCLUDED 00034 #define _CPL_QUAD_TREE_H_INCLUDED 00035 00036 #include "cpl_port.h" 00037 00049 CPL_C_START 00050 00051 /* Types */ 00052 00053 typedef struct { 00054 double minx, miny, maxx, maxy; 00055 } CPLRectObj; 00056 00057 typedef struct _CPLQuadTree CPLQuadTree; 00058 00059 typedef void (*CPLQuadTreeGetBoundsFunc)(const void* hFeature, CPLRectObj* pBounds); 00060 typedef int (*CPLQuadTreeForeachFunc)(void* pElt, void* pUserData); 00061 typedef void (*CPLQuadTreeDumpFeatureFunc)(const void* hFeature, int nIndentLevel, void* pUserData); 00062 00063 /* Functions */ 00064 00065 CPLQuadTree CPL_DLL *CPLQuadTreeCreate(const CPLRectObj* pGlobalBounds, 00066 CPLQuadTreeGetBoundsFunc pfnGetBounds); 00067 void CPL_DLL CPLQuadTreeDestroy(CPLQuadTree *hQuadtree); 00068 00069 void CPL_DLL CPLQuadTreeSetBucketCapacity(CPLQuadTree *hQuadtree, 00070 int nBucketCapacity); 00071 int CPL_DLL CPLQuadTreeGetAdvisedMaxDepth(int nExpectedFeatures); 00072 void CPL_DLL CPLQuadTreeSetMaxDepth(CPLQuadTree *hQuadtree, 00073 int nMaxDepth); 00074 00075 void CPL_DLL CPLQuadTreeInsert(CPLQuadTree *hQuadtree, 00076 void* hFeature); 00077 void CPL_DLL CPLQuadTreeInsertWithBounds(CPLQuadTree *hQuadtree, 00078 void* hFeature, 00079 const CPLRectObj* psBounds); 00080 00081 void CPL_DLL **CPLQuadTreeSearch(const CPLQuadTree *hQuadtree, 00082 const CPLRectObj* pAoi, 00083 int* pnFeatureCount); 00084 00085 void CPL_DLL CPLQuadTreeForeach(const CPLQuadTree *hQuadtree, 00086 CPLQuadTreeForeachFunc pfnForeach, 00087 void* pUserData); 00088 00089 void CPL_DLL CPLQuadTreeDump(const CPLQuadTree *hQuadtree, 00090 CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc, 00091 void* pUserData); 00092 void CPL_DLL CPLQuadTreeGetStats(const CPLQuadTree *hQuadtree, 00093 int* pnFeatureCount, 00094 int* pnNodeCount, 00095 int* pnMaxDepth, 00096 int* pnMaxBucketCapacity); 00097 00098 CPL_C_END 00099 00100 #endif