/src/geos/src/edgegraph/EdgeGraph.cpp
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 | | #ifdef _MSC_VER |
16 | | #pragma warning(disable:4355) |
17 | | #endif |
18 | | |
19 | | #include <cassert> |
20 | | #include <string> |
21 | | #include <sstream> |
22 | | |
23 | | #include <geos/edgegraph/HalfEdge.h> |
24 | | #include <geos/edgegraph/EdgeGraph.h> |
25 | | #include <geos/geom/Coordinate.h> |
26 | | |
27 | | using namespace geos::geom; |
28 | | |
29 | | namespace geos { |
30 | | namespace edgegraph { // geos.edgegraph |
31 | | |
32 | | /*protected*/ |
33 | | HalfEdge* |
34 | | EdgeGraph::createEdge(const CoordinateXYZM& orig) |
35 | 0 | { |
36 | 0 | edges.emplace_back(orig); |
37 | 0 | return &(edges.back()); |
38 | 0 | } |
39 | | |
40 | | /*private*/ |
41 | | HalfEdge* |
42 | | EdgeGraph::create(const CoordinateXYZM& p0, const CoordinateXYZM& p1) |
43 | 0 | { |
44 | 0 | HalfEdge* e0 = createEdge(p0); |
45 | 0 | HalfEdge* e1 = createEdge(p1); |
46 | 0 | e0->link(e1); |
47 | 0 | return e0; |
48 | 0 | } |
49 | | |
50 | | /*public*/ |
51 | | HalfEdge* |
52 | | EdgeGraph::addEdge(const CoordinateXYZM& orig, const CoordinateXYZM& dest) |
53 | 0 | { |
54 | 0 | if (! isValidEdge(orig, dest)) { |
55 | 0 | return nullptr; |
56 | 0 | } |
57 | | |
58 | | /** |
59 | | * Attempt to find the edge already in the graph. |
60 | | * Return it if found. |
61 | | * Otherwise, use a found edge with same origin (if any) to construct new edge. |
62 | | */ |
63 | 0 | HalfEdge* eAdj = nullptr; |
64 | 0 | auto it = vertexMap.find(orig); |
65 | 0 | if (it != vertexMap.end()) { |
66 | 0 | eAdj = it->second; |
67 | 0 | } |
68 | |
|
69 | 0 | HalfEdge* eSame = nullptr; |
70 | 0 | if (eAdj != nullptr) { |
71 | 0 | eSame = eAdj->find(dest); |
72 | 0 | } |
73 | 0 | if (eSame != nullptr) { |
74 | 0 | return eSame; |
75 | 0 | } |
76 | | |
77 | 0 | HalfEdge* e = insert(orig, dest, eAdj); |
78 | 0 | return e; |
79 | 0 | } |
80 | | |
81 | | /*public static*/ |
82 | | bool |
83 | | EdgeGraph::isValidEdge(const CoordinateXY& orig, const CoordinateXY& dest) |
84 | 0 | { |
85 | 0 | return dest.compareTo(orig) != 0; |
86 | 0 | } |
87 | | |
88 | | /*private*/ |
89 | | HalfEdge* |
90 | | EdgeGraph::insert(const CoordinateXYZM& orig, const CoordinateXYZM& dest, HalfEdge* eAdj) |
91 | 0 | { |
92 | | // edge does not exist, so create it and insert in graph |
93 | 0 | HalfEdge* e = create(orig, dest); |
94 | 0 | if (eAdj != nullptr) { |
95 | 0 | eAdj->insert(e); |
96 | 0 | } |
97 | 0 | else { |
98 | | // add halfedges to to map |
99 | 0 | vertexMap[orig] = e; |
100 | 0 | } |
101 | |
|
102 | 0 | HalfEdge* eAdjDest = nullptr; |
103 | 0 | auto it = vertexMap.find(dest); |
104 | 0 | if (it != vertexMap.end()) { |
105 | 0 | eAdjDest = it->second; |
106 | 0 | } |
107 | 0 | if (eAdjDest != nullptr) { |
108 | 0 | eAdjDest->insert(e->sym()); |
109 | 0 | } |
110 | 0 | else { |
111 | 0 | vertexMap[dest] = e->sym(); |
112 | 0 | } |
113 | 0 | return e; |
114 | 0 | } |
115 | | |
116 | | /*public*/ |
117 | | void |
118 | | EdgeGraph::getVertexEdges(std::vector<const HalfEdge*>& edgesOut) |
119 | 0 | { |
120 | 0 | for (auto it = vertexMap.begin(); it != vertexMap.end(); ++it) { |
121 | 0 | edgesOut.push_back(it->second); |
122 | 0 | } |
123 | 0 | return; |
124 | 0 | } |
125 | | |
126 | | /*public*/ |
127 | | HalfEdge* |
128 | | EdgeGraph::findEdge(const CoordinateXY& orig, const CoordinateXY& dest) |
129 | 0 | { |
130 | 0 | HalfEdge* e = nullptr; |
131 | 0 | auto it = vertexMap.find(orig); |
132 | 0 | if (it != vertexMap.end()) { |
133 | 0 | e = it->second; |
134 | 0 | } |
135 | 0 | if (e == nullptr) { |
136 | 0 | return nullptr; |
137 | 0 | } |
138 | 0 | return e->find(dest); |
139 | 0 | } |
140 | | |
141 | | |
142 | | |
143 | | } // namespace geos.edgegraph |
144 | | } // namespace geos |