pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_withPoints.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_withPoints.cpp
3 
4 Generated with Template by:
5 Copyright (c) 2015 pgRouting developers
6 Mail: project@pgrouting.org
7 
8 Function's developer:
9 Copyright (c) 2015 Celia Virginia Vergara Castillo
10 Mail:
11 
12 ------
13 
14 This program is free software; you can redistribute it and/or modify
15 it under the terms of the GNU General Public License as published by
16 the Free Software Foundation; either version 2 of the License, or
17 (at your option) any later version.
18 
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 GNU General Public License for more details.
23 
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 
28 ********************************************************************PGR-GNU*/
29 
30 
31 #if defined(__MINGW32__) || defined(_MSC_VER)
32 #include <winsock2.h>
33 #include <windows.h>
34 #endif
35 
36 
37 #include <sstream>
38 #include <deque>
39 #include <set>
40 #include <vector>
41 #include <algorithm>
42 #include <cassert>
43 #include "./pgr_withPoints.hpp"
44 #include "./msg_logger.hpp"
45 
46 #include "./../../common/src/pgr_types.h"
47 
48 /*
49  * 0 = success
50  * non 0 = error code
51  */
52 
53 int check_points(std::vector< Point_on_edge_t > &points,
54  std::ostringstream &log) {
55  PGR_LOG_POINTS(log, points, "original points");
56  /*
57  * deleting duplicate points
58  */
59  std::sort(points.begin(), points.end(),
60  [](const Point_on_edge_t &a, const Point_on_edge_t &b)
61  -> bool {
62  if (a.pid != b.pid) return a.pid < b.pid;
63  if (a.edge_id != b.edge_id) return a.edge_id < b.edge_id;
64  if (a.fraction != b.fraction) return a.fraction < b.fraction;
65  return a.side < b.side;
66  });
67  PGR_LOG_POINTS(log, points, "after sorting");
68  auto last = std::unique(points.begin(), points.end(),
69  [](const Point_on_edge_t &a, const Point_on_edge_t &b) {
70  return a.pid == b.pid &&
71  a.edge_id == b.edge_id &&
72  a.fraction == b.fraction &&
73  a.side == b.side;
74  });
75  points.erase(last, points.end());
76  size_t total_points = points.size();
77 
78  PGR_LOG_POINTS(log, points, "after deleting repetitions");
79  log << "We have " << total_points << " different points";
80 
81  last = std::unique(points.begin(), points.end(),
82  [](const Point_on_edge_t &a, const Point_on_edge_t &b) {
83  return a.pid == b.pid;
84  });
85  points.erase(last, points.end());
86  PGR_LOG_POINTS(log, points, "after deleting points with same id");
87 
88  if (points.size() != total_points) {
89  return 1;
90  }
91  return 0;
92 }
93 
94 
95 void
97  Path &path) {
98  /*
99  * There is no path nothing to do
100  */
101  if (path.empty()) return;
102 
103  Path newPath(path.start_id(), path.end_id());
104  for (const auto &pathstop : path) {
105  if ((pathstop.node == path.start_id())
106  || (pathstop.node == path.end_id())
107  || (pathstop.node > 0)) {
108  newPath.push_back(pathstop);
109  }
110  }
111 
112  path = newPath;
113 }
114 
115 
116 void
118  Path &path,
119  const std::vector< pgr_edge_t > &point_edges) {
120  /*
121  * There is no path nothing to do
122  */
123  if (path.empty()) return;
124 
125  Path newPath(path.start_id(), path.end_id());
126  double cost = 0.0;
127  for (const auto &pathstop : path) {
128  if ((pathstop.node == path.start_id())
129  || (pathstop.node == path.end_id())
130  || (pathstop.node > 0)) {
131  newPath.push_back(pathstop);
132  if (pathstop.node != path.end_id()) cost = 0.0;
133  continue;
134  }
135  cost += pathstop.cost;
136  }
137 
138  newPath[0].cost = newPath[1].agg_cost;
139  for (unsigned int i = 1; i < newPath.size() - 2; ++i) {
140  /* newPath[i] has: node, edge, cost, agg_cost
141  * pgr_type_t has: id, source, target, cost, reverse_cost
142  *
143  * find the edge where the pathstop.edge == edge.id */
144 
145  int64_t edge_to_find = newPath[i].edge;
146  auto edge_ptr = std::find_if(point_edges.begin(), point_edges.end(),
147  [&edge_to_find](const pgr_edge_t &edge)
148  {return edge_to_find == edge.id;});
149  if (edge_ptr != point_edges.end()) {
150  newPath[i].cost = edge_ptr->target == newPath[i+1].node ?
151  edge_ptr->cost : edge_ptr->reverse_cost;
152  }
153  }
154  newPath[newPath.size()-2].cost += cost;
155 
156 
157  path = newPath;
158 }
159 
160 
161 static void
163  const std::vector< Point_on_edge_t > &points,
164  const int64_t &start_pid,
165  const int64_t &end_pid,
166  Path &path) {
167  if (path.empty()) return;
168  path.start_id(start_pid);
169  path.end_id(end_pid);
170 
171  for (auto &path_stop : path) {
172  for (const auto point : points) {
173  if (point.vertex_id == path_stop.node) {
174  path_stop.node = -point.pid;
175  break;
176  }
177  }
178  }
179 }
180 
181 void
183  const std::vector< Point_on_edge_t > &points,
184  Path &path) {
185  /*
186  * There is no path nothing to do
187  */
188  if (path.empty()) return;
189  /* from, to:
190  * * are constant along the path
191  * */
192  int64_t start_vid = path.start_id();
193  int64_t end_vid = path.end_id();
194 
195  int64_t start_pid = 0;
196  int64_t end_pid = 0;
197 
198  for (auto &p : points) {
199  if (p.vertex_id == start_vid) {
200  start_pid = -p.pid;
201  }
202  if (p.vertex_id == end_vid) {
203  end_pid = -p.pid;
204  }
205  }
206  adjust_pids(points, start_pid, end_pid, path);
207 }
208 
209 
210 struct pointCompare {
211  bool operator() (const Point_on_edge_t& lhs, const Point_on_edge_t& rhs) const
212  { return lhs.fraction < rhs.fraction? true : lhs.pid < rhs.pid;}
213 };
214 
215 bool
217  std::vector< Point_on_edge_t > &points,
218  const std::vector< pgr_edge_t > &edges,
219  char driving_side,
220  std::vector< pgr_edge_t > &new_edges) {
221  std::ostringstream log;
222  return create_new_edges( points, edges, driving_side, new_edges, log);
223 }
224 
225 
226 
227 bool
229  std::vector< Point_on_edge_t > &points,
230  const std::vector< pgr_edge_t > &edges,
231  char driving_side,
232  std::vector< pgr_edge_t > &new_edges,
233  std::ostringstream &log) {
234  for (const auto &point : points) {
235  log << "point: "
236  << point.pid << "\t"
237  << point.edge_id << "\t"
238  << point.fraction << "\t"
239  << point.side << "\t"
240  << point.vertex_id << "\n";
241  }
242 
243  int64_t vertex_id = 1;
244  std::vector< Point_on_edge_t > new_points;
245  for (const auto edge : edges) {
246  std::set< Point_on_edge_t, pointCompare> points_on_edge;
247  for (const auto point : points) {
248  if (edge.id == point.edge_id) {
249  points_on_edge.insert(point);
250  log << "working points: "
251  << point.pid << "\t"
252  << point.edge_id << "\t"
253  << point.fraction << "\t"
254  << point.side << "\t"
255  << point.vertex_id << "\n";
256  }
257  }
258  if (points_on_edge.empty()) {
259  log << "For some reason we didn't find a point belonging to the edge, must be an error\n";
260  return false;
261  }
262 #if 0
263  log << "breaking: \n"
264  << edge.id << "\t"
265  << edge.source << "\t"
266  << edge.target << "\t"
267  << edge.cost << "\t"
268  << edge.reverse_cost << "\n";
269 #endif
270  int64_t prev_target = edge.source;
271  int64_t prev_rtarget = edge.source;
272  double prev_fraction = 0;
273  double prev_rfraction = 0;
274  double agg_cost = 0;
275  double agg_rcost = 0;
276  double last_cost = 0;
277  double last_rcost = 0;
278  std::vector< Point_on_edge_t> the_points(points_on_edge.begin(), points_on_edge.end());
279 
280  for (auto &point : the_points) {
281  /* the point either has
282  * vertex_id = source
283  * vertex_id = target
284  * vertex_id = -newnumber
285  */
286  log << "\npid"
287  << point.pid
288  << "\teid" << point.edge_id
289  << "/t" << point.fraction
290  << "\t" << point.side << "\n";
291  if (point.fraction <= 0 || point.fraction >= 1) {
292  log << "For some reason an invalid fraction was accepted, must be an error\n";
293  return false;
294  }
295  if (point.fraction == 0) {
296  log << "vertex_id of the point is the source" << edge.source << "\n";
297  point.vertex_id = edge.source;
298  }
299  if (point.fraction == 1) {
300  log << "vertex_id of the point is the target" << edge.target << "\n";
301  point.vertex_id = edge.target;
302  }
303  if (point.fraction > 0 && point.fraction < 1) {
304  log << "vertex_id of the point is " << -point.pid << "\n";
305  point.vertex_id = -point.pid;
306  ++vertex_id;
307  }
308  new_points.push_back(point);
309 
310  double deltaFraction = point.fraction - prev_fraction;
311  double deltarFraction = point.fraction - prev_rfraction;
312  if ((edge.cost < 0 || edge.reverse_cost < 0)
313  || driving_side == 'b'
314  || point.side == 'b') {
315  log << "Edge is one way or driving side is both or point side is both\n";
316  log << "Edge is one way: " << (edge.cost < 0 || edge.reverse_cost < 0) << "\n";
317  log << "driving side: " << driving_side << "\n";
318  log << "point side: " << point.side << "\n";
319  if (point.fraction > 0 && point.fraction < 1) {
320  if (edge.cost >= 0) {
321  last_cost = deltaFraction * edge.cost;
322  pgr_edge_t new_edge = {edge.id , prev_target, point.vertex_id, last_cost, -1};
323  new_edges.push_back(new_edge);
324  log << "new_edge: (id, source, target, cost, reverse_cost) = ("
325  << new_edge.id << "\t"
326  << new_edge.source << "\t"
327  << new_edge.target << "\t"
328  << new_edge.cost << "\t"
329  << new_edge.reverse_cost << ")\n";
330  }
331  if (edge.reverse_cost >= 0) {
332  last_rcost = deltarFraction * edge.reverse_cost;
333  pgr_edge_t new_edge = {edge.id , prev_target, point.vertex_id, -1, last_rcost};
334  new_edges.push_back(new_edge);
335  log << "new_edge: (id, source, target, cost, reverse_cost) = ("
336  << new_edge.id << "\t"
337  << new_edge.source << "\t"
338  << new_edge.target << "\t"
339  << new_edge.cost << "\t"
340  << new_edge.reverse_cost << ")\n";
341  }
342  }
343  prev_target = point.vertex_id;
344  prev_fraction = point.fraction;
345  agg_cost += last_cost;
346 
347  prev_rtarget = point.vertex_id;
348  prev_rfraction = point.fraction;
349  agg_rcost += last_rcost;
350  continue;
351  }
352 
353  assert(edge.cost > 0 && edge.reverse_cost > 0);
354  assert(point.side != 'b');
355 
356  if (driving_side == point.side) {
357  log << "two way and driving side is == than the side of the point\n";
358  log << "Breaking (source, target) edge only when its not the extreme of the segment\n";
359  if (point.fraction > 0 && point.fraction < 1) {
360  last_cost = deltaFraction * edge.cost;
361  pgr_edge_t new_edge = {edge.id , prev_target, point.vertex_id, last_cost, -1};
362  new_edges.push_back(new_edge);
363  log << "new_edge: (id, source, target, cost, reverse_cost) = ("
364  << new_edge.id << "\t"
365  << new_edge.source << "\t"
366  << new_edge.target << "\t"
367  << new_edge.cost << "\t"
368  << new_edge.reverse_cost << ")\n";
369  }
370  prev_target = point.vertex_id;
371  prev_fraction = point.fraction;
372  agg_cost += last_cost;
373  continue;
374  }
375 
376  log << "two way and driving side is != than the side of the point\n";
377  if (point.fraction > 0 && point.fraction < 1) {
378  last_rcost = deltarFraction * edge.reverse_cost;
379  pgr_edge_t new_edge = {
380  edge.id,
381  prev_rtarget,
382  point.vertex_id,
383  -1,
384  last_rcost};
385  new_edges.push_back(new_edge);
386  log << "new_edge: (id, source, target, cost, reverse_cost) = ("
387  << new_edge.id << "\t"
388  << new_edge.source << "\t"
389  << new_edge.target << "\t"
390  << new_edge.cost << "\t"
391  << new_edge.reverse_cost << ")\n";
392  }
393  prev_rtarget = point.vertex_id;
394  prev_rfraction = point.fraction;
395  agg_rcost += last_rcost;
396  }
397 
398  { // the last segments
399  pgr_edge_t new_edge = {
400  edge.id,
401  prev_target,
402  edge.target,
403  (edge.cost - agg_cost),
404  -1};
405  new_edges.push_back(new_edge);
406  log << "last edge: (id, source, target, cost, reverse_cost) = ("
407  << new_edge.id << "\t"
408  << new_edge.source << "\t"
409  << new_edge.target << "\t"
410  << new_edge.cost << "\t"
411  << new_edge.reverse_cost << ")\n";
412 
413  new_edge = {edge.id , prev_rtarget, edge.target,
414  -1, (edge.reverse_cost - agg_rcost)};
415  new_edges.push_back(new_edge);
416  log << "last edge: (id, source, target, cost, reverse_cost) = ("
417  << new_edge.id << "\t"
418  << new_edge.source << "\t"
419  << new_edge.target << "\t"
420  << new_edge.cost << "\t"
421  << new_edge.reverse_cost << ")\n";
422  }
423  }
424 
425  points = new_points;
426  for (const auto &point : points) {
427  log << "point: "
428  << point.pid << "\t"
429  << point.edge_id << "\t"
430  << point.fraction << "\t"
431  << point.side << "\t"
432  << point.vertex_id << "\n";
433  }
434  return true;
435 }
double cost
double reverse_cost
Definition: pgr_types.h:132
int64_t source
Definition: pgr_types.h:129
void eliminate_details(Path &path, const std::vector< pgr_edge_t > &point_edges)
int64_t target
Definition: pgr_types.h:130
double fraction
Definition: pgr_types.h:170
static int a
Definition: tsplib.c:114
static void adjust_pids(const std::vector< Point_on_edge_t > &points, const int64_t &start_pid, const int64_t &end_pid, Path &path)
void push_back(Path_t data)
int64_t end_id() const
bool operator()(const Point_on_edge_t &lhs, const Point_on_edge_t &rhs) const
int check_points(std::vector< Point_on_edge_t > &points, std::ostringstream &log)
int64_t id
Definition: pgr_types.h:128
int64_t edge_id
Definition: pgr_types.h:168
double cost
Definition: pgr_types.h:131
edge_astar_t * edges
Definition: BDATester.cpp:46
bool create_new_edges(std::vector< Point_on_edge_t > &points, const std::vector< pgr_edge_t > &edges, char driving_side, std::vector< pgr_edge_t > &new_edges)
static int b
Definition: tsplib.c:115
void eliminate_details_dd(Path &path)
int64_t start_id() const
void PGR_LOG_POINTS(std::ostringstream &log, const std::vector< Point_on_edge_t > &points, const std::string &title)
Definition: msg_logger.hpp:36
Definition: tsp.h:38
bool empty() const
path_element_t * path
Definition: BDATester.cpp:49
double reverse_cost