PGROUTING  3.1
xy_vertex.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2  *
3 
4  Copyright (c) 2015 Celia Virginia Vergara Castillo
5  vicky_vergara@hotmail.com
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 #if Boost_VERSION_MACRO >= 105600
27 #include <boost/geometry/io/wkt/write.hpp>
28 #else
29 #include <boost/bgeometry/io/wkt/write.hpp>
30 #endif
31 
32 #include <vector>
33 #include <limits>
34 #include <algorithm>
35 
36 #include "cpp_common/pgr_assert.h"
37 
38 namespace {
39 
40 template<typename T>
41 typename std::enable_if<!std::numeric_limits<T>::is_integer, bool>::type
42  almost_equal(T x, T y, int ulp) {
43  // the machine epsilon has to be scaled to the magnitude of the values used
44  // and multiplied by the desired precision in ULPs (units in the last place)
45  return std::abs(x-y) <= std::numeric_limits<T>::epsilon() * std::abs(x+y) * ulp
46  // unless the result is subnormal
47  || std::abs(x-y) < std::numeric_limits<T>::min();
48 }
49 
50 } // namespace
51 
52 namespace pgrouting {
53 
54 
55 std::ostream& operator<<(std::ostream& log, const XY_vertex &v) {
56  log << v.id << "-" << bg::wkt(v.point);
57  return log;
58 }
59 
60 bool
61 XY_vertex::operator==(const XY_vertex &rhs) const {
62  if (&rhs == this) return true;
63  return this->id == rhs.id &&
64  almost_equal(point.x(), rhs.point.x(), 2) && almost_equal(point.y(), rhs.point.y(), 2);
65 }
66 
67 
68 size_t
70  std::vector < XY_vertex > vertices) {
71  auto count(vertices.size());
72  std::stable_sort(
73  vertices.begin(), vertices.end(),
74  [](const XY_vertex &lhs, const XY_vertex &rhs)
75  {return lhs.id < rhs.id;});
76  vertices.erase(
77  std::unique(
78  vertices.begin(), vertices.end(),
79  [](const XY_vertex &lhs, const XY_vertex &rhs)
80  {return lhs.id == rhs.id;}), vertices.end());
81 
82  return count - vertices.size();
83 }
84 
85 std::vector < XY_vertex >
87  const std::vector <Pgr_edge_xy_t > &data_edges) {
88 
89  std::vector< XY_vertex > vertices;
90  if (data_edges.empty()) return vertices;
91 
92  vertices.reserve(data_edges.size() * 2);
93 
94  for (const auto &edge : data_edges) {
95  XY_vertex v_source(edge, true);
96  vertices.push_back(v_source);
97 
98  XY_vertex v_target(edge, false);
99  vertices.push_back(v_target);
100  }
101 
102  /*
103  * sort and delete duplicates
104  */
105  std::stable_sort(
106  vertices.begin(), vertices.end(),
107  [](const XY_vertex &lhs, const XY_vertex &rhs)
108  {return lhs.id < rhs.id;});
109  vertices.erase(
110  std::unique(
111  vertices.begin(), vertices.end(),
112  [](const XY_vertex &lhs, const XY_vertex &rhs)
113  {return lhs.id == rhs.id;}), vertices.end());
114  return vertices;
115 }
116 
117 std::vector < XY_vertex >
119  const Pgr_edge_xy_t *data_edges, size_t count) {
120  return extract_vertices(
121  std::vector < Pgr_edge_xy_t >(data_edges, data_edges + count));
122 }
123 
124 #if 0
125 /* the following might be needed when using withPoints */
126 std::vector < XY_vertex > extract_vertices(
127  std::vector < XY_vertex > vertices,
128  const std::vector < Pgr_edge_xy_t > data_edges) {
129  if (data_edges.empty()) return vertices;
130 
131  vertices.reserve(vertices.size() + data_edges.size() * 2);
132 
133  for (const auto edge : data_edges) {
134  vertices.push_back(XY_vertex(edge.source, edge.x1, edge.y1));
135  vertices.push_back(XY_vertex(edge.target, edge.x2, edge.y2));
136  }
137 
138  /*
139  * sort and delete duplicates
140  */
141  std::stable_sort(vertices.begin(), vertices.end(),
142  [](const XY_vertex &lhs, const XY_vertex &rhs)
143  {return lhs.id < rhs.id;});
144 
145  vertices.erase(
146  std::unique(vertices.begin(), vertices.end(),
147  [](const XY_vertex &lhs, const XY_vertex &rhs)
148  {return lhs.id == rhs.id;}), vertices.end());
149  return vertices;
150 }
151 std::vector < XY_vertex > extract_vertices(
152  std::vector < XY_vertex > vertices,
153  const Pgr_edge_xy_t *data_edges, int64_t count) {
154  return extract_vertices(vertices,
155  std::vector < Pgr_edge_xy_t >(data_edges, data_edges + count));
156 }
157 #endif
158 
159 } // namespace pgrouting
int64 target
Definition: trsp.h:44
Definition: trsp.h:41
std::ostream & operator<<(std::ostream &log, const Basic_vertex &v)
bool operator==(const XY_vertex &rhs) const
Definition: xy_vertex.cpp:61
int64 source
Definition: trsp.h:43
std::vector< Basic_vertex > extract_vertices(std::vector< Basic_vertex > vertices, const std::vector< pgr_edge_t > data_edges)
Book keeping class for swapping orders between vehicles.
Assertions Handling.
size_t check_vertices(std::vector< Basic_vertex > vertices)
std::enable_if<!std::numeric_limits< T >::is_integer, bool >::type almost_equal(T x, T y, int ulp)
Definition: xy_vertex.cpp:42