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
00079
00080
00081
00082
00083
00084
00085
00086 #ifndef GEOS_NODING_H
00087 #define GEOS_NODING_H
00088
00089 #include <string>
00090 #include <vector>
00091 #include <set>
00092 #include <geos/platform.h>
00093 #include <geos/geom.h>
00094 #include <geos/geomgraph.h>
00095 #include <geos/geosAlgorithm.h>
00096
00097 using namespace std;
00098
00099 namespace geos {
00100
00101
00102
00103
00104
00105 class SegmentNode {
00106 public:
00107 Coordinate *coord;
00108 int segmentIndex;
00109 double dist;
00110 SegmentNode(Coordinate *newCoord, int nSegmentIndex, double newDist);
00111 virtual ~SegmentNode();
00117 int compare(int cSegmentIndex,double cDist);
00118 bool isEndPoint(int maxSegmentIndex);
00119 int compareTo(void* obj);
00120 string print();
00121 };
00122
00123 struct SegmentNodeLT {
00124 bool operator()(SegmentNode *s1, SegmentNode *s2) const {
00125 return s1->compareTo(s2)<0;
00126 }
00127 };
00128
00129 class SegmentString;
00130
00131
00132
00133
00134
00135 class SegmentNodeList {
00136 private:
00137 set<SegmentNode*,SegmentNodeLT> *nodes;
00138 const SegmentString *edge;
00139 vector<SegmentNode*> *sortedNodes;
00140
00141
00142 vector<SegmentString*> splitEdges;
00143
00144
00145 vector<CoordinateSequence*> splitCoordLists;
00146
00147 void checkSplitEdgesCorrectness(vector<SegmentString*> *splitEdges);
00153 SegmentString* createSplitEdge(SegmentNode *ei0, SegmentNode *ei1);
00154
00155 public:
00156
00157 SegmentNodeList(const SegmentString *newEdge);
00158
00159 virtual ~SegmentNodeList();
00160
00166 SegmentNode* add(Coordinate *intPt, int segmentIndex, double dist);
00167
00171
00172 set<SegmentNode*,SegmentNodeLT>* getNodes() { return nodes; }
00173
00177 void addEndpoints();
00178
00185 void addSplitEdges(vector<SegmentString*> *edgeList);
00186
00187 string print();
00188 };
00189
00190
00191
00192
00193
00194
00195
00196
00197 class SegmentString {
00198 private:
00199 SegmentNodeList *eiList;
00200 const CoordinateSequence *pts;
00201 const void* context;
00202 bool isIsolatedVar;
00203 public:
00207 SegmentString(const CoordinateSequence *newPts, const void* newContext);
00208 virtual ~SegmentString();
00209 const void* getContext() const;
00210 SegmentNodeList* getIntersectionList() const;
00211 int size() const;
00212 const Coordinate& getCoordinate(int i) const;
00213 CoordinateSequence* getCoordinates() const;
00214 const CoordinateSequence* getCoordinatesRO() const;
00215 void setIsolated(bool isIsolated);
00216 bool isIsolated() const;
00217 bool isClosed() const;
00222 void addIntersections(LineIntersector *li,int segmentIndex, int geomIndex);
00229 void addIntersection(LineIntersector *li, int segmentIndex, int geomIndex, int intIndex);
00230
00236 void addIntersection(Coordinate& intPt, int segmentIndex);
00237 void addIntersection(Coordinate& intPt, int segmentIndex, double dist);
00238 };
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249 class nodingSegmentIntersector {
00250 private:
00255 bool hasIntersectionVar;
00256 bool hasProperVar;
00257 bool hasProperInteriorVar;
00258 bool hasInteriorVar;
00259
00260 Coordinate *properIntersectionPoint;
00261 LineIntersector *li;
00262 bool recordIsolated;
00263 bool isSelfIntersectionVar;
00270 bool isTrivialIntersection(SegmentString *e0, int segIndex0, SegmentString *e1, int segIndex1);
00271 public:
00272 static bool isAdjacentSegments(int i1, int i2);
00273 int numIntersections;
00274 int numInteriorIntersections;
00275 int numProperIntersections;
00276
00277 int numTests;
00278 nodingSegmentIntersector(LineIntersector *newLi);
00279 LineIntersector* getLineIntersector();
00283 Coordinate* getProperIntersectionPoint();
00284 bool hasIntersection();
00292 bool hasProperIntersection();
00297 bool hasProperInteriorIntersection();
00302 bool hasInteriorIntersection();
00311 void processIntersections(SegmentString *e0, int segIndex0,SegmentString *e1, int segIndex1);
00312 };
00313
00314
00315
00316
00317
00318
00319
00320 class Noder {
00321 public:
00322 static vector<SegmentString*>* getNodedEdges(vector<SegmentString*>* segStrings);
00323 static void getNodedEdges(vector<SegmentString*>* segStrings,vector<SegmentString*>* resultEdgelist);
00324 nodingSegmentIntersector *segInt;
00325 public:
00326 Noder(){};
00327 virtual void setSegmentIntersector(nodingSegmentIntersector *newSegInt);
00328 virtual vector<SegmentString*>* node(vector<SegmentString*>* segStrings)=0;
00329 };
00330
00331
00332
00333
00334
00335
00336
00337
00338 class SimpleNoder: public Noder {
00339 public:
00340 SimpleNoder(){};
00341 virtual vector<SegmentString*>* node(vector<SegmentString*> *inputSegStrings);
00342 private:
00343 virtual void computeIntersects(SegmentString *e0, SegmentString *e1);
00344 };
00345
00346
00347
00348
00349
00350
00351 class NodingValidator {
00352 public:
00353 NodingValidator(vector<SegmentString*> *newSegStrings);
00354 virtual ~NodingValidator();
00355 void checkValid();
00356 private:
00357 LineIntersector *li;
00358 vector<SegmentString*> *segStrings;
00359 void checkProperIntersections();
00360 void checkProperIntersections(SegmentString *ss0, SegmentString *ss1);
00361 void checkProperIntersections(SegmentString *e0, int segIndex0, SegmentString *e1, int segIndex1);
00365 bool hasInteriorIntersection(LineIntersector *aLi, Coordinate& p0, Coordinate& p1);
00366 void checkNoInteriorPointsSame();
00367 void checkNoInteriorPointsSame(const Coordinate& testPt,vector<SegmentString*> *segStrings);
00368 };
00369
00370
00371
00372
00373
00374
00375
00376
00377
00378
00379 class MCQuadtreeNoder: public Noder {
00380 public:
00381 MCQuadtreeNoder();
00382 virtual ~MCQuadtreeNoder();
00383 vector<SegmentString*>* node(vector<SegmentString*> *inputSegStrings);
00384 class SegmentOverlapAction: public MonotoneChainOverlapAction {
00385 private:
00386 nodingSegmentIntersector *si;
00387 public:
00388 SegmentOverlapAction(nodingSegmentIntersector *newSi);
00389 void overlap(indexMonotoneChain *mc1, int start1, indexMonotoneChain *mc2, int start2);
00390 };
00391
00392 private:
00393 vector<indexMonotoneChain*> *chains;
00394 SpatialIndex *index;
00395 int idCounter;
00396
00397 int nOverlaps;
00398 void intersectChains();
00399 void add(SegmentString *segStr);
00400 };
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413 class IteratedNoder {
00414 private:
00419 vector<SegmentString*>* node(vector<SegmentString*> *segStrings, int *numInteriorIntersections);
00420 const PrecisionModel *pm;
00421 LineIntersector *li;
00422 public:
00423 IteratedNoder(const PrecisionModel *newPm);
00424 virtual ~IteratedNoder();
00435 vector<SegmentString*>* node(vector<SegmentString*> *segStrings);
00436 };
00437
00438 }
00439 #endif
00440