PGROUTING  3.2
xy_vertex.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2  *
3 
4  Copyright (c) 2015 Celia Virginia Vergara Castillo
6 
7  ------
8 
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
13 
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 
23  ********************************************************************PGR-GNU*/
24 
25 #include "cpp_common/xy_vertex.h"
26 #include <boost/geometry/io/wkt/write.hpp>
27 
28 #include <vector>
29 #include <limits>
30 #include <algorithm>
31 
32 #include "cpp_common/pgr_assert.h"
33 
34 namespace {
35 
36 template<typename T>
37 typename std::enable_if<!std::numeric_limits<T>::is_integer, bool>::type
38  almost_equal(T x, T y, int ulp) {
39  // the machine epsilon has to be scaled to the magnitude of the values used
40  // and multiplied by the desired precision in ULPs (units in the last place)
41  return std::abs(x-y) <= std::numeric_limits<T>::epsilon() * std::abs(x+y) * ulp
42  // unless the result is subnormal
43  || std::abs(x-y) < std::numeric_limits<T>::min();
44 }
45 
46 } // namespace
47 
48 namespace pgrouting {
49 
50 
51 std::ostream& operator<<(std::ostream& log, const XY_vertex &v) {
52  log << v.id << "-" << bg::wkt(v.point);
53  return log;
54 }
55 
56 bool
57 XY_vertex::operator==(const XY_vertex &rhs) const {
58  if (&rhs == this) return true;
59  return this->id == rhs.id &&
60  almost_equal(point.x(), rhs.point.x(), 2) && almost_equal(point.y(), rhs.point.y(), 2);
61 }
62 
63 
64 size_t
66  std::vector < XY_vertex > vertices) {
67  auto count(vertices.size());
68  std::stable_sort(
69  vertices.begin(), vertices.end(),
70  [](const XY_vertex &lhs, const XY_vertex &rhs)
71  {return lhs.id < rhs.id;});
72  vertices.erase(
73  std::unique(
74  vertices.begin(), vertices.end(),
75  [](const XY_vertex &lhs, const XY_vertex &rhs)
76  {return lhs.id == rhs.id;}), vertices.end());
77 
78  return count - vertices.size();
79 }
80 
81 std::vector < XY_vertex >
83  const std::vector <Pgr_edge_xy_t > &data_edges) {
84 
85  std::vector< XY_vertex > vertices;
86  if (data_edges.empty()) return vertices;
87 
88  vertices.reserve(data_edges.size() * 2);
89 
90  for (const auto &edge : data_edges) {
91  XY_vertex v_source(edge, true);
92  vertices.push_back(v_source);
93 
94  XY_vertex v_target(edge, false);
95  vertices.push_back(v_target);
96  }
97 
98  /*
99  * sort and delete duplicates
100  */
101  std::stable_sort(
102  vertices.begin(), vertices.end(),
103  [](const XY_vertex &lhs, const XY_vertex &rhs)
104  {return lhs.id < rhs.id;});
105  vertices.erase(
106  std::unique(
107  vertices.begin(), vertices.end(),
108  [](const XY_vertex &lhs, const XY_vertex &rhs)
109  {return lhs.id == rhs.id;}), vertices.end());
110  return vertices;
111 }
112 
113 std::vector < XY_vertex >
115  const Pgr_edge_xy_t *data_edges, size_t count) {
116  return extract_vertices(
117  std::vector < Pgr_edge_xy_t >(data_edges, data_edges + count));
118 }
119 
120 #if 0
121 /* the following might be needed when using withPoints */
122 std::vector < XY_vertex > extract_vertices(
123  std::vector < XY_vertex > vertices,
124  const std::vector < Pgr_edge_xy_t > data_edges) {
125  if (data_edges.empty()) return vertices;
126 
127  vertices.reserve(vertices.size() + data_edges.size() * 2);
128 
129  for (const auto edge : data_edges) {
130  vertices.push_back(XY_vertex(edge.source, edge.x1, edge.y1));
131  vertices.push_back(XY_vertex(edge.target, edge.x2, edge.y2));
132  }
133 
134  /*
135  * sort and delete duplicates
136  */
137  std::stable_sort(vertices.begin(), vertices.end(),
138  [](const XY_vertex &lhs, const XY_vertex &rhs)
139  {return lhs.id < rhs.id;});
140 
141  vertices.erase(
142  std::unique(vertices.begin(), vertices.end(),
143  [](const XY_vertex &lhs, const XY_vertex &rhs)
144  {return lhs.id == rhs.id;}), vertices.end());
145  return vertices;
146 }
147 std::vector < XY_vertex > extract_vertices(
148  std::vector < XY_vertex > vertices,
149  const Pgr_edge_xy_t *data_edges, int64_t count) {
150  return extract_vertices(vertices,
151  std::vector < Pgr_edge_xy_t >(data_edges, data_edges + count));
152 }
153 #endif
154 
155 } // namespace pgrouting
pgrouting::XY_vertex
Definition: xy_vertex.h:40
pgrouting::XY_vertex::id
int64_t id
Definition: xy_vertex.h:66
anonymous_namespace{xy_vertex.cpp}::almost_equal
std::enable_if<!std::numeric_limits< T >::is_integer, bool >::type almost_equal(T x, T y, int ulp)
Definition: xy_vertex.cpp:38
edge::target
int64 target
Definition: trsp.h:44
pgrouting::check_vertices
size_t check_vertices(std::vector< Basic_vertex > vertices)
Definition: basic_vertex.cpp:42
pgrouting::XY_vertex::operator==
bool operator==(const XY_vertex &rhs) const
Definition: xy_vertex.cpp:57
edge
Definition: trsp.h:41
pgrouting::XY_vertex::point
Bpoint point
Definition: xy_vertex.h:67
pgrouting::operator<<
std::ostream & operator<<(std::ostream &log, const Basic_vertex &v)
Definition: basic_vertex.cpp:37
edge::source
int64 source
Definition: trsp.h:43
xy_vertex.h
pgr_assert.h
An assert functionality that uses C++ throw().
pgrouting::extract_vertices
std::vector< Basic_vertex > extract_vertices(std::vector< Basic_vertex > vertices, const std::vector< pgr_edge_t > data_edges)
Definition: basic_vertex.cpp:59
Pgr_edge_xy_t
Definition: pgr_edge_xy_t.h:38
pgrouting
Book keeping class for swapping orders between vehicles.
Definition: pgr_alphaShape.cpp:56