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