00001 /********************************************************************** 00002 * $Id: opLinemerge.h,v 1.4 2004/10/13 10:03:02 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 00016 #ifndef GEOS_OPLINEMERGE_H 00017 #define GEOS_OPLINEMERGE_H 00018 00019 #include <geos/platform.h> 00020 #include <geos/planargraph.h> 00021 #include <geos/geom.h> 00022 #include <vector> 00023 00024 namespace geos { 00025 00026 //using namespace planargraph; 00027 00028 /* 00029 * An edge of a LineMergeGraph. The <code>marked</code> field indicates 00030 * whether this Edge has been logically deleted from the graph. 00031 */ 00032 class LineMergeEdge: public planarEdge { 00033 private: 00034 LineString *line; 00035 public: 00039 LineMergeEdge(LineString *newLine); 00043 LineString* getLine(); 00044 }; 00045 00046 00047 /* 00048 * \class LineMergeDirectedEdge opLinemerge.h geos/opLinemerge.h 00049 * \brief 00050 * A planarDirectedEdge of a LineMergeGraph. 00051 * 00052 */ 00053 class LineMergeDirectedEdge: public planarDirectedEdge { 00054 public: 00068 LineMergeDirectedEdge(planarNode *from, planarNode *to, const Coordinate& directionPt, bool edgeDirection); 00069 00075 LineMergeDirectedEdge* getNext(); 00076 }; 00077 00078 /* 00079 * \brief 00080 * A sequence of LineMergeDirectedEdge forming one of the lines that will 00081 * be output by the line-merging process. 00082 */ 00083 class EdgeString { 00084 private: 00085 const GeometryFactory *factory; 00086 vector<LineMergeDirectedEdge*> *directedEdges; 00087 CoordinateSequence *coordinates; 00088 CoordinateSequence* getCoordinates(); 00089 public: 00090 /* 00091 * \brief 00092 * Constructs an EdgeString with the given factory used to 00093 * convert this EdgeString to a LineString 00094 */ 00095 EdgeString(const GeometryFactory *newFactory); 00096 00097 ~EdgeString(); 00098 00102 void add(LineMergeDirectedEdge *directedEdge); 00103 00104 /* 00105 * Converts this EdgeString into a LineString. 00106 */ 00107 LineString* toLineString(); 00108 }; 00109 00110 /* 00111 * A planar graph of edges that is analyzed to sew the edges together. The 00112 * <code>marked</code> flag on planarEdge 00113 * and planarNode indicates whether they have been 00114 * logically deleted from the graph. 00115 * 00116 */ 00117 class LineMergeGraph: public planarPlanarGraph { 00118 public: 00123 void addEdge(LineString *lineString); 00124 00125 ~LineMergeGraph(); 00126 private: 00127 planarNode* getNode(const Coordinate &coordinate); 00128 vector<planarNode*> newNodes; 00129 vector<planarEdge*> newEdges; 00130 vector<planarDirectedEdge*> newDirEdges; 00131 }; 00132 00133 /* 00134 * \class LineMerger opLinemerge.h geos/opLinemerge.h 00135 * \brief 00136 * Sews together a set of fully noded LineStrings. 00137 * 00138 * Sewing stops at nodes of degree 1 or 3 or more. 00139 * The exception is an isolated loop, which only has degree-2 nodes, 00140 * in which case a node is simply chosen as a starting point. 00141 * The direction of each merged LineString will be that of the majority 00142 * of the LineStrings from which it was derived. 00143 * 00144 * Any dimension of Geometry is handled. 00145 * The constituent linework is extracted to form the edges. 00146 * The edges must be correctly noded; that is, they must only meet 00147 * at their endpoints. 00148 * 00149 * The LineMerger will still run on incorrectly noded input 00150 * but will not form polygons from incorrected noded edges. 00151 * 00152 */ 00153 class LineMerger { 00154 public: 00155 LineMerger(); 00156 ~LineMerger(); 00157 00158 /* 00159 * \brief 00160 * Adds a collection of Geometries to be processed. 00161 * May be called multiple times. 00162 * 00163 * Any dimension of Geometry may be added; the constituent 00164 * linework will be extracted. 00165 */ 00166 void add(vector<Geometry*> *geometries); 00167 00168 /* 00169 * \brief 00170 * Adds a Geometry to be processed. 00171 * May be called multiple times. 00172 * 00173 * Any dimension of Geometry may be added; the constituent 00174 * linework will be extracted. 00175 */ 00176 void add(Geometry *geometry); 00177 00178 /* 00179 * \brief 00180 * Returns the LineStrings built by the merging process. 00181 */ 00182 vector<LineString*>* getMergedLineStrings(); 00183 00184 void add(LineString *lineString); 00185 00186 private: 00187 00188 LineMergeGraph *graph; 00189 vector<LineString*> *mergedLineStrings; 00190 vector<EdgeString*> *edgeStrings; 00191 const GeometryFactory *factory; 00192 void merge(); 00193 void buildEdgeStringsForObviousStartNodes(); 00194 void buildEdgeStringsForIsolatedLoops(); 00195 void buildEdgeStringsForUnprocessedNodes(); 00196 void buildEdgeStringsForNonDegree2Nodes(); 00197 void buildEdgeStringsStartingAt(planarNode *node); 00198 EdgeString* buildEdgeStringStartingWith(LineMergeDirectedEdge *start); 00199 }; 00200 00201 class LMGeometryComponentFilter: public GeometryComponentFilter { 00202 public: 00203 LineMerger *lm; 00204 LMGeometryComponentFilter(LineMerger *newLm); 00205 virtual void filter_rw(Geometry *geom); 00206 virtual void filter_ro(const Geometry *geom){}; // Unsupported 00207 }; 00208 00209 } 00210 #endif 00211 00212 /********************************************************************** 00213 * $Log: opLinemerge.h,v $ 00214 * Revision 1.4 2004/10/13 10:03:02 strk 00215 * Added missing linemerge and polygonize operation. 00216 * Bug fixes and leaks removal from the newly added modules and 00217 * planargraph (used by them). 00218 * Some comments and indentation changes. 00219 * 00220 * Revision 1.3 2004/07/19 13:19:31 strk 00221 * Documentation fixes 00222 * 00223 * Revision 1.2 2004/07/08 19:34:49 strk 00224 * Mirrored JTS interface of CoordinateSequence, factory and 00225 * default implementations. 00226 * Added DefaultCoordinateSequenceFactory::instance() function. 00227 * 00228 * Revision 1.1 2004/07/02 13:20:42 strk 00229 * Header files moved under geos/ dir. 00230 * 00231 * Revision 1.1 2004/04/07 06:55:50 ybychkov 00232 * "operation/linemerge" ported from JTS 1.4 00233 * 00234 * 00235 **********************************************************************/