00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef GEOS_GEOMGRAPH_H
00018 #define GEOS_GEOMGRAPH_H
00019
00020 #include <memory>
00021 #include <string>
00022 #include <vector>
00023 #include <map>
00024 #include <geos/geom.h>
00025 #include <geos/geomgraphindex.h>
00026 #include <geos/geosAlgorithm.h>
00027 #include <geos/platform.h>
00028
00029 using namespace std;
00030
00031 namespace geos {
00032
00033 class EdgeSetIntersector;
00034 class SegmentIntersector;
00035 class MonotoneChainEdge;
00036
00037
00038 class Position {
00039 public:
00040 enum {
00041
00042 ON,
00043
00044 LEFT,
00045
00046 RIGHT
00047 };
00052 static int opposite(int position);
00053 };
00054
00055 class TopologyLocation {
00056 public:
00057 TopologyLocation();
00058 virtual ~TopologyLocation();
00059 TopologyLocation(const vector<int>* newLocation);
00067 TopologyLocation(int on, int left, int right);
00068 TopologyLocation(int on);
00069 TopologyLocation(const TopologyLocation *gl);
00070 int get(int posIndex) const;
00071 bool isNull() const;
00072 bool isAnyNull() const;
00073 bool isEqualOnSide(const TopologyLocation &le, int locIndex) const;
00074 bool isArea() const;
00075 bool isLine() const;
00076 void flip();
00077 void setAllLocations(int locValue);
00078 void setAllLocationsIfNull(int locValue);
00079 void setLocation(int locIndex, int locValue);
00080 void setLocation(int locValue);
00081 const vector<int>* getLocations() const;
00082 void setLocations(int on, int left, int right);
00083 void setLocations(const TopologyLocation &gl);
00084 bool allPositionsEqual(int loc) const;
00085 void merge(const TopologyLocation* gl);
00086 string toString() const;
00087 protected:
00088 vector<int>* location;
00089 private:
00090 void init(int size);
00091 };
00092
00093 class Label {
00094 public:
00095 static Label* toLineLabel(const Label* label);
00096 Label(int onLoc);
00097 Label(int geomIndex, int onLoc);
00098 Label(int onLoc, int leftLoc, int rightLoc);
00099 Label(const Label *l);
00100 Label();
00101 virtual ~Label();
00102 Label(int geomIndex,int onLoc,int leftLoc,int rightLoc);
00103 Label(int geomIndex,const TopologyLocation* gl);
00104 void flip();
00105 int getLocation(int geomIndex, int posIndex) const;
00106 int getLocation(int geomIndex) const;
00107 void setLocation(int geomIndex, int posIndex, int location);
00108 void setLocation(int geomIndex, int location);
00109 void setAllLocations(int geomIndex, int location);
00110 void setAllLocationsIfNull(int geomIndex, int location);
00111 void setAllLocationsIfNull(int location);
00112 void merge(const Label* lbl);
00113 int getGeometryCount() const;
00114 bool isNull(int geomIndex) const;
00115 bool isAnyNull(int geomIndex) const;
00116 bool isArea() const;
00117 bool isArea(int geomIndex) const;
00118 bool isLine(int geomIndex) const;
00119 bool isEqualOnSide(Label* lbl, int side) const;
00120 bool allPositionsEqual(int geomIndex, int loc) const;
00121 void toLine(int geomIndex);
00122 string toString() const;
00123 protected:
00124 TopologyLocation* elt[2];
00125 private:
00126 void setGeometryLocation(int geomIndex, const TopologyLocation* tl);
00127 };
00128
00129 class Depth {
00130 public:
00131 static int depthAtLocation(int location);
00132 Depth();
00133 virtual ~Depth();
00134 int getDepth(int geomIndex,int posIndex);
00135 void setDepth(int geomIndex,int posIndex,int depthValue);
00136 int getLocation(int geomIndex,int posIndex);
00137 void add(int geomIndex,int posIndex,int location);
00138 bool isNull();
00139 bool isNull(int geomIndex);
00140 bool isNull(int geomIndex,int posIndex);
00141 int getDelta(int geomIndex);
00142 void normalize();
00143 void add(Label* lbl);
00144 string toString();
00145 private:
00146 enum {
00147 DEPTHNULL=-1
00148 };
00149
00150 int depth[2][3];
00151 };
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162 class Quadrant {
00163 public:
00168 static int quadrant(double dx, double dy);
00172 static int quadrant(const Coordinate& p0, const Coordinate& p1);
00176 static bool isOpposite(int quad1, int quad2);
00177
00178
00179
00180
00181 static int commonHalfPlane(int quad1, int quad2);
00186 static bool isInHalfPlane(int quad, int halfPlane);
00190 static bool isNorthern(int quad);
00191 };
00192
00193
00194 class GraphComponent {
00195 public:
00196 GraphComponent();
00197 GraphComponent(Label* newLabel);
00198 virtual ~GraphComponent();
00199 Label* getLabel();
00200 virtual void setLabel(Label* newLabel);
00201 virtual void setInResult(bool isInResult);
00202 virtual bool isInResult();
00203 virtual void setCovered(bool isCovered);
00204 virtual bool isCovered();
00205 virtual bool isCoveredSet();
00206 virtual bool isVisited();
00207 virtual void setVisited(bool isVisited);
00208
00209 virtual bool isIsolated()=0;
00210 virtual void updateIM(IntersectionMatrix *im);
00211 protected:
00212 Label* label;
00213 virtual void computeIM(IntersectionMatrix *im)=0;
00214 private:
00215 bool isInResultVar;
00216 bool isCoveredVar;
00217 bool isCoveredSetVar;
00218 bool isVisitedVar;
00219 };
00220
00221 class Node;
00222 class EdgeIntersectionList;
00223 class Edge: public GraphComponent{
00224 public:
00225 static void updateIM(Label *lbl,IntersectionMatrix *im);
00226 CoordinateSequence* pts;
00227 EdgeIntersectionList *eiList;
00228 Edge();
00229 Edge(CoordinateSequence* newPts, Label *newLabel);
00230 Edge(CoordinateSequence* newPts);
00231 virtual ~Edge();
00232 virtual int getNumPoints();
00233 virtual void setName(string newName);
00234 virtual const CoordinateSequence* getCoordinates() const;
00235 virtual const Coordinate& getCoordinate(int i);
00236 virtual const Coordinate& getCoordinate();
00237 virtual Depth *getDepth();
00242 virtual int getDepthDelta();
00243 virtual void setDepthDelta(int newDepthDelta);
00244 virtual int getMaximumSegmentIndex();
00245 virtual EdgeIntersectionList* getEdgeIntersectionList();
00246 virtual MonotoneChainEdge* getMonotoneChainEdge();
00247 virtual bool isClosed();
00248 virtual bool isCollapsed();
00249 virtual Edge* getCollapsedEdge();
00250 virtual void setIsolated(bool newIsIsolated);
00251 virtual bool isIsolated();
00252 virtual void addIntersections(LineIntersector *li,int segmentIndex,int geomIndex);
00253 virtual void addIntersection(LineIntersector *li,int segmentIndex,int geomIndex,int intIndex);
00254 virtual void computeIM(IntersectionMatrix *im);
00255 virtual bool isPointwiseEqual(Edge *e);
00256 virtual string print();
00257 virtual string printReverse();
00258 virtual bool equals(Edge* e);
00259 virtual Envelope* getEnvelope();
00260 private:
00261 string name;
00262 MonotoneChainEdge *mce;
00263 Envelope *env;
00264 bool isIsolatedVar;
00265 Depth *depth;
00266 int depthDelta;
00267 };
00268
00269 class EdgeEnd {
00270 friend class Unload;
00271 public:
00272 EdgeEnd();
00273 virtual ~EdgeEnd();
00274 EdgeEnd(Edge* newEdge, Coordinate& newP0, Coordinate& newP1);
00275 EdgeEnd(Edge* newEdge, Coordinate& newP0, Coordinate& newP1, Label* newLabel);
00276 virtual Edge* getEdge();
00277 virtual Label* getLabel();
00278 virtual Coordinate& getCoordinate();
00279 virtual Coordinate& getDirectedCoordinate();
00280 virtual int getQuadrant();
00281 virtual double getDx();
00282 virtual double getDy();
00283 virtual void setNode(Node* newNode);
00284 virtual Node* getNode();
00285 virtual int compareTo(EdgeEnd *e);
00286 virtual int compareDirection(EdgeEnd *e);
00287 virtual void computeLabel();
00288 virtual string print();
00289 protected:
00290
00291 Edge* edge;
00292 Label* label;
00293 EdgeEnd(Edge* newEdge);
00294 virtual void init(const Coordinate& newP0, const Coordinate& newP1);
00295 private:
00296 Node* node;
00297 Coordinate p0,p1;
00298 double dx, dy;
00299 int quadrant;
00300 };
00301
00302 struct EdgeEndLT {
00303 bool operator()(EdgeEnd *s1, EdgeEnd *s2) const {
00304 return s1->compareTo(s2)<0;
00305 }
00306 };
00307
00308 class GeometryGraph;
00309 class EdgeEndStar {
00310 public:
00311 EdgeEndStar();
00312 virtual ~EdgeEndStar();
00313 virtual void insert(EdgeEnd *e);
00314 virtual Coordinate& getCoordinate();
00315 virtual int getDegree();
00316 virtual vector<EdgeEnd*>::iterator getIterator();
00317 virtual vector<EdgeEnd*>* getEdges();
00318 virtual EdgeEnd* getNextCW(EdgeEnd *ee);
00319 virtual void computeLabelling(vector<GeometryGraph*> *geom);
00320 virtual int getLocation(int geomIndex,Coordinate& p,vector<GeometryGraph*> *geom);
00321 virtual bool isAreaLabelsConsistent();
00322 virtual void propagateSideLabels(int geomIndex);
00323 virtual int findIndex(EdgeEnd *eSearch);
00324 virtual string print();
00325 protected:
00326 map<EdgeEnd*,void*,EdgeEndLT> *edgeMap;
00327 vector<EdgeEnd*> *edgeList;
00328 virtual void insertEdgeEnd(EdgeEnd *e,void* obj);
00329 private:
00330 int ptInAreaLocation[2];
00331 virtual void computeEdgeEndLabels();
00332 virtual bool checkAreaLabelsConsistent(int geomIndex);
00333 };
00334
00335 class DirectedEdge;
00336 class EdgeRing;
00337 class DirectedEdgeStar: public EdgeEndStar {
00338 public:
00339 DirectedEdgeStar();
00340 ~DirectedEdgeStar();
00341 void insert(EdgeEnd *ee);
00342 Label *getLabel();
00343 int getOutgoingDegree();
00344 int getOutgoingDegree(EdgeRing *er);
00345 DirectedEdge* getRightmostEdge();
00346 void computeLabelling(vector<GeometryGraph*> *geom);
00347 void mergeSymLabels();
00348 void updateLabelling(Label *nodeLabel);
00349 void linkResultDirectedEdges();
00350 void linkMinimalDirectedEdges(EdgeRing *er);
00351 void linkAllDirectedEdges();
00352 void findCoveredLineEdges();
00353 void computeDepths(DirectedEdge *de);
00354 string print();
00355 private:
00359 vector<DirectedEdge*> *resultAreaEdgeList;
00360 Label *label;
00361 vector<DirectedEdge*>* getResultAreaEdges();
00362 enum {
00363 SCANNING_FOR_INCOMING=1,
00364 LINKING_TO_OUTGOING
00365 };
00366
00367
00368 int computeDepths(int startIndex, int endIndex, int startDepth);
00369 };
00370
00371 class Node: public GraphComponent {
00372
00373 public:
00374 Node(Coordinate& newCoord, EdgeEndStar* newEdges);
00375 virtual ~Node();
00376 virtual const Coordinate& getCoordinate() const;
00377 virtual EdgeEndStar* getEdges();
00378 virtual bool isIsolated();
00379 virtual void add(EdgeEnd *e);
00380 virtual void mergeLabel(const Node* n);
00381 virtual void mergeLabel(const Label* label2);
00382 virtual void setLabel(int argIndex, int onLocation);
00383 virtual void setLabelBoundary(int argIndex);
00384 virtual int computeMergedLocation(const Label* label2, int eltIndex);
00385 virtual string print();
00386 virtual const vector<double> &getZ() const;
00387 virtual void addZ(double);
00388
00389 protected:
00390 Coordinate coord;
00391 EdgeEndStar* edges;
00392 virtual void computeIM(IntersectionMatrix *im) {};
00393
00394 private:
00395 vector<double>zvals;
00396 double ztot;
00397
00398 };
00399
00400 class NodeFactory {
00401 public:
00402 virtual Node* createNode(Coordinate coord);
00403 };
00404
00405 class EdgeIntersection {
00406 public:
00407 Coordinate coord;
00408 int segmentIndex;
00409 double dist;
00410 EdgeIntersection(const Coordinate& newCoord, int newSegmentIndex, double newDist);
00411 virtual ~EdgeIntersection();
00412 int compare(int newSegmentIndex, double newDist);
00413 bool isEndPoint(int maxSegmentIndex);
00414 string print();
00415 int compareTo(void* obj);
00416 };
00417
00418 class EdgeIntersectionList{
00419 public:
00420 vector<EdgeIntersection*> *list;
00421 Edge *edge;
00422 EdgeIntersectionList(Edge *edge);
00423 ~EdgeIntersectionList();
00424 EdgeIntersection* add(const Coordinate& coord, int segmentIndex, double dist);
00425 vector<EdgeIntersection*>::iterator iterator();
00426 bool isEmpty();
00427 bool findInsertionPoint(int segmentIndex,double dist,vector<EdgeIntersection*>::iterator *insertIt);
00428 bool isIntersection(const Coordinate& pt);
00429 void addEndpoints();
00430 void addSplitEdges(vector<Edge*> *edgeList);
00431 Edge *createSplitEdge(EdgeIntersection *ei0, EdgeIntersection *ei1);
00432 string print();
00433 };
00434
00435 class EdgeList {
00436 public:
00437 EdgeList();
00438 virtual ~EdgeList();
00439 void add(Edge *e);
00440 void addAll(vector<Edge*> *edgeColl);
00441 vector<Edge*>* getEdges();
00442 Edge* findEqualEdge(Edge* e);
00443 Edge* get(int i);
00444 int findEdgeIndex(Edge *e);
00445 string print();
00446 private:
00447 vector<Edge*> *edges;
00457 SpatialIndex* index;
00458 };
00459
00460 struct CoordLT {
00461 bool operator()(Coordinate s1, Coordinate s2) const {
00462 return s1.compareTo(s2)<0;
00463 }
00464 };
00465
00466 class NodeMap{
00467 public:
00468 map<Coordinate,Node*,CoordLT>* nodeMap;
00469 NodeFactory *nodeFact;
00470
00471 NodeMap(NodeFactory *newNodeFact);
00472 virtual ~NodeMap();
00473 Node* addNode(const Coordinate& coord);
00474 Node* addNode(Node *n);
00475 void add(EdgeEnd *e);
00476 Node *find(const Coordinate& coord) const;
00477 map<Coordinate,Node*,CoordLT>::iterator iterator() const;
00478
00479
00480 vector<Node*>* getBoundaryNodes(int geomIndex) const;
00481 string print() const;
00482 };
00483
00484 class EdgeRing;
00485
00486 class DirectedEdge: public EdgeEnd{
00487 public:
00488 static int depthFactor(int currLocation, int nextLocation);
00489 DirectedEdge();
00490 virtual ~DirectedEdge();
00491 DirectedEdge(Edge *newEdge, bool newIsForward);
00492 Edge* getEdge();
00493 void setInResult(bool newIsInResult);
00494 bool isInResult();
00495 bool isVisited();
00496 void setVisited(bool newIsVisited);
00497 void setEdgeRing(EdgeRing *newEdgeRing);
00498 EdgeRing* getEdgeRing();
00499 void setMinEdgeRing(EdgeRing *newMinEdgeRing);
00500 EdgeRing* getMinEdgeRing();
00501 int getDepth(int position);
00502 void setDepth(int position, int newDepth);
00503 int getDepthDelta();
00504 void setVisitedEdge(bool newIsVisited);
00505 DirectedEdge* getSym();
00506 bool isForward();
00507 void setSym(DirectedEdge *de);
00508 DirectedEdge* getNext();
00509 void setNext(DirectedEdge *newNext);
00510 DirectedEdge* getNextMin();
00511 void setNextMin(DirectedEdge *newNextMin);
00512 bool isLineEdge();
00513 bool isInteriorAreaEdge();
00514 void setEdgeDepths(int position, int newDepth);
00515 void OLDsetEdgeDepths(int position, int newDepth);
00516 string print();
00517 string printEdge();
00518 protected:
00519 bool isForwardVar;
00520 private:
00521 bool isInResultVar;
00522 bool isVisitedVar;
00523 DirectedEdge *sym;
00524 DirectedEdge *next;
00525 DirectedEdge *nextMin;
00526 EdgeRing *edgeRing;
00527 EdgeRing *minEdgeRing;
00532 int depth[3];
00533 void computeDirectedLabel();
00534 };
00535
00536 class EdgeRing{
00537 public:
00538 EdgeRing(DirectedEdge *newStart, const GeometryFactory *newGeometryFactory, CGAlgorithms *newCga);
00539 virtual ~EdgeRing();
00540 bool isIsolated();
00541 bool isHole();
00542 const Coordinate& getCoordinate(int i);
00543 LinearRing* getLinearRing();
00544 Label* getLabel();
00545 bool isShell();
00546 EdgeRing *getShell();
00547 void setShell(EdgeRing *newShell);
00548 void addHole(EdgeRing *edgeRing);
00549 Polygon* toPolygon(const GeometryFactory* geometryFactory);
00550 void computeRing();
00551 virtual DirectedEdge* getNext(DirectedEdge *de)=0;
00552 virtual void setEdgeRing(DirectedEdge *de, EdgeRing *er)=0;
00553 vector<DirectedEdge*>* getEdges();
00554 int getMaxNodeDegree();
00555 void setInResult();
00556 bool containsPoint(Coordinate& p);
00557 protected:
00558 DirectedEdge *startDe;
00559 const GeometryFactory *geometryFactory;
00560 CGAlgorithms *cga;
00561 void computePoints(DirectedEdge *newStart);
00562 void mergeLabel(Label *deLabel);
00563 void mergeLabel(Label *deLabel, int geomIndex);
00564 void addPoints(Edge *edge, bool isForward, bool isFirstEdge);
00565 vector<EdgeRing*>* holes;
00566 private:
00567 int maxNodeDegree;
00568 vector<DirectedEdge*>* edges;
00569 CoordinateSequence* pts;
00570 Label* label;
00571 LinearRing *ring;
00572 bool isHoleVar;
00573 EdgeRing *shell;
00574 void computeMaxNodeDegree();
00575 };
00576
00577 class PlanarGraph {
00578 public:
00579 static CGAlgorithms *cga;
00580
00581 static void linkResultDirectedEdges(vector<Node*>* allNodes);
00582
00583 PlanarGraph(NodeFactory *nodeFact);
00584 PlanarGraph();
00585 virtual ~PlanarGraph();
00586 virtual vector<Edge*>::iterator getEdgeIterator();
00587 virtual vector<EdgeEnd*>* getEdgeEnds();
00588 virtual bool isBoundaryNode(int geomIndex,Coordinate& coord);
00589 virtual void add(EdgeEnd *e);
00590 virtual map<Coordinate,Node*,CoordLT>::iterator getNodeIterator();
00591 virtual vector<Node*>* getNodes();
00592 virtual Node* addNode(Node *node);
00593 virtual Node* addNode(const Coordinate& coord);
00594 virtual Node* find(Coordinate& coord);
00595 virtual void addEdges(vector<Edge*>* edgesToAdd);
00596 virtual void linkResultDirectedEdges();
00597 virtual void linkAllDirectedEdges();
00598 virtual EdgeEnd* findEdgeEnd(Edge *e);
00599 virtual Edge* findEdge(const Coordinate& p0,const Coordinate& p1);
00600 virtual Edge* findEdgeInSameDirection(const Coordinate& p0,const Coordinate& p1);
00601 virtual string printEdges();
00602 virtual NodeMap* getNodeMap();
00603
00604
00605
00606 protected:
00607 vector<Edge*> *edges;
00608 NodeMap *nodes;
00609 vector<EdgeEnd*> *edgeEndList;
00610 virtual void insertEdge(Edge *e);
00611 private:
00612 bool matchInSameDirection(const Coordinate& p0, const Coordinate& p1, const Coordinate& ep0, const Coordinate& ep1);
00613 };
00614
00615 struct LineStringLT {
00616 bool operator()(const LineString *ls1, const LineString *ls2) const {
00617 return ls1->compareTo(ls2)<0;
00618 }
00619 };
00620
00621 class GeometryGraph: public PlanarGraph {
00622 public:
00623 static bool isInBoundary(int boundaryCount);
00624 static int determineBoundary(int boundaryCount);
00625 GeometryGraph();
00626 virtual ~GeometryGraph();
00627 GeometryGraph(int newArgIndex, const Geometry *newParentGeom);
00628 const Geometry* getGeometry();
00629 vector<Node*>* getBoundaryNodes();
00630 CoordinateSequence* getBoundaryPoints();
00631 Edge* findEdge(const LineString *line);
00632 void computeSplitEdges(vector<Edge*> *edgelist);
00633 void addEdge(Edge *e);
00634 void addPoint(Coordinate& pt);
00635 SegmentIntersector* computeSelfNodes(LineIntersector *li,
00636 bool computeRingSelfNodes);
00637 SegmentIntersector* computeEdgeIntersections(GeometryGraph *g,
00638 LineIntersector *li,bool includeProper);
00639 vector<Edge*> *getEdges();
00640 bool hasTooFewPoints();
00641 const Coordinate& getInvalidPoint();
00642
00643 private:
00644
00645 const Geometry *parentGeom;
00646
00647
00648
00649
00650
00651
00652 map<const LineString*,Edge*,LineStringLT>* lineEdgeMap;
00653
00654
00655
00656
00657
00658 bool useBoundaryDeterminationRule;
00659
00660
00661
00662
00663
00664 int argIndex;
00665
00666 vector<Node*>* boundaryNodes;
00667
00668 bool hasTooFewPointsVar;
00669
00670 Coordinate invalidPoint;
00671
00672 EdgeSetIntersector* createEdgeSetIntersector();
00673
00674 void add(const Geometry *g);
00675 void addCollection(const GeometryCollection *gc);
00676 void addPoint(const Point *p);
00677 void addPolygonRing(const LinearRing *lr,int cwLeft,int cwRight);
00678 void addPolygon(const Polygon *p);
00679 void addLineString(const LineString *line);
00680
00681 void insertPoint(int argIndex, const Coordinate& coord,int onLocation);
00682 void insertBoundaryPoint(int argIndex, const Coordinate& coord);
00683
00684 void addSelfIntersectionNodes(int argIndex);
00685 void addSelfIntersectionNode(int argIndex,Coordinate& coord,int loc);
00686 };
00687
00688 class SegmentString;
00689 class NodingValidator;
00690
00691
00692
00693
00694
00695
00696
00697 class EdgeNodingValidator {
00698 private:
00699 static vector<SegmentString*>* toSegmentStrings(vector<Edge*> *edges);
00700 NodingValidator *nv;
00701 public:
00702 EdgeNodingValidator(vector<Edge*> *edges);
00703 virtual ~EdgeNodingValidator();
00704 void checkValid();
00705 };
00706
00707
00708 bool operator==(Edge a,Edge b);
00709
00710 }
00711
00712 #endif // ifndef GEOS_GEOMGRAPH_H
00713
00714
00715
00716
00717
00718
00719
00720
00721
00722
00723
00724
00725
00726
00727
00728
00729
00730
00731
00732
00733
00734
00735
00736
00737
00738
00739
00740
00741
00742
00743
00744
00745
00746
00747
00748
00749
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767
00768
00769
00770
00771
00772
00773
00774