Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | Related Pages

noding.h

00001 /**********************************************************************
00002  * $Id: noding.h,v 1.3 2004/07/19 13:19:31 strk Exp $
00003  *
00004  * GEOS - Geometry Engine Open Source
00005  * http://geos.refractions.net
00006  *
00007  * Copyright (C) 2001-2002 Vivid Solutions Inc.
00008  *
00009  * This is free software; you can redistribute and/or modify it under
00010  * the terms of the GNU Lesser General Public Licence as published
00011  * by the Free Software Foundation. 
00012  * See the COPYING file for more information.
00013  *
00014  **********************************************************************
00015  * $Log: noding.h,v $
00016  * Revision 1.3  2004/07/19 13:19:31  strk
00017  * Documentation fixes
00018  *
00019  * Revision 1.2  2004/07/08 19:34:49  strk
00020  * Mirrored JTS interface of CoordinateSequence, factory and
00021  * default implementations.
00022  * Added DefaultCoordinateSequenceFactory::instance() function.
00023  *
00024  * Revision 1.1  2004/07/02 13:20:42  strk
00025  * Header files moved under geos/ dir.
00026  *
00027  * Revision 1.12  2004/07/01 14:12:44  strk
00028  *
00029  * Geometry constructors come now in two flavors:
00030  *      - deep-copy args (pass-by-reference)
00031  *      - take-ownership of args (pass-by-pointer)
00032  * Same functionality is available through GeometryFactory,
00033  * including buildGeometry().
00034  *
00035  * Revision 1.11  2004/06/16 13:13:25  strk
00036  * Changed interface of SegmentString, now copying CoordinateSequence argument.
00037  * Fixed memory leaks associated with this and MultiGeometry constructors.
00038  * Other associated fixes.
00039  *
00040  * Revision 1.10  2004/05/07 07:57:27  strk
00041  * Added missing EdgeNodingValidator to build scripts.
00042  * Changed SegmentString constructor back to its original form
00043  * (takes const void *), implemented local tracking of "contexts"
00044  * in caller objects for proper destruction.
00045  *
00046  * Revision 1.9  2004/05/06 15:54:15  strk
00047  * SegmentNodeList keeps track of created splitEdges for later destruction.
00048  * SegmentString constructor copies given Label.
00049  * Buffer operation does no more leaks for doc/example.cpp
00050  *
00051  * Revision 1.8  2004/05/03 22:56:44  strk
00052  * leaks fixed, exception specification omitted.
00053  *
00054  * Revision 1.7  2004/04/30 09:15:28  strk
00055  * Enlarged exception specifications to allow for AssertionFailedException.
00056  * Added missing initializers.
00057  *
00058  * Revision 1.6  2004/04/23 00:02:18  strk
00059  * const-correctness changes
00060  *
00061  * Revision 1.5  2004/04/19 16:14:52  strk
00062  * Some memory leaks plugged in noding algorithms.
00063  *
00064  * Revision 1.4  2004/04/19 12:51:01  strk
00065  * Memory leaks fixes. Throw specifications added.
00066  *
00067  * Revision 1.3  2004/04/14 09:30:48  strk
00068  * Private iterated noding funx now use int* instead of vector to know
00069  * when it's time to stop.
00070  *
00071  * Revision 1.2  2004/03/26 07:48:30  ybychkov
00072  * "noding" package ported (JTS 1.4)
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  * Represents an intersection point between two {@link SegmentString}s.
00095  *
00096  */
00097 class SegmentNode {
00098 public:
00099         Coordinate *coord;   // the point of intersection
00100         int segmentIndex;   // the index of the containing line segment in the parent edge
00101         double dist;        // the edge distance of this point along the containing line segment
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  * A list of the {@link SegmentNode}s present along a
00124  * noded {@link SegmentString}.
00125  *
00126  */
00127 class SegmentNodeList {
00128 private:
00129         set<SegmentNode*,SegmentNodeLT> *nodes;
00130         const SegmentString *edge;  // the parent edge
00131         vector<SegmentNode*> *sortedNodes;
00132 
00133         // This vector is here to keep track of created splitEdges
00134         vector<SegmentString*> splitEdges;
00135 
00136         // This vector is here to keep track of created Coordinates
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         //replaces iterator()
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  * Contains a list of consecutive line segments which can be used to node the segments.
00186  * The line segments are represented by an array of {@link Coordinate}s.
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  * Computes the intersections between two line segments in {@link SegmentString}s
00234  * and adds them to each string.
00235  * The {@link nodingSegmentIntersector} is passed to a {@link Noder}.
00236  * The {@link addIntersections} method is called whenever the {@link Noder}
00237  * detects that two SegmentStrings <i>might</i> intersect.
00238  * This class is an example of the <i>Strategy</i> pattern.
00239  *
00240  */
00241 class nodingSegmentIntersector {
00242 private:
00247         bool hasIntersectionVar;
00248         bool hasProperVar;
00249         bool hasProperInteriorVar;
00250         bool hasInteriorVar;
00251         // the proper intersection point found
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         // testing only
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  * Computes all intersections between segments in a set of {@link SegmentString}s.
00308  * Intersections found are represented as {@link SegmentNode}s and add to the
00309  * {@link SegmentString}s in which they occur.
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  * Nodes a set of {@link SegmentString}s by
00325  * performing a brute-force comparison of every segment to every other one.
00326  * This has n^2 performance, so is too slow for use on large numbers
00327  * of segments.
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  * Validates that a collection of {@link SegmentString}s is correctly noded.
00340  * Throws an appropriate exception if an noding error is found.
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  * Nodes a set of {@link SegmentStrings} using a index based
00365  * on {@link indexMonotoneChain}s and a {@link SpatialIndex}.
00366  * The {@link SpatialIndex} used should be something that supports
00367  * envelope (range) queries efficiently (such as a {@link Quadtree}
00368  * or {@link STRtree}.
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         // statistics
00388         int nOverlaps;
00389         void intersectChains();
00390         void add(SegmentString *segStr);
00391 };
00392 
00393 /*
00394  * Nodes a set of SegmentStrings completely.
00395  * The set of segmentStrings is fully noded;
00396  * i.e. noding is repeated until no further
00397  * intersections are detected.
00398  * <p>
00399  * Iterated noding using a FLOATING precision model is not guaranteed to converge,
00400  * due to roundoff error.   This problem is detected and an exception is thrown.
00401  * Clients can choose to rerun the noding using a lower precision model.
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); // throw(GEOSException *);
00427 };
00428 
00429 }
00430 #endif
00431 

Generated on Fri Nov 26 21:30:45 2004 for GEOS by  doxygen 1.3.9.1