00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
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
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
00080 Coordinate properIntersectionPoint;
00081 LineIntersector *li;
00082 bool includeProper;
00083 bool recordIsolated;
00084 bool isSelfIntersection;
00085
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
00111
00112 };
00113
00114
00115
00116
00117
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;
00154 protected:
00155 SweepLineEventOBJ* obj;
00156 private:
00157 double xValue;
00158 int eventType;
00159 SweepLineEvent *insertEvent;
00160 int deleteEventIndex;
00161 };
00162
00163 class MonotoneChainIndexer{
00164 public:
00165
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;
00186
00187
00188 vector<int>* startIndex;
00189
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
00209
00210
00211
00212
00213
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
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
00246
00247
00248
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
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