geomgraphindex.h

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

Generated on Fri Nov 16 11:23:17 2007 for GEOS by  doxygen 1.5.3-20071008