noding.h

00001 /**********************************************************************
00002  * $Id: noding.h,v 1.5 2004/11/04 19:08:07 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.5  2004/11/04 19:08:07  strk
00017  * Cleanups, initializers list, profiling.
00018  *
00019  * Revision 1.4  2004/11/01 16:43:04  strk
00020  * Added Profiler code.
00021  * Temporarly patched a bug in DoubleBits (must check drawbacks).
00022  * Various cleanups and speedups.
00023  *
00024  * Revision 1.3  2004/07/19 13:19:31  strk
00025  * Documentation fixes
00026  *
00027  * Revision 1.2  2004/07/08 19:34:49  strk
00028  * Mirrored JTS interface of CoordinateSequence, factory and
00029  * default implementations.
00030  * Added DefaultCoordinateSequenceFactory::instance() function.
00031  *
00032  * Revision 1.1  2004/07/02 13:20:42  strk
00033  * Header files moved under geos/ dir.
00034  *
00035  * Revision 1.12  2004/07/01 14:12:44  strk
00036  *
00037  * Geometry constructors come now in two flavors:
00038  *      - deep-copy args (pass-by-reference)
00039  *      - take-ownership of args (pass-by-pointer)
00040  * Same functionality is available through GeometryFactory,
00041  * including buildGeometry().
00042  *
00043  * Revision 1.11  2004/06/16 13:13:25  strk
00044  * Changed interface of SegmentString, now copying CoordinateSequence argument.
00045  * Fixed memory leaks associated with this and MultiGeometry constructors.
00046  * Other associated fixes.
00047  *
00048  * Revision 1.10  2004/05/07 07:57:27  strk
00049  * Added missing EdgeNodingValidator to build scripts.
00050  * Changed SegmentString constructor back to its original form
00051  * (takes const void *), implemented local tracking of "contexts"
00052  * in caller objects for proper destruction.
00053  *
00054  * Revision 1.9  2004/05/06 15:54:15  strk
00055  * SegmentNodeList keeps track of created splitEdges for later destruction.
00056  * SegmentString constructor copies given Label.
00057  * Buffer operation does no more leaks for doc/example.cpp
00058  *
00059  * Revision 1.8  2004/05/03 22:56:44  strk
00060  * leaks fixed, exception specification omitted.
00061  *
00062  * Revision 1.7  2004/04/30 09:15:28  strk
00063  * Enlarged exception specifications to allow for AssertionFailedException.
00064  * Added missing initializers.
00065  *
00066  * Revision 1.6  2004/04/23 00:02:18  strk
00067  * const-correctness changes
00068  *
00069  * Revision 1.5  2004/04/19 16:14:52  strk
00070  * Some memory leaks plugged in noding algorithms.
00071  *
00072  * Revision 1.4  2004/04/19 12:51:01  strk
00073  * Memory leaks fixes. Throw specifications added.
00074  *
00075  * Revision 1.3  2004/04/14 09:30:48  strk
00076  * Private iterated noding funx now use int* instead of vector to know
00077  * when it's time to stop.
00078  *
00079  * Revision 1.2  2004/03/26 07:48:30  ybychkov
00080  * "noding" package ported (JTS 1.4)
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  * Represents an intersection point between two {@link SegmentString}s.
00103  *
00104  */
00105 class SegmentNode {
00106 public:
00107         Coordinate *coord;   // the point of intersection
00108         int segmentIndex;   // the index of the containing line segment in the parent edge
00109         double dist;        // the edge distance of this point along the containing line segment
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  * A list of the {@link SegmentNode}s present along a
00132  * noded {@link SegmentString}.
00133  *
00134  */
00135 class SegmentNodeList {
00136 private:
00137         set<SegmentNode*,SegmentNodeLT> *nodes;
00138         const SegmentString *edge;  // the parent edge
00139         vector<SegmentNode*> *sortedNodes;
00140 
00141         // This vector is here to keep track of created splitEdges
00142         vector<SegmentString*> splitEdges;
00143 
00144         // This vector is here to keep track of created Coordinates
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         //replaces iterator()
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  * Contains a list of consecutive line segments which can be used to node the segments.
00194  * The line segments are represented by an array of {@link Coordinate}s.
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  * Computes the intersections between two line segments in {@link SegmentString}s
00242  * and adds them to each string.
00243  * The {@link nodingSegmentIntersector} is passed to a {@link Noder}.
00244  * The {@link addIntersections} method is called whenever the {@link Noder}
00245  * detects that two SegmentStrings <i>might</i> intersect.
00246  * This class is an example of the <i>Strategy</i> pattern.
00247  *
00248  */
00249 class nodingSegmentIntersector {
00250 private:
00255         bool hasIntersectionVar;
00256         bool hasProperVar;
00257         bool hasProperInteriorVar;
00258         bool hasInteriorVar;
00259         // the proper intersection point found
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         // testing only
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  * Computes all intersections between segments in a set of {@link SegmentString}s.
00316  * Intersections found are represented as {@link SegmentNode}s and add to the
00317  * {@link SegmentString}s in which they occur.
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  * Nodes a set of {@link SegmentString}s by
00333  * performing a brute-force comparison of every segment to every other one.
00334  * This has n^2 performance, so is too slow for use on large numbers
00335  * of segments.
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  * Validates that a collection of {@link SegmentString}s is correctly noded.
00348  * Throws an appropriate exception if an noding error is found.
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  * Nodes a set of SegmentStrings using a index based
00373  * on indexMonotoneChain and a SpatialIndex.
00374  * The SpatialIndex used should be something that supports
00375  * envelope (range) queries efficiently (such as a Quadtree
00376  * or STRtree.
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         // statistics
00397         int nOverlaps;
00398         void intersectChains();
00399         void add(SegmentString *segStr);
00400 };
00401 
00402 /*
00403  * Nodes a set of SegmentStrings completely.
00404  * The set of segmentStrings is fully noded;
00405  * i.e. noding is repeated until no further
00406  * intersections are detected.
00407  * <p>
00408  * Iterated noding using a FLOATING precision model is not guaranteed to converge,
00409  * due to roundoff error.   This problem is detected and an exception is thrown.
00410  * Clients can choose to rerun the noding using a lower precision model.
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); // throw(GEOSException *);
00436 };
00437 
00438 }
00439 #endif
00440 

Generated on Fri Sep 14 20:01:02 2007 for GEOS by  doxygen 1.5.1