1 /********************************************************************** 2 * 3 * GEOS - Geometry Engine Open Source 4 * http://geos.osgeo.org 5 * 6 * Copyright (C) 2011 Sandro Santilli <strk@kbt.io> 7 * Copyright (C) 2005-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: geomgraph/EdgeIntersectionList.java r428 (JTS-1.12+) 18 * 19 **********************************************************************/ 20 21 22 #ifndef GEOS_GEOMGRAPH_EDGEINTERSECTIONLIST_H 23 #define GEOS_GEOMGRAPH_EDGEINTERSECTIONLIST_H 24 25 #include <geos/export.h> 26 #include <algorithm> 27 #include <vector> 28 #include <string> 29 30 #include <geos/geomgraph/EdgeIntersection.h> // for EdgeIntersectionLessThen 31 #include <geos/geom/Coordinate.h> // for CoordinateLessThen 32 33 #include <geos/inline.h> 34 35 #ifdef _MSC_VER 36 #pragma warning(push) 37 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class 38 #endif 39 40 // Forward declarations 41 namespace geos { 42 namespace geom { 43 class Coordinate; 44 } 45 namespace geomgraph { 46 class Edge; 47 } 48 } 49 50 namespace geos { 51 namespace geomgraph { // geos.geomgraph 52 53 54 /** \brief 55 * A list of edge intersections along an Edge. 56 * 57 * Implements splitting an edge with intersections 58 * into multiple resultant edges. 59 */ 60 class GEOS_DLL EdgeIntersectionList { 61 public: 62 // Instead of storing edge intersections in a set, as JTS does, we store them 63 // in a vector and then sort the vector if needed before iterating among the 64 // edges. This is much faster. 65 using container = std::vector<EdgeIntersection>; 66 using const_iterator = container::const_iterator; 67 68 private: 69 mutable container nodeMap; 70 mutable bool sorted; 71 72 public: 73 74 const Edge* edge; 75 EdgeIntersectionList(const Edge* edge); 76 ~EdgeIntersectionList() = default; 77 78 /* 79 * Adds an intersection into the list, if it isn't already there. 80 * The input segmentIndex and dist are expected to be normalized. 81 * @return the EdgeIntersection found or added 82 */ 83 void add(const geom::Coordinate& coord, size_t segmentIndex, double dist); 84 85 const_iterator begin()86 begin() const 87 { 88 if (!sorted) { 89 std::sort(nodeMap.begin(), nodeMap.end()); 90 nodeMap.erase(std::unique(nodeMap.begin(), nodeMap.end()), nodeMap.end()); 91 sorted = true; 92 } 93 94 return nodeMap.begin(); 95 } 96 const_iterator end()97 end() const 98 { 99 return nodeMap.end(); 100 } 101 102 bool isEmpty() const; 103 bool isIntersection(const geom::Coordinate& pt) const; 104 105 /* 106 * Adds entries for the first and last points of the edge to the list 107 */ 108 void addEndpoints(); 109 110 /** 111 * Creates new edges for all the edges that the intersections in this 112 * list split the parent edge into. 113 * Adds the edges to the input list (this is so a single list 114 * can be used to accumulate all split edges for a Geometry). 115 * 116 * @param edgeList a list of EdgeIntersections 117 */ 118 void addSplitEdges(std::vector<Edge*>* edgeList); 119 120 Edge* createSplitEdge(const EdgeIntersection* ei0, const EdgeIntersection* ei1); 121 std::string print() const; 122 }; 123 124 std::ostream& operator<< (std::ostream&, const EdgeIntersectionList&); 125 126 } // namespace geos.geomgraph 127 } // namespace geos 128 129 #ifdef _MSC_VER 130 #pragma warning(pop) 131 #endif 132 133 #endif // ifndef GEOS_GEOMGRAPH_EDGEINTERSECTIONLIST_H 134 135