/src/geos/include/geos/edgegraph/EdgeGraph.h
Line | Count | Source |
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 | | #undef EDGEGRAPH_HEAPHACK |
29 | | |
30 | | namespace geos { |
31 | | namespace edgegraph { // geos.edgegraph |
32 | | |
33 | | |
34 | | /** |
35 | | * A graph comprised of {@link HalfEdge}s. |
36 | | * It supports tracking the vertices in the graph |
37 | | * via edges incident on them, |
38 | | * to allow efficient lookup of edges and vertices. |
39 | | * |
40 | | * This class may be subclassed to use a |
41 | | * different subclass of HalfEdge, |
42 | | * by overriding {@link createEdge}. |
43 | | * If additional logic is required to initialize |
44 | | * edges then {@link addEdge} |
45 | | * can be overridden as well. |
46 | | * |
47 | | * @author Martin Davis |
48 | | * |
49 | | */ |
50 | | |
51 | | class GEOS_DLL EdgeGraph { |
52 | | |
53 | | private: |
54 | | |
55 | | std::deque<HalfEdge> edges; |
56 | | std::map<geom::CoordinateXY, HalfEdge*> vertexMap; |
57 | | |
58 | | HalfEdge* create(const geom::CoordinateXYZM& p0, const geom::CoordinateXYZM& p1); |
59 | | |
60 | | |
61 | | protected: |
62 | | |
63 | | /** |
64 | | * Creates a single HalfEdge. |
65 | | * Override to use a different HalfEdge subclass. |
66 | | * |
67 | | * @param orig the origin location |
68 | | * @return a new HalfEdge with the given origin |
69 | | */ |
70 | | virtual HalfEdge* createEdge(const geom::CoordinateXYZM& orig); |
71 | | |
72 | | /** |
73 | | * Inserts an edge not already present into the graph. |
74 | | * |
75 | | * @param orig the edge origin location |
76 | | * @param dest the edge destination location |
77 | | * @param eAdj an existing edge with same orig (if any) |
78 | | * @return the created edge |
79 | | */ |
80 | | HalfEdge* insert(const geom::CoordinateXYZM& orig, const geom::CoordinateXYZM& dest, HalfEdge* eAdj); |
81 | | |
82 | | |
83 | | public: |
84 | | |
85 | | /** |
86 | | * Initialized |
87 | | */ |
88 | 0 | EdgeGraph() {}; |
89 | 0 | virtual ~EdgeGraph() = default; |
90 | | |
91 | | /** |
92 | | * Adds an edge between the coordinates orig and dest |
93 | | * to this graph. |
94 | | * Only valid edges can be added (in particular, zero-length segments cannot be added) |
95 | | * |
96 | | * @param orig the edge origin location |
97 | | * @param dest the edge destination location. |
98 | | * @return the created edge |
99 | | * @return null if the edge was invalid and not added |
100 | | * |
101 | | * @see isValidEdge(Coordinate, Coordinate) |
102 | | */ |
103 | | HalfEdge* addEdge(const geom::CoordinateXYZM& orig, const geom::CoordinateXYZM& dest); |
104 | | |
105 | | /** |
106 | | * Tests if the given coordinates form a valid edge (with non-zero length). |
107 | | * |
108 | | * @param orig the start coordinate |
109 | | * @param dest the end coordinate |
110 | | * @return true if the edge formed is valid |
111 | | */ |
112 | | static bool isValidEdge(const geom::CoordinateXY& orig, const geom::CoordinateXY& dest); |
113 | | |
114 | | void getVertexEdges(std::vector<const HalfEdge*>& edgesOut); |
115 | | |
116 | | /** |
117 | | * Finds an edge in this graph with the given origin |
118 | | * and destination, if one exists. |
119 | | * |
120 | | * @param orig the origin location |
121 | | * @param dest the destination location. |
122 | | * @return an edge with the given orig and dest, or null if none exists |
123 | | */ |
124 | | HalfEdge* findEdge(const geom::CoordinateXY& orig, const geom::CoordinateXY& dest); |
125 | | |
126 | | |
127 | | |
128 | | |
129 | | |
130 | | |
131 | | }; |
132 | | |
133 | | |
134 | | } // namespace geos.edgegraph |
135 | | } // namespace geos |
136 | | |
137 | | |
138 | | |