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