1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU Lesser General Public Licence as published
10  * by the Free Software Foundation.
11  * See the COPYING file for more information.
12  *
13  **********************************************************************/
14 
15 
16 #pragma once
17 
18 #include <geos/edgegraph/HalfEdge.h>
19 
20 #include <geos/export.h>
21 #include <string>
22 #include <cassert>
23 #include <map>
24 #include <array>
25 #include <memory>
26 #include <vector>
27 
28 // Forward declarations
29 namespace geos {
30 namespace geom {
31 class Coordinate;
32 }
33 }
34 
35 #undef EDGEGRAPH_HEAPHACK
36 
37 namespace geos {
38 namespace edgegraph { // geos.edgegraph
39 
40 
41 /**
42  * A graph comprised of {@link HalfEdge}s.
43  * It supports tracking the vertices in the graph
44  * via edges incident on them,
45  * to allow efficient lookup of edges and vertices.
46  *
47  * This class may be subclassed to use a
48  * different subclass of HalfEdge,
49  * by overriding {@link createEdge}.
50  * If additional logic is required to initialize
51  * edges then {@link addEdge}
52  * can be overridden as well.
53  *
54  * @author Martin Davis
55  *
56  */
57 
58 class GEOS_DLL EdgeGraph {
59 
60 private:
61 
62     std::deque<HalfEdge> edges;
63     std::map<geom::Coordinate, HalfEdge*> vertexMap;
64 
65     HalfEdge* create(const geom::Coordinate& p0, const geom::Coordinate& p1);
66 
67 
68 protected:
69 
70     /**
71     * Creates a single HalfEdge.
72     * Override to use a different HalfEdge subclass.
73     *
74     * @param orig the origin location
75     * @return a new HalfEdge with the given origin
76     */
77     HalfEdge* createEdge(const geom::Coordinate& orig);
78 
79     /**
80     * Inserts an edge not already present into the graph.
81     *
82     * @param orig the edge origin location
83     * @param dest the edge destination location
84     * @param eAdj an existing edge with same orig (if any)
85     * @return the created edge
86     */
87     HalfEdge* insert(const geom::Coordinate& orig, const geom::Coordinate& dest, HalfEdge* eAdj);
88 
89 
90 public:
91 
92     /**
93     * Initialized
94     */
EdgeGraph()95     EdgeGraph() {};
96 
97     /**
98     * Adds an edge between the coordinates orig and dest
99     * to this graph.
100     * Only valid edges can be added (in particular, zero-length segments cannot be added)
101     *
102     * @param orig the edge origin location
103     * @param dest the edge destination location.
104     * @return the created edge
105     * @return null if the edge was invalid and not added
106     *
107     * @see isValidEdge(Coordinate, Coordinate)
108     */
109     HalfEdge* addEdge(const geom::Coordinate& orig, const geom::Coordinate& dest);
110 
111     /**
112     * Tests if the given coordinates form a valid edge (with non-zero length).
113     *
114     * @param orig the start coordinate
115     * @param dest the end coordinate
116     * @return true if the edge formed is valid
117     */
118     static bool isValidEdge(const geom::Coordinate& orig, const geom::Coordinate& dest);
119 
120     void getVertexEdges(std::vector<const HalfEdge*>& edgesOut);
121 
122     /**
123     * Finds an edge in this graph with the given origin
124     * and destination, if one exists.
125     *
126     * @param orig the origin location
127     * @param dest the destination location.
128     * @return an edge with the given orig and dest, or null if none exists
129     */
130     HalfEdge* findEdge(const geom::Coordinate& orig, const geom::Coordinate& dest);
131 
132 
133 
134 
135 
136 
137 };
138 
139 
140 } // namespace geos.edgegraph
141 } // namespace geos
142 
143 
144 
145