OGR
|
00001 /********************************************************************** 00002 * $Id: cpl_quad_tree.h 15067 2008-07-28 22:08:58Z 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 * 00013 * Permission is hereby granted, free of charge, to any person obtaining a 00014 * copy of this software and associated documentation files (the "Software"), 00015 * to deal in the Software without restriction, including without limitation 00016 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 00017 * and/or sell copies of the Software, and to permit persons to whom the 00018 * Software is furnished to do so, subject to the following conditions: 00019 * 00020 * The above copyright notice and this permission notice shall be included 00021 * in all copies or substantial portions of the Software. 00022 * 00023 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 00024 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 00025 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 00026 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 00027 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 00028 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 00029 * DEALINGS IN THE SOFTWARE. 00030 ****************************************************************************/ 00031 00032 #ifndef _CPL_QUAD_TREE_H_INCLUDED 00033 #define _CPL_QUAD_TREE_H_INCLUDED 00034 00035 #include "cpl_port.h" 00036 00048 CPL_C_START 00049 00050 /* Types */ 00051 00052 typedef struct { 00053 double minx, miny, maxx, maxy; 00054 } CPLRectObj; 00055 00056 typedef struct _CPLQuadTree CPLQuadTree; 00057 00058 typedef void (*CPLQuadTreeGetBoundsFunc)(const void* hFeature, CPLRectObj* pBounds); 00059 typedef int (*CPLQuadTreeForeachFunc)(void* pElt, void* pUserData); 00060 typedef void (*CPLQuadTreeDumpFeatureFunc)(const void* hFeature, int nIndentLevel, void* pUserData); 00061 00062 /* Functions */ 00063 00064 CPLQuadTree CPL_DLL *CPLQuadTreeCreate(const CPLRectObj* pGlobalBounds, 00065 CPLQuadTreeGetBoundsFunc pfnGetBounds); 00066 void CPL_DLL CPLQuadTreeDestroy(CPLQuadTree *hQuadtree); 00067 00068 void CPL_DLL CPLQuadTreeSetBucketCapacity(CPLQuadTree *hQuadtree, 00069 int nBucketCapacity); 00070 int CPL_DLL CPLQuadTreeGetAdvisedMaxDepth(int nExpectedFeatures); 00071 void CPL_DLL CPLQuadTreeSetMaxDepth(CPLQuadTree *hQuadtree, 00072 int nMaxDepth); 00073 00074 void CPL_DLL CPLQuadTreeInsert(CPLQuadTree *hQuadtree, 00075 void* hFeature); 00076 00077 void CPL_DLL **CPLQuadTreeSearch(const CPLQuadTree *hQuadtree, 00078 const CPLRectObj* pAoi, 00079 int* pnFeatureCount); 00080 00081 void CPL_DLL CPLQuadTreeForeach(const CPLQuadTree *hQuadtree, 00082 CPLQuadTreeForeachFunc pfnForeach, 00083 void* pUserData); 00084 00085 void CPL_DLL CPLQuadTreeDump(const CPLQuadTree *hQuadtree, 00086 CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc, 00087 void* pUserData); 00088 void CPL_DLL CPLQuadTreeGetStats(const CPLQuadTree *hQuadtree, 00089 int* pnFeatureCount, 00090 int* pnNodeCount, 00091 int* pnMaxDepth, 00092 int* pnMaxBucketCapacity); 00093 00094 CPL_C_END 00095 00096 #endif