PGROUTING  2.4
 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 #include "./pgr_withPoints.hpp"
32 
33 #include <sstream>
34 #include <deque>
35 #include <set>
36 #include <vector>
37 #include <string>
38 #include <algorithm>
39 #include <cassert>
40 
41 #include "./../../common/src/pgr_assert.h"
42 #include "./../../common/src/pgr_types.h"
43 
44 static
45 void
47  std::ostringstream &log,
48  const std::vector< Point_on_edge_t > &points,
49  const std::string &title) {
50  log << title << "\n";
51  for (const auto &p : points) {
52  log << p.pid << "\t"
53  << p.edge_id << "\t"
54  << p.fraction << "\t"
55  << p.side << "\n";
56  }
57 }
58 
59 /*
60  * 0 = success
61  * non 0 = error code
62  */
63 
64 int check_points(std::vector< Point_on_edge_t > &points,
65  std::ostringstream &log) {
66  PGR_LOG_POINTS(log, points, "original points");
67  /*
68  * deleting duplicate points
69  */
70  std::sort(points.begin(), points.end(),
71  [](const Point_on_edge_t &a, const Point_on_edge_t &b)
72  -> bool {
73  if (a.pid != b.pid) return a.pid < b.pid;
74  if (a.edge_id != b.edge_id) return a.edge_id < b.edge_id;
75  if (a.fraction != b.fraction) return a.fraction < b.fraction;
76  return a.side < b.side;
77  });
78  PGR_LOG_POINTS(log, points, "after sorting");
79  auto last = std::unique(points.begin(), points.end(),
80  [](const Point_on_edge_t &a, const Point_on_edge_t &b) {
81  return a.pid == b.pid &&
82  a.edge_id == b.edge_id &&
83  a.fraction == b.fraction &&
84  a.side == b.side;
85  });
86  points.erase(last, points.end());
87  size_t total_points = points.size();
88 
89  PGR_LOG_POINTS(log, points, "after deleting repetitions");
90  log << "We have " << total_points << " different points";
91 
92  last = std::unique(points.begin(), points.end(),
93  [](const Point_on_edge_t &a, const Point_on_edge_t &b) {
94  return a.pid == b.pid;
95  });
96  points.erase(last, points.end());
97  PGR_LOG_POINTS(log, points, "after deleting points with same id");
98 
99  if (points.size() != total_points) {
100  return 1;
101  }
102  return 0;
103 }
104 
105 
106 void
108  Path &path) {
109  /*
110  * There is no path nothing to do
111  */
112  if (path.empty()) return;
113 
114  Path newPath(path.start_id(), path.end_id());
115  for (const auto &pathstop : path) {
116  if ((pathstop.node == path.start_id())
117  || (pathstop.node == path.end_id())
118  || (pathstop.node > 0)) {
119  newPath.push_back(pathstop);
120  }
121  }
122 
123  path = newPath;
124 }
125 
126 
127 void
129  Path &path,
130  const std::vector< pgr_edge_t > &point_edges) {
131  /*
132  * There is no path nothing to do
133  */
134  if (path.empty()) return;
135 
136  Path newPath(path.start_id(), path.end_id());
137  double cost = 0.0;
138  for (const auto &pathstop : path) {
139  if ((pathstop.node == path.start_id())
140  || (pathstop.node == path.end_id())
141  || (pathstop.node > 0)) {
142  newPath.push_back(pathstop);
143  if (pathstop.node != path.end_id()) cost = 0.0;
144  continue;
145  }
146  cost += pathstop.cost;
147  }
148 
149  newPath[0].cost = newPath[1].agg_cost;
150  for (unsigned int i = 1; i < newPath.size() - 2; ++i) {
151  /* newPath[i] has: node, edge, cost, agg_cost
152  * pgr_type_t has: id, source, target, cost, reverse_cost
153  *
154  * find the edge where the pathstop.edge == edge.id */
155 
156  int64_t edge_to_find = newPath[i].edge;
157  auto edge_ptr = std::find_if(point_edges.begin(), point_edges.end(),
158  [&edge_to_find](const pgr_edge_t &edge)
159  {return edge_to_find == edge.id;});
160  if (edge_ptr != point_edges.end()) {
161  newPath[i].cost = edge_ptr->target == newPath[i+1].node ?
162  edge_ptr->cost : edge_ptr->reverse_cost;
163  }
164  }
165  newPath[newPath.size()-2].cost += cost;
166 
167 
168  path = newPath;
169 }
170 
171 
172 static void
174  const std::vector< Point_on_edge_t > &points,
175  const int64_t &start_pid,
176  const int64_t &end_pid,
177  Path &path) {
178  if (path.empty()) return;
179  path.start_id(start_pid);
180  path.end_id(end_pid);
181 
182  for (auto &path_stop : path) {
183  for (const auto point : points) {
184  if (point.vertex_id == path_stop.node) {
185  path_stop.node = -point.pid;
186  break;
187  }
188  }
189  }
190 }
191 
192 void
194  const std::vector< Point_on_edge_t > &points,
195  Path &path) {
196  /*
197  * There is no path nothing to do
198  */
199  if (path.empty()) return;
200  /* from, to:
201  * * are constant along the path
202  * */
203  int64_t start_vid = path.start_id();
204  int64_t end_vid = path.end_id();
205 
206  int64_t start_pid = 0;
207  int64_t end_pid = 0;
208 
209  for (auto &p : points) {
210  if (p.vertex_id == start_vid) {
211  start_pid = -p.pid;
212  }
213  if (p.vertex_id == end_vid) {
214  end_pid = -p.pid;
215  }
216  }
217  adjust_pids(points, start_pid, end_pid, path);
218 }
219 
220 
221 struct pointCompare {
223  const Point_on_edge_t& lhs,
224  const Point_on_edge_t& rhs) const
225  {return lhs.fraction < rhs.fraction? true : lhs.pid < rhs.pid;}
226 };
227 
228 bool
230  std::vector< Point_on_edge_t > &points,
231  const std::vector< pgr_edge_t > &edges,
232  char driving_side,
233  std::vector< pgr_edge_t > &new_edges) {
234  std::ostringstream log;
235  return create_new_edges( points, edges, driving_side, new_edges, log);
236 }
237 
238 
239 
240 bool
242  std::vector< Point_on_edge_t > &points,
243  const std::vector< pgr_edge_t > &edges,
244  char driving_side,
245  std::vector< pgr_edge_t > &new_edges,
246  std::ostringstream &log) {
247  for (const auto &point : points) {
248  log << "point: "
249  << point.pid << "\t"
250  << point.edge_id << "\t"
251  << point.fraction << "\t"
252  << point.side << "\t"
253  << point.vertex_id << "\n";
254  }
255 
256  int64_t vertex_id = 1;
257  std::vector< Point_on_edge_t > new_points;
258  for (const auto edge : edges) {
259  std::set< Point_on_edge_t, pointCompare> points_on_edge;
260  for (const auto point : points) {
261  if (edge.id == point.edge_id) {
262  points_on_edge.insert(point);
263  log << "working points: "
264  << point.pid << "\t"
265  << point.edge_id << "\t"
266  << point.fraction << "\t"
267  << point.side << "\t"
268  << point.vertex_id << "\n";
269  }
270  }
271  if (points_on_edge.empty()) {
272  log << "For some reason didn't find a point belonging to the edge"
273  << ", must be an error\n";
274  return false;
275  }
276 #if 0
277  log << "breaking: \n"
278  << edge.id << "\t"
279  << edge.source << "\t"
280  << edge.target << "\t"
281  << edge.cost << "\t"
282  << edge.reverse_cost << "\n";
283 #endif
284  int64_t prev_target = edge.source;
285  int64_t prev_rtarget = edge.source;
286  double prev_fraction = 0;
287  double prev_rfraction = 0;
288  double agg_cost = 0;
289  double agg_rcost = 0;
290  double last_cost = 0;
291  double last_rcost = 0;
292  std::vector<Point_on_edge_t> the_points(
293  points_on_edge.begin(), points_on_edge.end());
294 
295  for (auto &point : the_points) {
296  /* the point either has
297  * vertex_id = source
298  * vertex_id = target
299  * vertex_id = -newnumber
300  */
301  log << "\npid"
302  << point.pid
303  << "\teid" << point.edge_id
304  << "/t" << point.fraction
305  << "\t" << point.side << "\n";
306  if (point.fraction <= 0 || point.fraction >= 1) {
307  log << "For some reason an invalid fraction was accepted,"
308  << " must be an error\n";
309  return false;
310  }
311  if (point.fraction == 0) {
312  log << "Point's vertex_id = source" << edge.source << "\n";
313  point.vertex_id = edge.source;
314  }
315  if (point.fraction == 1) {
316  log << "point's vertex_id = target" << edge.target << "\n";
317  point.vertex_id = edge.target;
318  }
319  if (point.fraction > 0 && point.fraction < 1) {
320  log << "vertex_id of the point is " << -point.pid << "\n";
321  point.vertex_id = -point.pid;
322  ++vertex_id;
323  }
324  new_points.push_back(point);
325 
326  double deltaFraction = point.fraction - prev_fraction;
327  double deltarFraction = point.fraction - prev_rfraction;
328  if ((edge.cost < 0 || edge.reverse_cost < 0)
329  || driving_side == 'b'
330  || point.side == 'b') {
331  log << "Edge is one way "
332  << " or driving side is both or point side is both\n";
333  log << "Edge is one way: "
334  << (edge.cost < 0 || edge.reverse_cost < 0)
335  << "\n";
336  log << "driving side: " << driving_side << "\n";
337  log << "point side: " << point.side << "\n";
338  if (point.fraction > 0 && point.fraction < 1) {
339  if (edge.cost >= 0) {
340  last_cost = deltaFraction * edge.cost;
341  pgr_edge_t new_edge = {
342  edge.id,
343  prev_target,
344  point.vertex_id,
345  last_cost,
346  -1};
347  new_edges.push_back(new_edge);
348  log << "new_edge("
349  << "id, source, target, cost, reverse_cost) = ("
350  << new_edge.id << "\t"
351  << new_edge.source << "\t"
352  << new_edge.target << "\t"
353  << new_edge.cost << "\t"
354  << new_edge.reverse_cost << ")\n";
355  }
356  if (edge.reverse_cost >= 0) {
357  last_rcost = deltarFraction * edge.reverse_cost;
358  pgr_edge_t new_edge = {
359  edge.id,
360  prev_target,
361  point.vertex_id,
362  -1,
363  last_rcost};
364  new_edges.push_back(new_edge);
365  log << "new_edge("
366  << "id, source, target, cost, reverse_cost) = ("
367  << new_edge.id << "\t"
368  << new_edge.source << "\t"
369  << new_edge.target << "\t"
370  << new_edge.cost << "\t"
371  << new_edge.reverse_cost << ")\n";
372  }
373  }
374  prev_target = point.vertex_id;
375  prev_fraction = point.fraction;
376  agg_cost += last_cost;
377 
378  prev_rtarget = point.vertex_id;
379  prev_rfraction = point.fraction;
380  agg_rcost += last_rcost;
381  continue;
382  }
383 
384  pgassert(edge.cost > 0 && edge.reverse_cost > 0);
385  pgassert(point.side != 'b');
386 
387  if (driving_side == point.side) {
388  log << "two way and driving side == the side of the point\n";
389  log << "Breaking (source, target) when its not the extreme\n";
390  if (point.fraction > 0 && point.fraction < 1) {
391  last_cost = deltaFraction * edge.cost;
392  pgr_edge_t new_edge = {
393  edge.id, prev_target, point.vertex_id, last_cost, -1};
394  new_edges.push_back(new_edge);
395  log << "new_edge("
396  << "id, source, target, cost, reverse_cost) = ("
397  << new_edge.id << "\t"
398  << new_edge.source << "\t"
399  << new_edge.target << "\t"
400  << new_edge.cost << "\t"
401  << new_edge.reverse_cost << ")\n";
402  }
403  prev_target = point.vertex_id;
404  prev_fraction = point.fraction;
405  agg_cost += last_cost;
406  continue;
407  }
408 
409  log << "\ntwo way and driving side != the side of the point";
410  if (point.fraction > 0 && point.fraction < 1) {
411  last_rcost = deltarFraction * edge.reverse_cost;
412  pgr_edge_t new_edge = {
413  edge.id,
414  prev_rtarget,
415  point.vertex_id,
416  -1,
417  last_rcost};
418  new_edges.push_back(new_edge);
419  log << "\nnew_edge(id, source, target, cost, reverse_cost) = ("
420  << new_edge.id << "\t"
421  << new_edge.source << "\t"
422  << new_edge.target << "\t"
423  << new_edge.cost << "\t"
424  << new_edge.reverse_cost << ")\n";
425  }
426  prev_rtarget = point.vertex_id;
427  prev_rfraction = point.fraction;
428  agg_rcost += last_rcost;
429  }
430 
431  { // the last segments
432  pgr_edge_t new_edge = {
433  edge.id,
434  prev_target,
435  edge.target,
436  (edge.cost - agg_cost),
437  -1};
438  new_edges.push_back(new_edge);
439  log << "last edge: (id, source, target, cost, reverse_cost) = ("
440  << new_edge.id << "\t"
441  << new_edge.source << "\t"
442  << new_edge.target << "\t"
443  << new_edge.cost << "\t"
444  << new_edge.reverse_cost << ")\n";
445 
446  new_edge = {edge.id , prev_rtarget, edge.target,
447  -1, (edge.reverse_cost - agg_rcost)};
448  new_edges.push_back(new_edge);
449  log << "last edge: (id, source, target, cost, reverse_cost) = ("
450  << new_edge.id << "\t"
451  << new_edge.source << "\t"
452  << new_edge.target << "\t"
453  << new_edge.cost << "\t"
454  << new_edge.reverse_cost << ")\n";
455  }
456  }
457 
458  points = new_points;
459  for (const auto &point : points) {
460  log << "point: "
461  << point.pid << "\t"
462  << point.edge_id << "\t"
463  << point.fraction << "\t"
464  << point.side << "\t"
465  << point.vertex_id << "\n";
466  }
467  return true;
468 }
double reverse_cost
Definition: pgr_types.h:146
int64_t source
Definition: pgr_types.h:143
void eliminate_details(Path &path, const std::vector< pgr_edge_t > &point_edges)
int64_t target
Definition: pgr_types.h:144
double cost
double fraction
Definition: pgr_types.h:184
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)
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
int64_t id
Definition: pgr_types.h:142
int64_t edge_id
Definition: pgr_types.h:182
double cost
Definition: pgr_types.h:145
double reverse_cost
static void PGR_LOG_POINTS(std::ostringstream &log, const std::vector< Point_on_edge_t > &points, const std::string &title)
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)
void eliminate_details_dd(Path &path)
int64_t start_id() const
bool empty() const
path_element_t * path
Definition: BDATester.cpp:49