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