00001 /********************************************************************** 00002 * $Id: indexChain.h,v 1.6 2004/11/04 19:08:06 strk Exp $ 00003 * 00004 * GEOS - Geometry Engine Open Source 00005 * http://geos.refractions.net 00006 * 00007 * Copyright (C) 2001-2002 Vivid Solutions Inc. 00008 * 00009 * This is free software; you can redistribute and/or modify it under 00010 * the terms of the GNU Lesser General Public Licence as published 00011 * by the Free Software Foundation. 00012 * See the COPYING file for more information. 00013 * 00014 ********************************************************************** 00015 * $Log: indexChain.h,v $ 00016 * Revision 1.6 2004/11/04 19:08:06 strk 00017 * Cleanups, initializers list, profiling. 00018 * 00019 * Revision 1.5 2004/10/26 17:46:18 strk 00020 * Removed slash-stars in comments to remove annoying compiler warnings. 00021 * 00022 * Revision 1.4 2004/07/19 13:19:31 strk 00023 * Documentation fixes 00024 * 00025 * Revision 1.3 2004/07/13 08:33:52 strk 00026 * Added missing virtual destructor to virtual classes. 00027 * Fixed implicit unsigned int -> int casts 00028 * 00029 * Revision 1.2 2004/07/08 19:34:49 strk 00030 * Mirrored JTS interface of CoordinateSequence, factory and 00031 * default implementations. 00032 * Added DefaultCoordinateSequenceFactory::instance() function. 00033 * 00034 * Revision 1.1 2004/07/02 13:20:42 strk 00035 * Header files moved under geos/ dir. 00036 * 00037 * Revision 1.8 2004/05/27 09:53:49 strk 00038 * MonotoneChainOverlapAction::overlap(*) funx made virtual 00039 * as they are supposed to be. 00040 * 00041 * Revision 1.7 2004/03/25 02:23:55 ybychkov 00042 * All "index/" packages upgraded to JTS 1.4 00043 * 00044 * Revision 1.6 2003/11/07 01:23:42 pramsey 00045 * Add standard CVS headers licence notices and copyrights to all cpp and h 00046 * files. 00047 * 00048 * 00049 **********************************************************************/ 00050 00051 00052 #ifndef GEOS_INDEXCHAIN_H 00053 #define GEOS_INDEXCHAIN_H 00054 00055 #include <memory> 00056 #include <vector> 00057 #include <geos/platform.h> 00058 #include <geos/geom.h> 00059 00060 using namespace std; 00061 00062 namespace geos { 00063 00064 class indexMonotoneChain; 00065 /* 00066 * The action for the internal iterator for performing 00067 * envelope select queries on a MonotoneChain 00068 */ 00069 class MonotoneChainSelectAction { 00070 protected: 00071 LineSegment *selectedSegment; 00072 public: 00073 MonotoneChainSelectAction(); 00074 virtual ~MonotoneChainSelectAction(); 00078 virtual void select(indexMonotoneChain *mc,int start); 00084 virtual void select(LineSegment *newSeg){} 00085 // these envelopes are used during the MonotoneChain search process 00086 Envelope *tempEnv1; 00087 }; 00088 00089 /* 00090 * The action for the internal iterator for performing 00091 * overlap queries on a MonotoneChain 00092 */ 00093 class MonotoneChainOverlapAction { 00094 protected: 00095 LineSegment *overlapSeg1; 00096 LineSegment *overlapSeg2; 00097 public: 00098 MonotoneChainOverlapAction(); 00099 virtual ~MonotoneChainOverlapAction(); 00100 00107 virtual void overlap(indexMonotoneChain *mc1,int start1,indexMonotoneChain *mc2,int start2); 00114 virtual void overlap(LineSegment *newSeg1,LineSegment *newSeg2){} 00115 // these envelopes are used during the MonotoneChain search process 00116 Envelope *tempEnv1; 00117 Envelope *tempEnv2; 00118 }; 00119 00120 00121 /* 00122 * MonotoneChains are a way of partitioning the segments of a linestring to 00123 * allow for fast searching of intersections. 00124 * They have the following properties: 00125 * <ol> 00126 * <li>the segments within a monotone chain will never intersect each other 00127 * <li>the envelope of any contiguous subset of the segments in a monotone chain 00128 * is equal to the envelope of the endpoints of the subset. 00129 * </ol> 00130 * Property 1 means that there is no need to test pairs of segments from within 00131 * the same monotone chain for intersection. 00132 * Property 2 allows 00133 * binary search to be used to find the intersection points of two monotone chains. 00134 * For many types of real-world data, these properties eliminate a large number of 00135 * segment comparisons, producing substantial speed gains. 00136 * <p> 00137 * One of the goals of this implementation of MonotoneChains is to be 00138 * as space and time efficient as possible. One design choice that aids this 00139 * is that a MonotoneChain is based on a subarray of a list of points. 00140 * This means that new arrays of points (potentially very large) do not 00141 * have to be allocated. 00142 * <p> 00143 * 00144 * MonotoneChains support the following kinds of queries: 00145 * <ul> 00146 * <li>Envelope select: determine all the segments in the chain which 00147 * intersect a given envelope 00148 * <li>Overlap: determine all the pairs of segments in two chains whose 00149 * envelopes overlap 00150 * </ul> 00151 * 00152 * This implementation of MonotoneChains uses the concept of internal iterators 00153 * to return the resultsets for the above queries. 00154 * This has time and space advantages, since it 00155 * is not necessary to build lists of instantiated objects to represent the segments 00156 * returned by the query. 00157 * However, it does mean that the queries are not thread-safe. 00158 * 00159 * @version 1.4 00160 */ 00161 class indexMonotoneChain { 00162 public: 00163 indexMonotoneChain(CoordinateSequence *newPts,int nstart,int nend, void* nContext); 00164 ~indexMonotoneChain(); 00165 Envelope* getEnvelope(); 00166 int getStartIndex(); 00167 int getEndIndex(); 00168 void getLineSegment(int index,LineSegment *ls); 00173 CoordinateSequence* getCoordinates(); 00178 void select(Envelope *searchEnv,MonotoneChainSelectAction *mcs); 00179 void computeOverlaps(indexMonotoneChain *mc,MonotoneChainOverlapAction *mco); 00180 00181 void setId(int nId); 00182 00183 int getId(); 00184 00185 void* getContext(); 00186 00187 private: 00188 void computeSelect(Envelope *searchEnv,int start0,int end0,MonotoneChainSelectAction *mcs); 00189 void computeOverlaps(int start0,int end0,indexMonotoneChain *mc,int start1,int end1,MonotoneChainOverlapAction *mco); 00190 CoordinateSequence *pts; 00191 int start, end; 00192 Envelope *env; 00193 void *context;// user-defined information 00194 int id; // useful for optimizing chain comparisons 00195 }; 00196 00197 /* 00198 * A MonotoneChainBuilder implements functions to determine the monotone chains 00199 * in a sequence of points. 00200 */ 00201 class MonotoneChainBuilder { 00202 public: 00203 // static int[] toIntArray(List list); //Not needed 00204 MonotoneChainBuilder(){} 00205 static vector<indexMonotoneChain*>* getChains(CoordinateSequence *pts); 00210 static vector<indexMonotoneChain*>* getChains(CoordinateSequence *pts,void* context); 00217 static vector<int>* getChainStartIndices(CoordinateSequence *pts); 00221 static int findChainEnd(CoordinateSequence *pts,int start); 00222 }; 00223 } 00224 #endif 00225