1 /********************************************************************** 2 * 3 * GEOS - Geometry Engine Open Source 4 * http://geos.osgeo.org 5 * 6 * Copyright (C) 2010 Sandro Santilli <strk@kbt.io> 7 * Copyright (C) 2006 Refractions Research Inc. 8 * Copyright (C) 2001-2002 Vivid Solutions Inc. 9 * 10 * This is free software; you can redistribute and/or modify it under 11 * the terms of the GNU Lesser General Public Licence as published 12 * by the Free Software Foundation. 13 * See the COPYING file for more information. 14 * 15 ********************************************************************** 16 * 17 * Last port: operation/polygonize/Polygonizer.java 0b3c7e3eb0d3e 18 * 19 **********************************************************************/ 20 21 #ifndef GEOS_OP_POLYGONIZE_POLYGONIZER_H 22 #define GEOS_OP_POLYGONIZE_POLYGONIZER_H 23 24 #include <geos/export.h> 25 #include <geos/geom/Polygon.h> 26 #include <geos/geom/GeometryComponentFilter.h> // for LineStringAdder inheritance 27 #include <geos/operation/polygonize/PolygonizeGraph.h> 28 29 #include <memory> 30 #include <vector> 31 32 #ifdef _MSC_VER 33 #pragma warning(push) 34 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class 35 #endif 36 37 // Forward declarations 38 namespace geos { 39 namespace geom { 40 class Geometry; 41 42 class LineString; 43 44 class Polygon; 45 } 46 namespace operation { 47 namespace polygonize { 48 class EdgeRing; 49 } 50 } 51 } 52 53 namespace geos { 54 namespace operation { // geos::operation 55 namespace polygonize { // geos::operation::polygonize 56 57 /** \brief 58 * Polygonizes a set of Geometrys which contain linework that 59 * represents the edges of a planar graph. 60 * 61 * All types of Geometry are accepted as input; the constituent linework is extracted 62 * as the edges to be polygonized. 63 * The edges must be correctly noded; that is, they must only meet 64 * at their endpoints. Polygonization will accept incorrectly noded input but will 65 * not form polygons from non-noded edges, and reports them as errors. 66 * 67 * The Polygonizer reports the follow kinds of errors: 68 * 69 * - <b>Dangles</b> - edges which have one or both ends which are 70 * not incident on another edge endpoint 71 * - <b>Cut Edges</b> - edges which are connected at both ends but 72 * which do not form part of a polygon 73 * - <b>Invalid Ring Lines</b> - edges which form rings which are invalid 74 * (e.g. the component lines contain a self-intersection) 75 * 76 * The Polygonizer constructor allows extracting only polygons which form a 77 * valid polygonal result. 78 * The set of extracted polygons is guaranteed to be edge-disjoint. 79 * This is useful when it is known that the input lines form a valid 80 * polygonal geometry (which may include holes or nested polygons). 81 * 82 */ 83 class GEOS_DLL Polygonizer { 84 private: 85 /** 86 * Add every linear element in a geometry into the polygonizer graph. 87 */ 88 class GEOS_DLL LineStringAdder: public geom::GeometryComponentFilter { 89 public: 90 Polygonizer* pol; 91 explicit LineStringAdder(Polygonizer* p); 92 //void filter_rw(geom::Geometry *g); 93 void filter_ro(const geom::Geometry* g) override; 94 }; 95 96 // default factory 97 LineStringAdder lineStringAdder; 98 99 /** 100 * Add a linestring to the graph of polygon edges. 101 * 102 * @param line the {@link LineString} to add 103 */ 104 void add(const geom::LineString* line); 105 106 /** 107 * Perform the polygonization, if it has not already been carried out. 108 */ 109 void polygonize(); 110 111 static void findValidRings(const std::vector<EdgeRing*>& edgeRingList, 112 std::vector<EdgeRing*>& validEdgeRingList, 113 std::vector<std::unique_ptr<geom::LineString>>& invalidRingList); 114 115 void findShellsAndHoles(const std::vector<EdgeRing*>& edgeRingList); 116 117 void findDisjointShells(); 118 119 static void findOuterShells(std::vector<EdgeRing*>& shellList); 120 121 static std::vector<std::unique_ptr<geom::Polygon>> extractPolygons(std::vector<EdgeRing*> & shellList, bool includeAll); 122 123 bool extractOnlyPolygonal; 124 bool computed; 125 126 protected: 127 128 std::unique_ptr<PolygonizeGraph> graph; 129 130 // initialize with empty collections, in case nothing is computed 131 std::vector<const geom::LineString*> dangles; 132 std::vector<const geom::LineString*> cutEdges; 133 std::vector<std::unique_ptr<geom::LineString>> invalidRingLines; 134 135 std::vector<EdgeRing*> holeList; 136 std::vector<EdgeRing*> shellList; 137 std::vector<std::unique_ptr<geom::Polygon>> polyList; 138 139 public: 140 141 /** \brief 142 * Create a Polygonizer with the same GeometryFactory 143 * as the input Geometrys. 144 * 145 * @param onlyPolygonal true if only polygons which form a valid polygonal geometry should be extracted 146 */ 147 explicit Polygonizer(bool onlyPolygonal = false); 148 149 ~Polygonizer() = default; 150 151 /** \brief 152 * Add a collection of geometries to be polygonized. 153 * May be called multiple times. 154 * Any dimension of Geometry may be added; 155 * the constituent linework will be extracted and used 156 * 157 * @param geomList a list of Geometry with linework to be polygonized 158 */ 159 void add(std::vector<geom::Geometry*>* geomList); 160 161 /** \brief 162 * Add a collection of geometries to be polygonized. 163 * May be called multiple times. 164 * Any dimension of Geometry may be added; 165 * the constituent linework will be extracted and used 166 * 167 * @param geomList a list of Geometry with linework to be polygonized 168 */ 169 void add(std::vector<const geom::Geometry*>* geomList); 170 171 /** 172 * Add a geometry to the linework to be polygonized. 173 * May be called multiple times. 174 * Any dimension of Geometry may be added; 175 * the constituent linework will be extracted and used 176 * 177 * @param g a Geometry with linework to be polygonized 178 */ 179 void add(geom::Geometry* g); 180 181 /** 182 * Add a geometry to the linework to be polygonized. 183 * May be called multiple times. 184 * Any dimension of Geometry may be added; 185 * the constituent linework will be extracted and used 186 * 187 * @param g a Geometry with linework to be polygonized 188 */ 189 void add(const geom::Geometry* g); 190 191 /** \brief 192 * Gets the list of polygons formed by the polygonization. 193 * 194 * Ownership of vector is transferred to caller, subsequent 195 * calls will return NULL. 196 * @return a collection of Polygons 197 */ 198 std::vector<std::unique_ptr<geom::Polygon>> getPolygons(); 199 200 /** \brief 201 * Get the list of dangling lines found during polygonization. 202 * 203 * @return a (possibly empty) collection of pointers to 204 * the input LineStrings which are dangles. 205 * 206 */ 207 const std::vector<const geom::LineString*>& getDangles(); 208 209 bool hasDangles(); 210 211 /** \brief 212 * Get the list of cut edges found during polygonization. 213 * 214 * @return a (possibly empty) collection of pointers to 215 * the input LineStrings which are cut edges. 216 * 217 */ 218 const std::vector<const geom::LineString*>& getCutEdges(); 219 220 bool hasCutEdges(); 221 222 /** \brief 223 * Get the list of lines forming invalid rings found during 224 * polygonization. 225 * 226 * @return a (possibly empty) collection of pointers to 227 * the input LineStrings which form invalid rings 228 * 229 */ 230 const std::vector<std::unique_ptr<geom::LineString>>& getInvalidRingLines(); 231 232 bool hasInvalidRingLines(); 233 234 bool allInputsFormPolygons(); 235 236 // This seems to be needed by GCC 2.95.4 237 friend class Polygonizer::LineStringAdder; 238 }; 239 240 } // namespace geos::operation::polygonize 241 } // namespace geos::operation 242 } // namespace geos 243 244 #ifdef _MSC_VER 245 #pragma warning(pop) 246 #endif 247 248 #endif // GEOS_OP_POLYGONIZE_POLYGONIZER_H 249