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

geomgraphindex.h

00001 /**********************************************************************
00002  * $Id: geomgraphindex.h,v 1.3 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: geomgraphindex.h,v $
00016  * Revision 1.3  2004/07/19 13:19:31  strk
00017  * Documentation fixes
00018  *
00019  * Revision 1.2  2004/07/08 19:34:49  strk
00020  * Mirrored JTS interface of CoordinateSequence, factory and
00021  * default implementations.
00022  * Added DefaultCoordinateSequenceFactory::instance() function.
00023  *
00024  * Revision 1.1  2004/07/02 13:20:42  strk
00025  * Header files moved under geos/ dir.
00026  *
00027  * Revision 1.2  2004/04/04 06:29:11  ybychkov
00028  * "planargraph" and "geom/utill" upgraded to JTS 1.4
00029  *
00030  * Revision 1.1  2004/03/19 09:48:45  ybychkov
00031  * "geomgraph" and "geomgraph/indexl" upgraded to JTS 1.4
00032  *
00033  * Revision 1.20  2003/11/07 01:23:42  pramsey
00034  * Add standard CVS headers licence notices and copyrights to all cpp and h
00035  * files.
00036  *
00037  *
00038  **********************************************************************/
00039 
00040 
00041 #ifndef GEOS_GEOMGRAPH_INDEX_H
00042 #define GEOS_GEOMGRAPH_INDEX_H
00043 
00044 #include <memory>
00045 #include <geos/geomgraph.h>
00046 #include <geos/geom.h>
00047 #include <vector>
00048 #include <geos/geosAlgorithm.h>
00049 #include <geos/platform.h>
00050 
00051 namespace geos {
00052 
00053 class Edge;
00054 class Node;
00055 class CoordinateSequence;
00056 
00057 class SegmentIntersector{
00058 public:
00059         static bool isAdjacentSegments(int i1,int i2);
00060         // testing only
00061         int numTests;
00062         SegmentIntersector();
00063         virtual ~SegmentIntersector();
00064         SegmentIntersector(LineIntersector *newLi,bool newIncludeProper,bool newRecordIsolated);
00065         void setBoundaryNodes(vector<Node*> *bdyNodes0,vector<Node*> *bdyNodes1);
00066         Coordinate& getProperIntersectionPoint();
00067         bool hasIntersection();
00068         bool hasProperIntersection();
00069         bool hasProperInteriorIntersection();
00070         void addIntersections(Edge *e0,int segIndex0,Edge *e1,int segIndex1);
00071 private:
00076         bool hasIntersectionVar;
00077         bool hasProper;
00078         bool hasProperInterior;
00079         // the proper intersection point found
00080         Coordinate properIntersectionPoint;
00081         LineIntersector *li;
00082         bool includeProper;
00083         bool recordIsolated;
00084         bool isSelfIntersection;
00085         //bool intersectionFound;
00086         int numIntersections;
00087         vector<vector<Node*>*> *bdyNodes;
00088         bool isTrivialIntersection(Edge *e0,int segIndex0,Edge *e1, int segIndex1);
00089         bool isBoundaryPoint(LineIntersector *li,vector<vector<Node*>*> *tstBdyNodes);
00090         bool isBoundaryPoint(LineIntersector *li,vector<Node*> *tstBdyNodes);
00091 };
00092 
00093 class EdgeSetIntersector{
00094 public:
00103         virtual void computeIntersections(vector<Edge*> *edges,SegmentIntersector *si,bool testAllSegments)=0;
00107         virtual void computeIntersections(vector<Edge*> *edges0,vector<Edge*> *edges1,SegmentIntersector *si)=0;
00108         virtual ~EdgeSetIntersector(){};
00109 protected:
00110 //      vector<Edge*>* edgesZero;
00111 //      vector<Edge*>* edgesOne;
00112 };
00113 //
00114 // This is here so that SweepLineEvent constructor
00115 // can use it as argument type. 
00116 // Both  SweepLineSegment and MonotoneChain will
00117 // inherit from it.
00118 class SweepLineEventOBJ {
00119 public:
00120         virtual ~SweepLineEventOBJ(){};
00121 };
00122 
00123 
00124 class SweepLineSegment: public SweepLineEventOBJ {
00125 public:
00126         SweepLineSegment(Edge *newEdge,int newPtIndex);
00127         ~SweepLineSegment();
00128         double getMinX();
00129         double getMaxX();
00130         void computeIntersections(SweepLineSegment *ss,SegmentIntersector *si);
00131 protected:
00132         Edge *edge;
00133         const CoordinateSequence* pts;
00134         int ptIndex;
00135 };
00136 
00137 class SweepLineEvent{
00138 public:
00139         enum {
00140                 INSERT=1,
00141                 DELETE
00142         };
00143         SweepLineEvent(void* newEdgeSet,double x,SweepLineEvent *newInsertEvent,SweepLineEventOBJ *newObj);
00144         virtual ~SweepLineEvent();
00145         bool isInsert();
00146         bool isDelete();
00147         SweepLineEvent* getInsertEvent();
00148         int getDeleteEventIndex();
00149         void setDeleteEventIndex(int newDeleteEventIndex);
00150         SweepLineEventOBJ* getObject() const;
00151         int compareTo(SweepLineEvent *sle);
00152         string print();
00153         void* edgeSet;    // used for red-blue intersection detection
00154 protected:
00155         SweepLineEventOBJ* obj;
00156 private:
00157         double xValue;
00158         int eventType;
00159         SweepLineEvent *insertEvent; // null if this is an INSERT event
00160         int deleteEventIndex;
00161 };
00162 
00163 class MonotoneChainIndexer{
00164 public:
00165 //      public static int[] toIntArray(List list); //Not needed
00166         MonotoneChainIndexer(){};
00167         vector<int>* getChainStartIndices(const CoordinateSequence* pts);
00168 private:
00169         int findChainEnd(const CoordinateSequence* pts,int start);
00170 };
00171 
00172 class MonotoneChainEdge{
00173 public:
00174         MonotoneChainEdge();
00175         ~MonotoneChainEdge();
00176         MonotoneChainEdge(Edge *newE);
00177         const CoordinateSequence* getCoordinates();
00178         vector<int>* getStartIndexes();
00179         double getMinX(int chainIndex);
00180         double getMaxX(int chainIndex);
00181         void computeIntersects(MonotoneChainEdge *mce,SegmentIntersector *si);
00182         void computeIntersectsForChain(int chainIndex0,MonotoneChainEdge *mce,int chainIndex1,SegmentIntersector *si);
00183 protected:
00184         Edge *e;
00185         const CoordinateSequence* pts; // cache a reference to the coord array, for efficiency
00186         // the lists of start/end indexes of the monotone chains.
00187         // Includes the end point of the edge as a sentinel
00188         vector<int>* startIndex;
00189         // these envelopes are created once and reused
00190         Envelope *env1;
00191         Envelope *env2;
00192 private:
00193         void computeIntersectsForChain(int start0,int end0,MonotoneChainEdge *mce,
00194                                                                         int start1,int end1,SegmentIntersector *ei);
00195 };
00196 
00197 class MonotoneChain: public SweepLineEventOBJ {
00198 public:
00199         MonotoneChain(MonotoneChainEdge *newMce,int newChainIndex);
00200         ~MonotoneChain();
00201         void computeIntersections(MonotoneChain *mc,SegmentIntersector *si);
00202 protected:
00203         MonotoneChainEdge *mce;
00204         int chainIndex;
00205 };
00206 
00207 /*
00208  * Finds all intersections in one or two sets of edges,
00209  * using an x-axis sweepline algorithm in conjunction with Monotone Chains.
00210  * While still O(n^2) in the worst case, this algorithm
00211  * drastically improves the average-case time.
00212  * The use of MonotoneChains as the items in the index
00213  * seems to offer an improvement in performance over a sweep-line alone.
00214  */
00215 class SimpleMCSweepLineIntersector: public EdgeSetIntersector {
00216 public:
00217         SimpleMCSweepLineIntersector();
00218         virtual ~SimpleMCSweepLineIntersector();
00219         void computeIntersections(vector<Edge*> *edges,SegmentIntersector *si,bool testAllSegments);
00220         void computeIntersections(vector<Edge*> *edges0,vector<Edge*> *edges1,SegmentIntersector *si);
00221 protected:
00222         vector<SweepLineEvent*>* events;
00223         // statistics information
00224         int nOverlaps;
00225 private:
00226         void add(vector<Edge*> *edges);
00227         void add(vector<Edge*> *edges,void* edgeSet);
00228         void add(Edge *edge,void* edgeSet);
00229         void prepareEvents();
00230         void computeIntersections(SegmentIntersector *si);
00231         void processOverlaps(int start,int end,SweepLineEvent *ev0,SegmentIntersector *si);
00232 };
00233 
00234 class SimpleEdgeSetIntersector: public EdgeSetIntersector {
00235 public:
00236         SimpleEdgeSetIntersector();
00237         void computeIntersections(vector<Edge*> *edges,SegmentIntersector *si,bool testAllSegments);
00238         void computeIntersections(vector<Edge*> *edges0,vector<Edge*> *edges1,SegmentIntersector *si);
00239 private:
00240         int nOverlaps;
00241         void computeIntersects(Edge *e0,Edge *e1,SegmentIntersector *si);
00242 };
00243 
00244 /*
00245  * Finds all intersections in one or two sets of edges,
00246  * using a simple x-axis sweepline algorithm.
00247  * While still O(n^2) in the worst case, this algorithm
00248  * drastically improves the average-case time.
00249  */
00250 class SimpleSweepLineIntersector: public EdgeSetIntersector {
00251 public:
00252         SimpleSweepLineIntersector();
00253         virtual ~SimpleSweepLineIntersector();
00254         void computeIntersections(vector<Edge*> *edges,SegmentIntersector *si,bool testAllSegments);
00255         void computeIntersections(vector<Edge*> *edges0,vector<Edge*> *edges1,SegmentIntersector *si);
00256 private:
00257         void add(vector<Edge*> *edges);
00258         vector<SweepLineEvent*>* events;
00259         // statistics information
00260         int nOverlaps;
00261         void add(vector<Edge*> *edges,void* edgeSet);
00262         void add(Edge *edge,void* edgeSet);
00263         void prepareEvents();
00264         void computeIntersections(SegmentIntersector *si);
00265         void processOverlaps(int start,int end,SweepLineEvent *ev0,SegmentIntersector *si);
00266 };
00267 
00268 bool sleLessThen(SweepLineEvent *first,SweepLineEvent *second);
00269 }
00270 #endif

Generated on Tue Jan 10 01:34:44 2006 for GEOS by  doxygen 1.4.4