Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | Related Pages

indexChain.h

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 

Generated on Fri Nov 26 21:30:45 2004 for GEOS by  doxygen 1.3.9.1