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
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078 #ifndef GEOS_NODING_H
00079 #define GEOS_NODING_H
00080
00081 #include <string>
00082 #include <vector>
00083 #include <set>
00084 #include <geos/platform.h>
00085 #include <geos/geom.h>
00086 #include <geos/geomgraph.h>
00087 #include <geos/geosAlgorithm.h>
00088
00089 using namespace std;
00090
00091 namespace geos {
00092
00093
00094
00095
00096
00097 class SegmentNode {
00098 public:
00099 Coordinate *coord;
00100 int segmentIndex;
00101 double dist;
00102 SegmentNode(Coordinate *newCoord, int nSegmentIndex, double newDist);
00103 virtual ~SegmentNode();
00109 int compare(int cSegmentIndex,double cDist);
00110 bool isEndPoint(int maxSegmentIndex);
00111 int compareTo(void* obj);
00112 string print();
00113 };
00114
00115 struct SegmentNodeLT {
00116 bool operator()(SegmentNode *s1, SegmentNode *s2) const {
00117 return s1->compareTo(s2)<0;
00118 }
00119 };
00120
00121 class SegmentString;
00122
00123
00124
00125
00126
00127 class SegmentNodeList {
00128 private:
00129 set<SegmentNode*,SegmentNodeLT> *nodes;
00130 const SegmentString *edge;
00131 vector<SegmentNode*> *sortedNodes;
00132
00133
00134 vector<SegmentString*> splitEdges;
00135
00136
00137 vector<CoordinateSequence*> splitCoordLists;
00138
00139 void checkSplitEdgesCorrectness(vector<SegmentString*> *splitEdges);
00145 SegmentString* createSplitEdge(SegmentNode *ei0, SegmentNode *ei1);
00146
00147 public:
00148
00149 SegmentNodeList(const SegmentString *newEdge);
00150
00151 virtual ~SegmentNodeList();
00152
00158 SegmentNode* add(Coordinate *intPt, int segmentIndex, double dist);
00159
00163
00164 set<SegmentNode*,SegmentNodeLT>* getNodes() { return nodes; }
00165
00169 void addEndpoints();
00170
00177 void addSplitEdges(vector<SegmentString*> *edgeList);
00178
00179 string print();
00180 };
00181
00182
00183
00184
00185
00186
00187
00188
00189 class SegmentString {
00190 private:
00191 SegmentNodeList *eiList;
00192 const CoordinateSequence *pts;
00193 const void* context;
00194 bool isIsolatedVar;
00195 public:
00199 SegmentString(const CoordinateSequence *newPts, const void* newContext);
00200 virtual ~SegmentString();
00201 const void* getContext() const;
00202 SegmentNodeList* getIntersectionList() const;
00203 int size() const;
00204 const Coordinate& getCoordinate(int i) const;
00205 CoordinateSequence* getCoordinates() const;
00206 const CoordinateSequence* getCoordinatesRO() const;
00207 void setIsolated(bool isIsolated);
00208 bool isIsolated() const;
00209 bool isClosed() const;
00214 void addIntersections(LineIntersector *li,int segmentIndex, int geomIndex);
00221 void addIntersection(LineIntersector *li, int segmentIndex, int geomIndex, int intIndex);
00222 void OLDaddIntersection(LineIntersector *li, int segmentIndex, int geomIndex, int intIndex);
00228 void addIntersection(Coordinate& intPt, int segmentIndex);
00229 void addIntersection(Coordinate& intPt, int segmentIndex, double dist);
00230 };
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241 class nodingSegmentIntersector {
00242 private:
00247 bool hasIntersectionVar;
00248 bool hasProperVar;
00249 bool hasProperInteriorVar;
00250 bool hasInteriorVar;
00251
00252 Coordinate *properIntersectionPoint;
00253 LineIntersector *li;
00254 bool recordIsolated;
00255 bool isSelfIntersectionVar;
00262 bool isTrivialIntersection(SegmentString *e0, int segIndex0, SegmentString *e1, int segIndex1);
00263 public:
00264 static bool isAdjacentSegments(int i1, int i2);
00265 int numIntersections;
00266 int numInteriorIntersections;
00267 int numProperIntersections;
00268
00269 int numTests;
00270 nodingSegmentIntersector(LineIntersector *newLi);
00271 LineIntersector* getLineIntersector();
00275 Coordinate* getProperIntersectionPoint();
00276 bool hasIntersection();
00284 bool hasProperIntersection();
00289 bool hasProperInteriorIntersection();
00294 bool hasInteriorIntersection();
00303 void processIntersections(SegmentString *e0, int segIndex0,SegmentString *e1, int segIndex1);
00304 };
00305
00306
00307
00308
00309
00310
00311
00312 class Noder {
00313 public:
00314 static vector<SegmentString*>* getNodedEdges(vector<SegmentString*>* segStrings);
00315 static void getNodedEdges(vector<SegmentString*>* segStrings,vector<SegmentString*>* resultEdgelist);
00316 nodingSegmentIntersector *segInt;
00317 public:
00318 Noder(){};
00319 virtual void setSegmentIntersector(nodingSegmentIntersector *newSegInt);
00320 virtual vector<SegmentString*>* node(vector<SegmentString*>* segStrings)=0;
00321 };
00322
00323
00324
00325
00326
00327
00328
00329
00330 class SimpleNoder: public Noder {
00331 public:
00332 SimpleNoder(){};
00333 virtual vector<SegmentString*>* node(vector<SegmentString*> *inputSegStrings);
00334 private:
00335 virtual void computeIntersects(SegmentString *e0, SegmentString *e1);
00336 };
00337
00338
00339
00340
00341
00342
00343 class NodingValidator {
00344 public:
00345 NodingValidator(vector<SegmentString*> *newSegStrings);
00346 virtual ~NodingValidator();
00347 void checkValid();
00348 private:
00349 LineIntersector *li;
00350 vector<SegmentString*> *segStrings;
00351 void checkProperIntersections();
00352 void checkProperIntersections(SegmentString *ss0, SegmentString *ss1);
00353 void checkProperIntersections(SegmentString *e0, int segIndex0, SegmentString *e1, int segIndex1);
00357 bool hasInteriorIntersection(LineIntersector *aLi, Coordinate& p0, Coordinate& p1);
00358 void checkNoInteriorPointsSame();
00359 void checkNoInteriorPointsSame(const Coordinate& testPt,vector<SegmentString*> *segStrings);
00360 };
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371 class MCQuadtreeNoder: public Noder {
00372 public:
00373 MCQuadtreeNoder();
00374 virtual ~MCQuadtreeNoder();
00375 vector<SegmentString*>* node(vector<SegmentString*> *inputSegStrings);
00376 class SegmentOverlapAction: public MonotoneChainOverlapAction {
00377 private:
00378 nodingSegmentIntersector *si;
00379 public:
00380 SegmentOverlapAction(nodingSegmentIntersector *newSi);
00381 void overlap(indexMonotoneChain *mc1, int start1, indexMonotoneChain *mc2, int start2);
00382 };
00383 private:
00384 vector<indexMonotoneChain*> *chains;
00385 SpatialIndex *index;
00386 int idCounter;
00387
00388 int nOverlaps;
00389 void intersectChains();
00390 void add(SegmentString *segStr);
00391 };
00392
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404 class IteratedNoder {
00405 private:
00410 vector<SegmentString*>* node(vector<SegmentString*> *segStrings, int *numInteriorIntersections);
00411 const PrecisionModel *pm;
00412 LineIntersector *li;
00413 public:
00414 IteratedNoder(const PrecisionModel *newPm);
00415 virtual ~IteratedNoder();
00426 vector<SegmentString*>* node(vector<SegmentString*> *segStrings);
00427 };
00428
00429 }
00430 #endif
00431