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 bool isIncidentEdgeInResult() const;
00389
00390
00391 protected:
00392 Coordinate coord;
00393 EdgeEndStar* edges;
00394 virtual void computeIM(IntersectionMatrix *im) {};
00395
00396 private:
00397 vector<double>zvals;
00398 double ztot;
00399
00400 };
00401
00402 class NodeFactory {
00403 public:
00404 virtual Node* createNode(Coordinate coord);
00405 };
00406
00407 class EdgeIntersection {
00408 public:
00409 Coordinate coord;
00410 int segmentIndex;
00411 double dist;
00412 EdgeIntersection(const Coordinate& newCoord, int newSegmentIndex, double newDist);
00413 virtual ~EdgeIntersection();
00414 int compare(int newSegmentIndex, double newDist);
00415 bool isEndPoint(int maxSegmentIndex);
00416 string print();
00417 int compareTo(void* obj);
00418 };
00419
00420 class EdgeIntersectionList{
00421 public:
00422 vector<EdgeIntersection*> *list;
00423 Edge *edge;
00424 EdgeIntersectionList(Edge *edge);
00425 ~EdgeIntersectionList();
00426 EdgeIntersection* add(const Coordinate& coord, int segmentIndex, double dist);
00427 vector<EdgeIntersection*>::iterator iterator();
00428 bool isEmpty();
00429 bool findInsertionPoint(int segmentIndex,double dist,vector<EdgeIntersection*>::iterator *insertIt);
00430 bool isIntersection(const Coordinate& pt);
00431 void addEndpoints();
00432 void addSplitEdges(vector<Edge*> *edgeList);
00433 Edge *createSplitEdge(EdgeIntersection *ei0, EdgeIntersection *ei1);
00434 string print();
00435 };
00436
00437 class EdgeList {
00438 public:
00439 EdgeList();
00440 virtual ~EdgeList();
00441 void add(Edge *e);
00442 void addAll(vector<Edge*> *edgeColl);
00443 vector<Edge*>* getEdges();
00444 Edge* findEqualEdge(Edge* e);
00445 Edge* get(int i);
00446 int findEdgeIndex(Edge *e);
00447 string print();
00448 private:
00449 vector<Edge*> *edges;
00459 SpatialIndex* index;
00460 };
00461
00462 struct CoordLT {
00463 bool operator()(Coordinate s1, Coordinate s2) const {
00464 return s1.compareTo(s2)<0;
00465 }
00466 };
00467
00468 class NodeMap{
00469 public:
00470 map<Coordinate,Node*,CoordLT>* nodeMap;
00471 NodeFactory *nodeFact;
00472
00473 NodeMap(NodeFactory *newNodeFact);
00474 virtual ~NodeMap();
00475 Node* addNode(const Coordinate& coord);
00476 Node* addNode(Node *n);
00477 void add(EdgeEnd *e);
00478 Node *find(const Coordinate& coord) const;
00479 map<Coordinate,Node*,CoordLT>::iterator iterator() const;
00480
00481
00482 vector<Node*>* getBoundaryNodes(int geomIndex) const;
00483 string print() const;
00484 };
00485
00486 class EdgeRing;
00487
00488 class DirectedEdge: public EdgeEnd{
00489 public:
00490 static int depthFactor(int currLocation, int nextLocation);
00491 DirectedEdge();
00492 virtual ~DirectedEdge();
00493 DirectedEdge(Edge *newEdge, bool newIsForward);
00494 Edge* getEdge();
00495 void setInResult(bool newIsInResult);
00496 bool isInResult();
00497 bool isVisited();
00498 void setVisited(bool newIsVisited);
00499 void setEdgeRing(EdgeRing *newEdgeRing);
00500 EdgeRing* getEdgeRing();
00501 void setMinEdgeRing(EdgeRing *newMinEdgeRing);
00502 EdgeRing* getMinEdgeRing();
00503 int getDepth(int position);
00504 void setDepth(int position, int newDepth);
00505 int getDepthDelta();
00506 void setVisitedEdge(bool newIsVisited);
00507 DirectedEdge* getSym();
00508 bool isForward();
00509 void setSym(DirectedEdge *de);
00510 DirectedEdge* getNext();
00511 void setNext(DirectedEdge *newNext);
00512 DirectedEdge* getNextMin();
00513 void setNextMin(DirectedEdge *newNextMin);
00514 bool isLineEdge();
00515 bool isInteriorAreaEdge();
00516 void setEdgeDepths(int position, int newDepth);
00517 void OLDsetEdgeDepths(int position, int newDepth);
00518 string print();
00519 string printEdge();
00520 protected:
00521 bool isForwardVar;
00522 private:
00523 bool isInResultVar;
00524 bool isVisitedVar;
00525 DirectedEdge *sym;
00526 DirectedEdge *next;
00527 DirectedEdge *nextMin;
00528 EdgeRing *edgeRing;
00529 EdgeRing *minEdgeRing;
00534 int depth[3];
00535 void computeDirectedLabel();
00536 };
00537
00538 class EdgeRing{
00539 public:
00540 EdgeRing(DirectedEdge *newStart, const GeometryFactory *newGeometryFactory, CGAlgorithms *newCga);
00541 virtual ~EdgeRing();
00542 bool isIsolated();
00543 bool isHole();
00544 const Coordinate& getCoordinate(int i);
00545 LinearRing* getLinearRing();
00546 Label* getLabel();
00547 bool isShell();
00548 EdgeRing *getShell();
00549 void setShell(EdgeRing *newShell);
00550 void addHole(EdgeRing *edgeRing);
00551 Polygon* toPolygon(const GeometryFactory* geometryFactory);
00552 void computeRing();
00553 virtual DirectedEdge* getNext(DirectedEdge *de)=0;
00554 virtual void setEdgeRing(DirectedEdge *de, EdgeRing *er)=0;
00555 vector<DirectedEdge*>* getEdges();
00556 int getMaxNodeDegree();
00557 void setInResult();
00558 bool containsPoint(Coordinate& p);
00559 protected:
00560 DirectedEdge *startDe;
00561 const GeometryFactory *geometryFactory;
00562 CGAlgorithms *cga;
00563 void computePoints(DirectedEdge *newStart);
00564 void mergeLabel(Label *deLabel);
00565 void mergeLabel(Label *deLabel, int geomIndex);
00566 void addPoints(Edge *edge, bool isForward, bool isFirstEdge);
00567 vector<EdgeRing*>* holes;
00568 private:
00569 int maxNodeDegree;
00570 vector<DirectedEdge*>* edges;
00571 CoordinateSequence* pts;
00572 Label* label;
00573 LinearRing *ring;
00574 bool isHoleVar;
00575 EdgeRing *shell;
00576 void computeMaxNodeDegree();
00577 };
00578
00579 class PlanarGraph {
00580 public:
00581 static CGAlgorithms *cga;
00582
00583 static void linkResultDirectedEdges(vector<Node*>* allNodes);
00584
00585 PlanarGraph(NodeFactory *nodeFact);
00586 PlanarGraph();
00587 virtual ~PlanarGraph();
00588 virtual vector<Edge*>::iterator getEdgeIterator();
00589 virtual vector<EdgeEnd*>* getEdgeEnds();
00590 virtual bool isBoundaryNode(int geomIndex,Coordinate& coord);
00591 virtual void add(EdgeEnd *e);
00592 virtual map<Coordinate,Node*,CoordLT>::iterator getNodeIterator();
00593 virtual vector<Node*>* getNodes();
00594 virtual Node* addNode(Node *node);
00595 virtual Node* addNode(const Coordinate& coord);
00596 virtual Node* find(Coordinate& coord);
00597 virtual void addEdges(vector<Edge*>* edgesToAdd);
00598 virtual void linkResultDirectedEdges();
00599 virtual void linkAllDirectedEdges();
00600 virtual EdgeEnd* findEdgeEnd(Edge *e);
00601 virtual Edge* findEdge(const Coordinate& p0,const Coordinate& p1);
00602 virtual Edge* findEdgeInSameDirection(const Coordinate& p0,const Coordinate& p1);
00603 virtual string printEdges();
00604 virtual NodeMap* getNodeMap();
00605
00606
00607
00608 protected:
00609 vector<Edge*> *edges;
00610 NodeMap *nodes;
00611 vector<EdgeEnd*> *edgeEndList;
00612 virtual void insertEdge(Edge *e);
00613 private:
00614 bool matchInSameDirection(const Coordinate& p0, const Coordinate& p1, const Coordinate& ep0, const Coordinate& ep1);
00615 };
00616
00617 struct LineStringLT {
00618 bool operator()(const LineString *ls1, const LineString *ls2) const {
00619 return ls1->compareTo(ls2)<0;
00620 }
00621 };
00622
00623 class GeometryGraph: public PlanarGraph {
00624 public:
00625 static bool isInBoundary(int boundaryCount);
00626 static int determineBoundary(int boundaryCount);
00627 GeometryGraph();
00628 virtual ~GeometryGraph();
00629 GeometryGraph(int newArgIndex, const Geometry *newParentGeom);
00630 const Geometry* getGeometry();
00631 vector<Node*>* getBoundaryNodes();
00632 CoordinateSequence* getBoundaryPoints();
00633 Edge* findEdge(const LineString *line);
00634 void computeSplitEdges(vector<Edge*> *edgelist);
00635 void addEdge(Edge *e);
00636 void addPoint(Coordinate& pt);
00637 SegmentIntersector* computeSelfNodes(LineIntersector *li,
00638 bool computeRingSelfNodes);
00639 SegmentIntersector* computeEdgeIntersections(GeometryGraph *g,
00640 LineIntersector *li,bool includeProper);
00641 vector<Edge*> *getEdges();
00642 bool hasTooFewPoints();
00643 const Coordinate& getInvalidPoint();
00644
00645 private:
00646
00647 const Geometry *parentGeom;
00648
00649
00650
00651
00652
00653
00654 map<const LineString*,Edge*,LineStringLT>* lineEdgeMap;
00655
00656
00657
00658
00659
00660 bool useBoundaryDeterminationRule;
00661
00662
00663
00664
00665
00666 int argIndex;
00667
00668 vector<Node*>* boundaryNodes;
00669
00670 bool hasTooFewPointsVar;
00671
00672 Coordinate invalidPoint;
00673
00674 EdgeSetIntersector* createEdgeSetIntersector();
00675
00676 void add(const Geometry *g);
00677 void addCollection(const GeometryCollection *gc);
00678 void addPoint(const Point *p);
00679 void addPolygonRing(const LinearRing *lr,int cwLeft,int cwRight);
00680 void addPolygon(const Polygon *p);
00681 void addLineString(const LineString *line);
00682
00683 void insertPoint(int argIndex, const Coordinate& coord,int onLocation);
00684 void insertBoundaryPoint(int argIndex, const Coordinate& coord);
00685
00686 void addSelfIntersectionNodes(int argIndex);
00687 void addSelfIntersectionNode(int argIndex,Coordinate& coord,int loc);
00688 };
00689
00690 class SegmentString;
00691 class NodingValidator;
00692
00693
00694
00695
00696
00697
00698
00699 class EdgeNodingValidator {
00700 private:
00701 static vector<SegmentString*>* toSegmentStrings(vector<Edge*> *edges);
00702 NodingValidator *nv;
00703 public:
00704 EdgeNodingValidator(vector<Edge*> *edges);
00705 virtual ~EdgeNodingValidator();
00706 void checkValid();
00707 };
00708
00709
00710 bool operator==(Edge a,Edge b);
00711
00712 }
00713
00714 #endif // ifndef GEOS_GEOMGRAPH_H
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
00775
00776
00777
00778
00779