00001 /********************************************************************** 00002 * $Id: indexChain.h,v 1.4 2004/07/19 13:19:31 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.4 2004/07/19 13:19:31 strk 00017 * Documentation fixes 00018 * 00019 * Revision 1.3 2004/07/13 08:33:52 strk 00020 * Added missing virtual destructor to virtual classes. 00021 * Fixed implicit unsigned int -> int casts 00022 * 00023 * Revision 1.2 2004/07/08 19:34:49 strk 00024 * Mirrored JTS interface of CoordinateSequence, factory and 00025 * default implementations. 00026 * Added DefaultCoordinateSequenceFactory::instance() function. 00027 * 00028 * Revision 1.1 2004/07/02 13:20:42 strk 00029 * Header files moved under geos/ dir. 00030 * 00031 * Revision 1.8 2004/05/27 09:53:49 strk 00032 * MonotoneChainOverlapAction::overlap(*) funx made virtual 00033 * as they are supposed to be. 00034 * 00035 * Revision 1.7 2004/03/25 02:23:55 ybychkov 00036 * All "index/*" packages upgraded to JTS 1.4 00037 * 00038 * Revision 1.6 2003/11/07 01:23:42 pramsey 00039 * Add standard CVS headers licence notices and copyrights to all cpp and h 00040 * files. 00041 * 00042 * 00043 **********************************************************************/ 00044 00045 00046 #ifndef GEOS_INDEXCHAIN_H 00047 #define GEOS_INDEXCHAIN_H 00048 00049 #include <memory> 00050 #include <vector> 00051 #include <geos/platform.h> 00052 #include <geos/geom.h> 00053 00054 using namespace std; 00055 00056 namespace geos { 00057 00058 class indexMonotoneChain; 00059 /* 00060 * The action for the internal iterator for performing 00061 * envelope select queries on a MonotoneChain 00062 */ 00063 class MonotoneChainSelectAction { 00064 protected: 00065 LineSegment *selectedSegment; 00066 public: 00067 MonotoneChainSelectAction(); 00068 virtual ~MonotoneChainSelectAction(); 00072 virtual void select(indexMonotoneChain *mc,int start); 00078 virtual void select(LineSegment *newSeg){} 00079 // these envelopes are used during the MonotoneChain search process 00080 Envelope *tempEnv1; 00081 }; 00082 00083 /* 00084 * The action for the internal iterator for performing 00085 * overlap queries on a MonotoneChain 00086 */ 00087 class MonotoneChainOverlapAction { 00088 protected: 00089 LineSegment *overlapSeg1; 00090 LineSegment *overlapSeg2; 00091 public: 00092 MonotoneChainOverlapAction(); 00093 virtual ~MonotoneChainOverlapAction(); 00094 00101 virtual void overlap(indexMonotoneChain *mc1,int start1,indexMonotoneChain *mc2,int start2); 00108 virtual void overlap(LineSegment *newSeg1,LineSegment *newSeg2){} 00109 // these envelopes are used during the MonotoneChain search process 00110 Envelope *tempEnv1; 00111 Envelope *tempEnv2; 00112 }; 00113 00114 00115 /* 00116 * MonotoneChains are a way of partitioning the segments of a linestring to 00117 * allow for fast searching of intersections. 00118 * They have the following properties: 00119 * <ol> 00120 * <li>the segments within a monotone chain will never intersect each other 00121 * <li>the envelope of any contiguous subset of the segments in a monotone chain 00122 * is equal to the envelope of the endpoints of the subset. 00123 * </ol> 00124 * Property 1 means that there is no need to test pairs of segments from within 00125 * the same monotone chain for intersection. 00126 * Property 2 allows 00127 * binary search to be used to find the intersection points of two monotone chains. 00128 * For many types of real-world data, these properties eliminate a large number of 00129 * segment comparisons, producing substantial speed gains. 00130 * <p> 00131 * One of the goals of this implementation of MonotoneChains is to be 00132 * as space and time efficient as possible. One design choice that aids this 00133 * is that a MonotoneChain is based on a subarray of a list of points. 00134 * This means that new arrays of points (potentially very large) do not 00135 * have to be allocated. 00136 * <p> 00137 * 00138 * MonotoneChains support the following kinds of queries: 00139 * <ul> 00140 * <li>Envelope select: determine all the segments in the chain which 00141 * intersect a given envelope 00142 * <li>Overlap: determine all the pairs of segments in two chains whose 00143 * envelopes overlap 00144 * </ul> 00145 * 00146 * This implementation of MonotoneChains uses the concept of internal iterators 00147 * to return the resultsets for the above queries. 00148 * This has time and space advantages, since it 00149 * is not necessary to build lists of instantiated objects to represent the segments 00150 * returned by the query. 00151 * However, it does mean that the queries are not thread-safe. 00152 * 00153 * @version 1.4 00154 */ 00155 class indexMonotoneChain { 00156 public: 00157 indexMonotoneChain(CoordinateSequence *newPts,int nstart,int nend, void* nContext); 00158 ~indexMonotoneChain(); 00159 Envelope* getEnvelope(); 00160 int getStartIndex(); 00161 int getEndIndex(); 00162 void getLineSegment(int index,LineSegment *ls); 00167 CoordinateSequence* getCoordinates(); 00172 void select(Envelope *searchEnv,MonotoneChainSelectAction *mcs); 00173 void computeOverlaps(indexMonotoneChain *mc,MonotoneChainOverlapAction *mco); 00174 void setId(int nId); 00175 int getId(); 00176 void* getContext(); 00177 00178 private: 00179 void computeSelect(Envelope *searchEnv,int start0,int end0,MonotoneChainSelectAction *mcs); 00180 void computeOverlaps(int start0,int end0,indexMonotoneChain *mc,int start1,int end1,MonotoneChainOverlapAction *mco); 00181 CoordinateSequence *pts; 00182 int start, end; 00183 Envelope *env; 00184 void *context;// user-defined information 00185 int id; // useful for optimizing chain comparisons 00186 }; 00187 00188 /* 00189 * A MonotoneChainBuilder implements functions to determine the monotone chains 00190 * in a sequence of points. 00191 */ 00192 class MonotoneChainBuilder { 00193 public: 00194 // static int[] toIntArray(List list); //Not needed 00195 MonotoneChainBuilder(){} 00196 static vector<indexMonotoneChain*>* getChains(CoordinateSequence *pts); 00201 static vector<indexMonotoneChain*>* getChains(CoordinateSequence *pts,void* context); 00208 static vector<int>* getChainStartIndices(CoordinateSequence *pts); 00212 static int findChainEnd(CoordinateSequence *pts,int start); 00213 }; 00214 } 00215 #endif 00216