/[zanavi_public1]/navit/navit/route.c
ZANavi

Contents of /navit/navit/route.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Mon Feb 4 17:41:59 2013 UTC (11 years, 1 month ago) by zoff99
File MIME type: text/plain
File size: 121729 byte(s)
new map version, lots of fixes and experimental new features
1 /**
2 * ZANavi, Zoff Android Navigation system.
3 * Copyright (C) 2011-2012 Zoff <zoff@zoff.cc>
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * version 2 as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 */
19
20 /**
21 * Navit, a modular navigation system.
22 * Copyright (C) 2005-2008 Navit Team
23 *
24 * This program is free software; you can redistribute it and/or
25 * modify it under the terms of the GNU General Public License
26 * version 2 as published by the Free Software Foundation.
27 *
28 * This program is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 * GNU General Public License for more details.
32 *
33 * You should have received a copy of the GNU General Public License
34 * along with this program; if not, write to the
35 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
36 * Boston, MA 02110-1301, USA.
37 */
38
39 /** @file
40 * @brief Contains code related to finding a route from a position to a destination
41 *
42 * Routing uses segments, points and items. Items are items from the map: Streets, highways, etc.
43 * Segments represent such items, or parts of it. Generally, a segment is a driveable path. An item
44 * can be represented by more than one segment - in that case it is "segmented". Each segment has an
45 * "offset" associated, that indicates at which position in a segmented item this segment is - a
46 * segment representing a not-segmented item always has the offset 1.
47 * A point is located at the end of segments, often connecting several segments.
48 *
49 * The code in this file will make navit find a route between a position and a destination.
50 * It accomplishes this by first building a "route graph". This graph contains segments and
51 * points.
52 *
53 * After building this graph in route_graph_build(), the function route_graph_flood() assigns every
54 * point and segment a "value" which represents the "costs" of traveling from this point to the
55 * destination. This is done by Dijkstra's algorithm.
56 *
57 * When the graph is built a "route path" is created, which is a path in this graph from a given
58 * position to the destination determined at time of building the graph.
59 */
60
61 #include <stdio.h>
62 #include <stdlib.h>
63 #include <string.h>
64 #if 0
65 #include <math.h>
66 #include <assert.h>
67 #include <unistd.h>
68 #include <sys/time.h>
69 #endif
70 #include "glib_slice.h"
71 #include "config.h"
72 #include "point.h"
73 #include "graphics.h"
74 #include "profile.h"
75 #include "coord.h"
76 #include "projection.h"
77 #include "item.h"
78 #include "map.h"
79 #include "mapset.h"
80 #include "route.h"
81 #include "track.h"
82 #include "transform.h"
83 #include "plugin.h"
84 #include "fib.h"
85 #include "event.h"
86 #include "callback.h"
87 #include "vehicle.h"
88 #include "vehicleprofile.h"
89 #include "roadprofile.h"
90 #include "debug.h"
91
92 #include "navit.h"
93
94 struct map_priv
95 {
96 struct route *route;
97 };
98
99 int debug_route = 0;
100
101 /**
102 * @brief A point in the route graph
103 *
104 * This represents a point in the route graph. A point usually connects two or more segments,
105 * but there are also points which don't do that (e.g. at the end of a dead-end).
106 */
107 struct route_graph_point
108 {
109 struct route_graph_point *hash_next; /**< Pointer to a chained hashlist of all route_graph_points with this hash */
110 struct route_graph_segment *start; /**< Pointer to a list of segments of which this point is the start. The links
111 * of this linked-list are in route_graph_segment->start_next.*/
112 struct route_graph_segment *end; /**< Pointer to a list of segments of which this pointer is the end. The links
113 * of this linked-list are in route_graph_segment->end_next. */
114 struct route_graph_segment *seg; /**< Pointer to the segment one should use to reach the destination at
115 * least costs */
116 struct fibheap_el *el; /**< When this point is put on a Fibonacci heap, this is a pointer
117 * to this point's heap-element */
118 int value; /**< The cost at which one can reach the destination from this point on */
119 struct coord c; /**< Coordinates of this point */
120 int flags; /**< Flags for this point (eg traffic distortion) */
121 };
122
123 #define RP_TRAFFIC_DISTORTION 1
124 #define RP_TURN_RESTRICTION 2
125 #define RP_TURN_RESTRICTION_RESOLVED 4
126 #define RP_TRAFFIC_LIGHT 8
127 #define RP_TRAFFIC_LIGHT_RESOLVED 16
128
129 /**
130 * @brief A segment in the route graph or path
131 *
132 * This is a segment in the route graph or path. A segment represents a driveable way.
133 */
134
135 struct route_segment_data
136 {
137 struct item item; /**< The item (e.g. street) that this segment represents. */
138 int flags;
139 int len; /**< Length of this segment */
140 /*NOTE: After a segment, various fields may follow, depending on what flags are set. Order of fields:
141 1.) maxspeed Maximum allowed speed on this segment. Present if AF_SPEED_LIMIT is set.
142 2.) offset If the item is segmented (i.e. represented by more than one segment), this
143 indicates the position of this segment in the item. Present if AF_SEGMENTED is set.
144 */
145 };
146
147 struct size_weight_limit
148 {
149 int width;
150 int length;
151 int height;
152 int weight;
153 int axle_weight;
154 };
155
156 #define RSD_OFFSET(x) *((int *)route_segment_data_field_pos((x), attr_offset))
157 #define RSD_MAXSPEED(x) *((int *)route_segment_data_field_pos((x), attr_maxspeed))
158 #define RSD_SIZE_WEIGHT(x) *((struct size_weight_limit *)route_segment_data_field_pos((x), attr_vehicle_width))
159 #define RSD_DANGEROUS_GOODS(x) *((int *)route_segment_data_field_pos((x), attr_vehicle_dangerous_goods))
160
161 struct route_graph_segment_data
162 {
163 struct item *item;
164 int offset;
165 int flags;
166 int len;
167 int maxspeed;
168 struct size_weight_limit size_weight;
169 int dangerous_goods;
170 };
171
172 /**
173 * @brief A segment in the route graph
174 *
175 * This is a segment in the route graph. A segment represents a driveable way.
176 */
177 struct route_graph_segment
178 {
179 struct route_graph_segment *next; /**< Linked-list pointer to a list of all route_graph_segments */
180 struct route_graph_segment *start_next; /**< Pointer to the next element in the list of segments that start at the
181 * same point. Start of this list is in route_graph_point->start. */
182 struct route_graph_segment *end_next; /**< Pointer to the next element in the list of segments that end at the
183 * same point. Start of this list is in route_graph_point->end. */
184 struct route_graph_point *start; /**< Pointer to the point this segment starts at. */
185 struct route_graph_point *end; /**< Pointer to the point this segment ends at. */
186 struct route_segment_data data; /**< The segment data */
187 };
188
189 /**
190 * @brief A traffic distortion
191 *
192 * This is distortion in the traffic where you can't drive as fast as usual or have to wait for some time
193 */
194 struct route_traffic_distortion
195 {
196 int maxspeed; /**< Maximum speed possible in km/h */
197 int delay; /**< Delay in tenths of seconds */
198 };
199
200 /**
201 * @brief A segment in the route path
202 *
203 * This is a segment in the route path.
204 */
205 struct route_path_segment
206 {
207 struct route_path_segment *next; /**< Pointer to the next segment in the path */
208 struct route_segment_data *data; /**< The segment data */
209 int direction; /**< Order in which the coordinates are ordered. >0 means "First
210 * coordinate of the segment is the first coordinate of the item", <=0
211 * means reverse. */
212 unsigned ncoords; /**< How many coordinates does this segment have? */
213 struct coord c[0]; /**< Pointer to the ncoords coordinates of this segment */
214 /* WARNING: There will be coordinates following here, so do not create new fields after c! */
215 };
216
217 /**
218 * @brief A complete route path
219 *
220 * This structure describes a whole routing path
221 */
222 struct route_path
223 {
224 int in_use; /**< The path is in use and can not be updated */
225 int update_required; /**< The path needs to be updated after it is no longer in use */
226 int updated; /**< The path has only been updated */
227 int path_time; /**< Time to pass the path */
228 int path_len; /**< Length of the path */
229 struct route_path_segment *path; /**< The first segment in the path, i.e. the segment one should
230 * drive in next */
231 struct route_path_segment *path_last; /**< The last segment in the path */
232 /* XXX: path_hash is not necessery now */
233 struct item_hash *path_hash; /**< A hashtable of all the items represented by this route's segements */
234 struct route_path *next; /**< Next route path in case of intermediate destinations */
235 };
236
237 /**
238 * @brief A complete route
239 *
240 * This struct holds all information about a route.
241 */
242
243 /**
244 * @brief A complete route graph
245 *
246 * This structure describes a whole routing graph
247 */
248 struct route_graph
249 {
250 int busy; /**< The graph is being built */
251 struct map_selection *sel; /**< The rectangle selection for the graph */
252 struct mapset_handle *h; /**< Handle to the mapset */
253 struct map *m; /**< Pointer to the currently active map */
254 struct map_rect *mr; /**< Pointer to the currently active map rectangle */
255 struct vehicleprofile *vehicleprofile; /**< The vehicle profile */
256 struct callback *idle_cb; /**< Idle callback to process the graph */
257 struct callback *done_cb; /**< Callback when graph is done */
258 struct event_idle *idle_ev; /**< The pointer to the idle event */
259 struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */
260 // *ORIG* #define HASH_SIZE 8192
261 // #define HASH_SIZE 65536
262 #define HASH_SIZE 16384
263 struct route_graph_point *hash[HASH_SIZE]; /**< A hashtable containing all route_graph_points in this graph */
264 };
265
266 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
267
268 /**
269 * @brief Iterator to iterate through all route graph segments in a route graph point
270 *
271 * This structure can be used to iterate through all route graph segments connected to a
272 * route graph point. Use this with the rp_iterator_* functions.
273 */
274 struct route_graph_point_iterator
275 {
276 struct route_graph_point *p; /**< The route graph point whose segments should be iterated */
277 int end; /**< Indicates if we have finished iterating through the "start" segments */
278 struct route_graph_segment *next; /**< The next segment to be returned */
279 };
280
281 struct attr_iter
282 {
283 union
284 {
285 GList *list;
286 } u;
287 };
288
289 static struct route_info * route_find_nearest_street(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *c);
290 static struct route_info * route_find_nearest_street_harder(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc, int max_dist_wanted);
291 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
292 static void route_graph_update(struct route *this, struct callback *cb, int async);
293 static void route_graph_build_done(struct route_graph *rg, int cancel);
294 static struct route_path *route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct vehicleprofile *profile);
295 static void route_process_street_graph(struct route_graph *this, struct item *item, struct vehicleprofile *profile);
296 //static void route_graph_destroy(struct route_graph *this);
297 void route_path_update(struct route *this, int cancel, int async);
298 static int route_time_seg(struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist);
299 static void route_graph_flood(struct route_graph *this, struct route_info *dst, struct vehicleprofile *profile, struct callback *cb);
300 static void route_graph_reset(struct route_graph *this);
301
302 /**
303 * @brief Returns the projection used for this route
304 *
305 * @param route The route to return the projection for
306 * @return The projection used for this route
307 */
308 static enum projection route_projection(struct route *route)
309 {
310 struct street_data *street;
311 struct route_info *dst = route_get_dst(route);
312 if (!route->pos && !dst)
313 {
314 return projection_none;
315 }
316 street = route->pos ? route->pos->street : dst->street;
317 if (!street || !street->item.map)
318 {
319 return projection_none;
320 }
321 return map_projection(street->item.map);
322 }
323
324 /**
325 * @brief Creates a new graph point iterator
326 *
327 * This function creates a new route graph point iterator, that can be used to
328 * iterate through all segments connected to the point.
329 *
330 * @param p The route graph point to create the iterator from
331 * @return A new iterator.
332 */
333 static struct route_graph_point_iterator rp_iterator_new(struct route_graph_point *p)
334 {
335 //// dbg(0, "enter\n");
336
337 struct route_graph_point_iterator it;
338
339 it.p = p;
340 if (p->start)
341 {
342 it.next = p->start;
343 it.end = 0;
344 }
345 else
346 {
347 it.next = p->end;
348 it.end = 1;
349 }
350
351 return it;
352 }
353
354 /**
355 * @brief Gets the next segment connected to a route graph point from an iterator
356 *
357 * @param it The route graph point iterator to get the segment from
358 * @return The next segment or NULL if there are no more segments
359 */
360 static struct route_graph_segment *rp_iterator_next(struct route_graph_point_iterator *it)
361 {
362 //// dbg(0, "enter\n");
363
364 struct route_graph_segment *ret;
365
366 ret = it->next;
367 if (!ret)
368 {
369 return NULL;
370 }
371
372 if (!it->end)
373 {
374 if (ret->start_next)
375 {
376 it->next = ret->start_next;
377 }
378 else
379 {
380 it->next = it->p->end;
381 it->end = 1;
382 }
383 }
384 else
385 {
386 it->next = ret->end_next;
387 }
388
389 return ret;
390 }
391
392 /**
393 * @brief Checks if the last segment returned from a route_graph_point_iterator comes from the end
394 *
395 * @param it The route graph point iterator to be checked
396 * @return 1 if the last segment returned comes from the end of the route graph point, 0 otherwise
397 */
398 static int rp_iterator_end(struct route_graph_point_iterator *it)
399 {
400 //// dbg(0, "enter\n");
401
402 if (it->end && (it->next != it->p->end))
403 {
404 return 1;
405 }
406 else
407 {
408 return 0;
409 }
410 }
411
412 /**
413 * @brief Destroys a route_path
414 *
415 * @param this The route_path to be destroyed
416 */
417 void route_path_destroy(struct route_path *this, int recurse)
418 {
419 // dbg(0, "enter\n");
420
421 struct route_path_segment *c, *n;
422 struct route_path *next;
423 while (this)
424 {
425 next = this->next;
426 if (this->path_hash)
427 {
428 item_hash_destroy(this->path_hash);
429 this->path_hash = NULL;
430 }
431 c = this->path;
432 while (c)
433 {
434 n = c->next;
435 g_free(c);
436 c = n;
437 }
438 this->in_use--;
439 if (!this->in_use)
440 g_free(this);
441 if (!recurse)
442 break;
443 this = next;
444 }
445 }
446
447 /**
448 * @brief Creates a completely new route structure
449 *
450 * @param attrs Not used
451 * @return The newly created route
452 */
453 struct route *
454 route_new(struct attr *parent, struct attr **attrs)
455 {
456 // dbg(0, "enter\n");
457
458 struct route *this=g_new0(struct route, 1);
459 struct attr dest_attr;
460
461 if (attr_generic_get_attr(attrs, NULL, attr_destination_distance, &dest_attr, NULL))
462 {
463 this->destination_distance = dest_attr.u.num;
464 }
465 else
466 {
467 this->destination_distance = 50; // Default value
468 }
469 this->cbl2 = callback_list_new();
470
471 return this;
472 }
473
474 /**
475 * @brief Checks if a segment is part of a roundabout
476 *
477 * This function checks if a segment is part of a roundabout.
478 *
479 * @param seg The segment to be checked
480 * @param level How deep to scan the route graph
481 * @param direction Set this to 1 if we're entering the segment through its end, to 0 otherwise
482 * @param origin Used internally, set to NULL
483 * @return 1 If a roundabout was detected, 0 otherwise
484 */
485 static int route_check_roundabout(struct route_graph_segment *seg, int level, int direction, struct route_graph_segment *origin)
486 {
487 //// dbg(0, "enter\n");
488
489 struct route_graph_point_iterator it, it2;
490 struct route_graph_segment *cur;
491 int count = 0;
492
493 if (!level)
494 {
495 return 0;
496 }
497 if (!direction && !(seg->data.flags & AF_ONEWAY))
498 {
499 return 0;
500 }
501 if (direction && !(seg->data.flags & AF_ONEWAYREV))
502 {
503 return 0;
504 }
505 if (seg->data.flags & AF_ROUNDABOUT_VALID)
506 return 0;
507
508 if (!origin)
509 {
510 origin = seg;
511 }
512
513 if (!direction)
514 {
515 it = rp_iterator_new(seg->end);
516 }
517 else
518 {
519 it = rp_iterator_new(seg->start);
520 }
521 it2 = it;
522
523 while ((cur = rp_iterator_next(&it2)))
524 count++;
525
526 if (count > 3)
527 return 0;
528 cur = rp_iterator_next(&it);
529 while (cur)
530 {
531 if (cur == seg)
532 {
533 cur = rp_iterator_next(&it);
534 continue;
535 }
536
537 if (cur->data.item.type != origin->data.item.type)
538 {
539 // This street is of another type, can't be part of the roundabout
540 cur = rp_iterator_next(&it);
541 continue;
542 }
543
544 if (cur == origin)
545 {
546 seg->data.flags |= AF_ROUNDABOUT;
547 return 1;
548 }
549
550 if (route_check_roundabout(cur, (level - 1), rp_iterator_end(&it), origin))
551 {
552 seg->data.flags |= AF_ROUNDABOUT;
553 return 1;
554 }
555
556 cur = rp_iterator_next(&it);
557 }
558
559 return 0;
560 }
561
562 /**
563 * @brief Sets the mapset of the route passwd
564 *
565 * @param this The route to set the mapset for
566 * @param ms The mapset to set for this route
567 */
568 void route_set_mapset(struct route *this, struct mapset *ms)
569 {
570 //// dbg(0, "enter\n");
571
572 this->ms = ms;
573 }
574
575 /**
576 * @brief Sets the vehicle profile of a route
577 *
578 * @param this The route to set the profile for
579 * @param prof The vehicle profile
580 */
581
582 void route_set_profile(struct route *this, struct vehicleprofile *prof)
583 {
584 // dbg(0, "enter\n");
585
586 if (this->vehicleprofile != prof)
587 {
588 this->vehicleprofile = prof;
589 route_path_update(this, 1, 1);
590 }
591 }
592
593 /**
594 * @brief Returns the mapset of the route passed
595 *
596 * @param this The route to get the mapset of
597 * @return The mapset of the route passed
598 */
599 struct mapset *
600 route_get_mapset(struct route *this)
601 {
602 //// dbg(0, "enter\n");
603
604 return this->ms;
605 }
606
607 /**
608 * @brief Returns the current position within the route passed
609 *
610 * @param this The route to get the position for
611 * @return The position within the route passed
612 */
613 struct route_info *
614 route_get_pos(struct route *this)
615 {
616 //// dbg(0, "enter\n");
617
618 return this->pos;
619 }
620
621 /**
622 * @brief Returns the destination of the route passed
623 *
624 * @param this The route to get the destination for
625 * @return The destination of the route passed
626 */
627 struct route_info *
628 route_get_dst(struct route *this)
629 {
630 //// dbg(0, "enter\n");
631
632 struct route_info *dst = NULL;
633
634 if (this->destinations)
635 dst = g_list_last(this->destinations)->data;
636 return dst;
637 }
638
639 /**
640 * @brief Checks if the path is calculated for the route passed
641 *
642 * @param this The route to check
643 * @return True if the path is calculated, false if not
644 */
645 int route_get_path_set(struct route *this)
646 {
647 //// dbg(0, "enter\n");
648
649 return this->path2 != NULL;
650 }
651
652 /**
653 * @brief Checks if the route passed contains a certain item within the route path
654 *
655 * This function checks if a certain items exists in the path that navit will guide
656 * the user to his destination. It does *not* check if this item exists in the route
657 * graph!
658 *
659 * @param this The route to check for this item
660 * @param item The item to search for
661 * @return True if the item was found, false if the item was not found or the route was not calculated
662 */
663 int route_contains(struct route *this, struct item *item)
664 {
665 //// dbg(0, "enter\n");
666
667 if (!this->path2 || !this->path2->path_hash)
668 return 0;
669 if (item_hash_lookup(this->path2->path_hash, item))
670 return 1;
671 if (!this->pos || !this->pos->street)
672 return 0;
673 return item_is_equal(this->pos->street->item, *item);
674
675 }
676
677 static struct route_info *
678 route_next_destination(struct route *this)
679 {
680 // dbg(0, "enter\n");
681
682 if (!this->destinations)
683 return NULL;
684 return this->destinations->data;
685 }
686
687 /**
688 * @brief Checks if a route has reached its destination
689 *
690 * @param this The route to be checked
691 * @return True if the destination is "reached", false otherwise.
692 */
693 int route_destination_reached(struct route *this)
694 {
695 // dbg(0, "enter\n");
696
697 struct street_data *sd = NULL;
698 enum projection pro;
699 struct route_info *dst = route_next_destination(this);
700
701 if (!this->pos)
702 return 0;
703 if (!dst)
704 return 0;
705
706 sd = this->pos->street;
707
708 if (!this->path2)
709 {
710 return 0;
711 }
712
713 // this fixed a crash for large offroad start segments
714 if (!this->pos->street)
715 {
716 return 0;
717 }
718
719 if (!item_is_equal(this->pos->street->item, dst->street->item))
720 {
721 return 0;
722 }
723
724 if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= dst->lenneg))
725 { // We would have to drive against the one-way road
726 return 0;
727 }
728
729 if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= dst->lenpos))
730 {
731 return 0;
732 }
733
734 pro = route_projection(this);
735 if (pro == projection_none)
736 {
737 return 0;
738 }
739
740 if (transform_distance(pro, &this->pos->c, &dst->lp) > this->destination_distance)
741 {
742 return 0;
743 }
744
745 if (g_list_next(this->destinations))
746 {
747 return 1;
748 }
749 else
750 {
751 return 2;
752 }
753 }
754
755 static struct route_info *
756 route_previous_destination(struct route *this)
757 {
758 // dbg(0, "enter\n");
759
760 GList *l = g_list_find(this->destinations, this->current_dst);
761 if (!l)
762 return this->pos;
763 l = g_list_previous(l);
764 if (!l)
765 return this->pos;
766 return l->data;
767 }
768
769 static void route_path_update_done(struct route *this, int new_graph)
770 {
771 //dbg(0, "enter\n");
772
773 struct route_path *oldpath = this->path2;
774 struct attr route_status;
775 struct route_info *prev_dst;
776 route_status.type = attr_route_status;
777
778 if (this->path2 && (this->path2->in_use > 1))
779 {
780 this->path2->update_required = 1 + new_graph;
781 //dbg(0,"return 001\n");
782 return;
783 }
784
785 route_status.u.num = route_status_building_path;
786 route_set_attr(this, &route_status);
787 prev_dst = route_previous_destination(this);
788
789 if (this->link_path)
790 {
791 this->path2 = route_path_new(this->graph, NULL, prev_dst, this->current_dst, this->vehicleprofile);
792 if (this->path2)
793 this->path2->next = oldpath;
794 }
795 else
796 {
797 this->path2 = route_path_new(this->graph, oldpath, prev_dst, this->current_dst, this->vehicleprofile);
798 if (oldpath && this->path2)
799 {
800 this->path2->next = oldpath->next;
801 route_path_destroy(oldpath, 0);
802 }
803 }
804
805 if (this->path2)
806 {
807 struct route_path_segment *seg = this->path2->path;
808 int path_time = 0, path_len = 0;
809 while (seg)
810 {
811 /* FIXME */
812 int seg_time = route_time_seg(this->vehicleprofile, seg->data, NULL);
813
814 if (seg_time == INT_MAX)
815 {
816 // dbg(1, "error\n");
817 }
818 else
819 {
820 path_time += seg_time;
821 }
822 path_len += seg->data->len;
823 seg = seg->next;
824 }
825
826 this->path2->path_time = path_time;
827 this->path2->path_len = path_len;
828
829 if (prev_dst != this->pos)
830 {
831 this->link_path = 1;
832 this->current_dst = prev_dst;
833 route_graph_reset(this->graph);
834 route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, this->route_graph_flood_done_cb);
835 //dbg(0,"return 002\n");
836 return;
837 }
838
839 if (!new_graph && this->path2->updated)
840 {
841 route_status.u.num = route_status_path_done_incremental;
842 }
843 else
844 {
845 route_status.u.num = route_status_path_done_new;
846 }
847 }
848 else
849 {
850 // dbg(0, "try harder\n");
851 // Try to rebuild the graph with smaller roads
852 if (this->try_harder == 0)
853 {
854 this->try_harder = 1;
855 route_graph_destroy(this->graph);
856 this->graph = NULL;
857 route_path_update(this, 1, 1);
858 }
859 else
860 {
861 route_status.u.num = route_status_not_found;
862 }
863 }
864
865 this->link_path = 0;
866 route_set_attr(this, &route_status);
867
868 //dbg(0,"leave\n");
869 }
870
871 /**
872 * @brief Updates the route graph and the route path if something changed with the route
873 *
874 * This will update the route graph and the route path of the route if some of the
875 * route's settings (destination, position) have changed.
876 *
877 * @attention For this to work the route graph has to be destroyed if the route's
878 * @attention destination is changed somewhere!
879 *
880 * @param this The route to update
881 */
882 void route_path_update(struct route *this, int cancel, int async)
883 {
884 //dbg(0, "enter\n");
885
886 //dbg(1, "enter %d\n", cancel);
887 if (!this->pos || !this->destinations)
888 {
889 //dbg(0, "destroy\n");
890 route_path_destroy(this->path2, 1);
891 this->path2 = NULL;
892 return;
893 }
894
895 if (cancel)
896 {
897 route_graph_destroy(this->graph);
898 this->graph = NULL;
899 }
900
901 /* the graph is destroyed when setting the destination */
902 if (this->graph)
903 {
904 if (this->graph->busy)
905 {
906 //dbg(0, "busy building graph\n");
907 return;
908 }
909 // we can try to update
910 //dbg(0, "try update\n");
911 route_path_update_done(this, 0);
912 }
913 else
914 {
915 route_path_destroy(this->path2, 1);
916 this->path2 = NULL;
917 }
918
919 if (!this->graph || !this->path2)
920 {
921 //dbg(0, "rebuild graph\n");
922 if (!this->route_graph_flood_done_cb)
923 {
924 this->route_graph_flood_done_cb = callback_new_2(callback_cast(route_path_update_done), this, (long) 1);
925 callback_add_names(this->route_graph_flood_done_cb, "route_path_update", "route_path_update_done");
926 }
927 //dbg(0, "route_graph_update\n");
928 route_graph_update(this, this->route_graph_flood_done_cb, async);
929 }
930
931 //dbg(0,"leave\n");
932 }
933
934 /**
935 * @brief This will calculate all the distances stored in a route_info
936 *
937 * @param ri The route_info to calculate the distances for
938 * @param pro The projection used for this route
939 */
940 static void route_info_distances(struct route_info *ri, enum projection pro)
941 {
942 //// dbg(0, "enter\n");
943
944 int npos = ri->pos + 1;
945 struct street_data *sd = ri->street;
946
947 /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
948
949 ri->lenextra = transform_distance(pro, &ri->lp, &ri->c);
950
951 ri->lenneg = transform_polyline_length(pro, sd->c, npos) + transform_distance(pro, &sd->c[ri->pos], &ri->lp);
952
953 ri->lenpos = transform_polyline_length(pro, sd->c + npos, sd->count - npos) + transform_distance(pro, &sd->c[npos], &ri->lp);
954
955 if (ri->lenneg || ri->lenpos)
956 {
957 ri->percent = (ri->lenneg * 100) / (ri->lenneg + ri->lenpos);
958 }
959 else
960 {
961 ri->percent = 50;
962 }
963
964 //dbg(0,"len extra=%d\n", ri->lenextra);
965 }
966
967 /**
968 * @brief This sets the current position of the route passed
969 *
970 * This will set the current position of the route passed to the street that is nearest to the
971 * passed coordinates. It also automatically updates the route.
972 *
973 * @param this The route to set the position of
974 * @param pos Coordinates to set as position
975 */
976 void route_set_position(struct route *this, struct pcoord *pos)
977 {
978 //dbg(0, "enter\n");
979
980 if (this->pos)
981 {
982 route_info_free(this->pos);
983 }
984
985 this->pos = NULL;
986 this->pos = route_find_nearest_street(this->vehicleprofile, this->ms, pos);
987
988 //dbg(0,"this->pos=%p\n", this->pos);
989
990 // try harder
991 if (this->pos == NULL)
992 {
993 this->pos = route_find_nearest_street_harder(this->vehicleprofile, this->ms, pos, 5000);
994 //dbg(0,"this->pos=%p\n", this->pos);
995 }
996
997 // If there is no nearest street, bail out.
998 if (!this->pos)
999 {
1000 //dbg(0,"this->pos=%p\n", this->pos);
1001 //dbg(0,"return 001\n");
1002 return;
1003 }
1004
1005 //dbg(0, "1: x y: %i %i\n", pos->x, pos->y);
1006 //dbg(0, "2: x y: %i %i\n", this->pos->c.x, this->pos->c.y);
1007 //dbg(0, "3: x y: %i %i\n", this->pos->lp.x, this->pos->lp.y);
1008
1009
1010 this->pos->street_direction = 0;
1011 //dbg(1, "this->pos=%p\n", this->pos);
1012 route_info_distances(this->pos, pos->pro);
1013
1014 //dbg(0,"sp 002\n");
1015
1016 route_path_update(this, 0, 1);
1017
1018 //dbg(0,"leave\n");
1019 }
1020
1021 /**
1022 * @brief Sets a route's current position based on coordinates from tracking
1023 *
1024 * @param this The route to set the current position of
1025 * @param tracking The tracking to get the coordinates from
1026 */
1027 void route_set_position_from_tracking(struct route *this, struct tracking *tracking, enum projection pro)
1028 {
1029 //dbg(0, "enter\n");
1030
1031 struct coord *c;
1032 struct route_info *ret;
1033 struct street_data *sd;
1034
1035 //dbg(2, "enter\n");
1036 c = tracking_get_pos(tracking);
1037 ret=g_new0(struct route_info, 1);
1038
1039 if (!ret)
1040 {
1041 dbg(0, "Out of memory\n");
1042 return;
1043 }
1044
1045 if (this->pos)
1046 {
1047 route_info_free(this->pos);
1048 }
1049
1050 this->pos = NULL;
1051 ret->c = *c;
1052 ret->lp = *c;
1053 ret->pos = tracking_get_segment_pos(tracking);
1054 ret->street_direction = tracking_get_street_direction(tracking);
1055 sd = tracking_get_street_data(tracking);
1056 if (sd)
1057 {
1058 ret->street = street_data_dup(sd);
1059 route_info_distances(ret, pro);
1060 }
1061 //dbg(
1062 // 3,
1063 // "position 0x%x,0x%x item 0x%x,0x%x direction %d pos %d lenpos %d lenneg %d\n",
1064 // c->x, c->y, sd ? sd->item.id_hi : 0, sd ? sd->item.id_lo : 0,
1065 // ret->street_direction, ret->pos, ret->lenpos, ret->lenneg);
1066 //dbg(3, "c->x=0x%x, c->y=0x%x pos=%d item=(0x%x,0x%x)\n", c->x, c->y,
1067 // ret->pos, ret->street ? ret->street->item.id_hi : 0,
1068 // ret->street ? ret->street->item.id_lo : 0);
1069 //dbg(3, "street 0=(0x%x,0x%x) %d=(0x%x,0x%x)\n",
1070 // ret->street ? ret->street->c[0].x : 0,
1071 // ret->street ? ret->street->c[0].y : 0,
1072 // ret->street ? ret->street->count - 1 : 0,
1073 // ret->street ? ret->street->c[ret->street->count - 1].x : 0,
1074 // ret->street ? ret->street->c[ret->street->count - 1].y : 0);
1075 this->pos = ret;
1076 if (this->destinations)
1077 {
1078 route_path_update(this, 0, 1);
1079 }
1080 //dbg(2, "ret\n");
1081 }
1082
1083 /* Used for debuging of route_rect, what routing sees */
1084 struct map_selection *route_selection;
1085
1086 /**
1087 * @brief Returns a single map selection
1088 */
1089 struct map_selection *
1090 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
1091 {
1092 //// dbg(0, "enter\n");
1093
1094 int dx, dy, sx = 1, sy = 1, d, m;
1095 struct map_selection *sel=g_new(struct map_selection, 1);
1096
1097 if (!sel)
1098 {
1099 dbg(0, "Out of memory\n");
1100 // printf("%s:Out of memory\n", __FUNCTION__);
1101 return sel;
1102 }
1103
1104 sel->order = order;
1105 sel->range.min = route_item_first;
1106 sel->range.max = route_item_last;
1107 // dbg(1, "%p %p\n", c1, c2);
1108 dx = c1->x - c2->x;
1109 dy = c1->y - c2->y;
1110
1111 if (dx < 0)
1112 {
1113 sx = -1;
1114 sel->u.c_rect.lu.x = c1->x;
1115 sel->u.c_rect.rl.x = c2->x;
1116 }
1117 else
1118 {
1119 sel->u.c_rect.lu.x = c2->x;
1120 sel->u.c_rect.rl.x = c1->x;
1121 }
1122
1123 if (dy < 0)
1124 {
1125 sy = -1;
1126 sel->u.c_rect.lu.y = c2->y;
1127 sel->u.c_rect.rl.y = c1->y;
1128 }
1129 else
1130 {
1131 sel->u.c_rect.lu.y = c1->y;
1132 sel->u.c_rect.rl.y = c2->y;
1133 }
1134
1135 if (dx * sx > dy * sy)
1136 {
1137 d = dx * sx;
1138 }
1139 else
1140 {
1141 d = dy * sy;
1142 }
1143
1144 m = d * rel / 100 + abs;
1145
1146 //dbg(0,"m=%d d=%d rel=%d abs=%d\n",m,d,rel,abs);
1147
1148 sel->u.c_rect.lu.x -= m;
1149 sel->u.c_rect.rl.x += m;
1150 sel->u.c_rect.lu.y += m;
1151 sel->u.c_rect.rl.y -= m;
1152 sel->next = NULL;
1153 return sel;
1154 }
1155
1156 /**
1157 * @brief Returns a list of map selections useable to create a route graph
1158 *
1159 * Returns a list of map selections useable to get a map rect from which items can be
1160 * retrieved to build a route graph. The selections are a rectangle with
1161 * c1 and c2 as two corners.
1162 *
1163 * @param c1 Corner 1 of the rectangle
1164 * @param c2 Corder 2 of the rectangle
1165 */
1166 static struct map_selection *
1167 route_calc_selection(struct coord *c, int count, int try_harder)
1168 {
1169 // dbg(0, "enter\n");
1170
1171 struct map_selection *ret, *sel;
1172 int i;
1173 struct coord_rect r;
1174
1175 if (!count)
1176 {
1177 return NULL;
1178 }
1179
1180 r.lu = c[0];
1181 r.rl = c[0];
1182 for (i = 1; i < count; i++)
1183 {
1184 // extend the rectangle to include all waypoints -> make 1 big rectangle
1185 coord_rect_extend(&r, &c[i]);
1186 }
1187
1188 // the route selection rectangle will be extened further, to find all routes (by 25%)
1189 #ifdef HAVE_API_ANDROID
1190 if (global_show_route_rectangles)
1191 {
1192 send_route_rect_to_java(r.lu.x, r.lu.y, r.rl.x, r.rl.y, -99);
1193 }
1194 #endif
1195
1196 if (routing_mode == 0)
1197 {
1198 // normal highway routing
1199 // sel=route_rect(4, &r.lu, &r.rl, 25, 0);
1200 sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0);
1201
1202 // the route selection rectangle will be extened further, to find all routes (by 25%)
1203 #ifdef HAVE_API_ANDROID
1204 if (global_show_route_rectangles)
1205 {
1206 send_route_rect_to_java(sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y, try_harder ? 6 : 4);
1207 }
1208 #endif
1209 }
1210 else if (routing_mode == 1)
1211 {
1212 // normal roads routing (should take longer and use more roads)
1213 // sel=route_rect(6, &r.lu, &r.rl, 25, 0);
1214 sel = route_rect(try_harder ? 7 : 6, &r.lu, &r.rl, 25, 0);
1215
1216 #ifdef HAVE_API_ANDROID
1217 if (global_show_route_rectangles)
1218 {
1219 send_route_rect_to_java(sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y, try_harder ? 7 : 6);
1220 }
1221 #endif
1222 }
1223 else
1224 {
1225 // DEFAULT setting
1226 // normal highway routing
1227 // sel=route_rect(4, &r.lu, &r.rl, 25, 0);
1228 sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0);
1229
1230 // the route selection rectangle will be extened further, to find all routes (by 25%)
1231 #ifdef HAVE_API_ANDROID
1232 if (global_show_route_rectangles)
1233 {
1234 send_route_rect_to_java(sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y, try_harder ? 6 : 4);
1235 }
1236 #endif
1237
1238 }
1239
1240 ret = sel;
1241 for (i = 0; i < count; i++)
1242 {
1243 // make 2 rectangles around every waypoint
1244 // 1 rect small but with high detail (every small street)
1245 // 1 rect a bit bigger but with lower detail
1246
1247 sel->next = route_rect(8, &c[i], &c[i], 0, 40000);
1248 sel = sel->next;
1249 #ifdef HAVE_API_ANDROID
1250 if (global_show_route_rectangles)
1251 {
1252 send_route_rect_to_java(sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y, 8);
1253 }
1254 #endif
1255
1256 sel->next = route_rect(18, &c[i], &c[i], 0, 10000);
1257 sel = sel->next;
1258 #ifdef HAVE_API_ANDROID
1259 if (global_show_route_rectangles)
1260 {
1261 send_route_rect_to_java(sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y, 18);
1262 }
1263 #endif
1264 }
1265 /* route_selection=ret; */
1266 return ret;
1267 }
1268
1269 /**
1270 * @brief Destroys a list of map selections
1271 *
1272 * @param sel Start of the list to be destroyed
1273 */
1274 static void route_free_selection(struct map_selection *sel)
1275 {
1276 //// dbg(0, "enter\n");
1277
1278 struct map_selection *next;
1279 while (sel)
1280 {
1281 next = sel->next;
1282 g_free(sel);
1283 sel = next;
1284 }
1285 }
1286
1287 static void route_clear_destinations(struct route *this_)
1288 {
1289 // dbg(0, "enter\n");
1290
1291 g_list_foreach(this_->destinations, (GFunc) route_info_free, NULL);
1292 g_list_free(this_->destinations);
1293 this_->destinations = NULL;
1294 }
1295
1296 /**
1297 * @brief Sets the destination of a route
1298 *
1299 * This sets the destination of a route to the street nearest to the coordinates passed
1300 * and updates the route.
1301 *
1302 * @param this The route to set the destination for
1303 * @param dst Coordinates to set as destination
1304 * @param count: Number of destinations (last one is final)
1305 * @param async: If set, do routing asynchronously
1306 */
1307
1308 void route_set_destinations(struct route *this, struct pcoord *dst, int count, int async)
1309 {
1310 // dbg(0, "enter\n");
1311
1312 struct attr route_status;
1313 struct route_info *dsti;
1314 int i;
1315 route_status.type = attr_route_status;
1316
1317 //profile(0,NULL);
1318 route_clear_destinations(this);
1319
1320 if (dst && count)
1321 {
1322 for (i = 0; i < count; i++)
1323 {
1324 dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[i]);
1325
1326 // try harder
1327 if (dsti == NULL)
1328 {
1329 dsti = route_find_nearest_street_harder(this->vehicleprofile, this->ms, &dst[i], 16000);
1330 }
1331
1332 if (dsti)
1333 {
1334
1335 //dbg(0, "1: x y: %i %i\n", dst[i].x, dst[i].y);
1336 //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y);
1337 //dbg(0, "3: x y: %i %i\n", dsti->lp.x, dsti->lp.y);
1338 route_info_distances(dsti, dst->pro);
1339 this->destinations = g_list_append(this->destinations, dsti);
1340 }
1341 }
1342 route_status.u.num = route_status_destination_set;
1343 }
1344 else
1345 {
1346 route_status.u.num = route_status_no_destination;
1347 }
1348
1349 callback_list_call_attr_1(this->cbl2, attr_destination, this);
1350 route_set_attr(this, &route_status);
1351 //profile(1,"find_nearest_street");
1352
1353 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
1354 route_graph_destroy(this->graph);
1355 this->graph = NULL;
1356 this->current_dst = route_get_dst(this);
1357 this->try_harder = 0;
1358 route_path_update(this, 1, async);
1359 //profile(0,"end");
1360 }
1361
1362 void route_add_destination(struct route *this, struct pcoord *dst, int async)
1363 {
1364 // dbg(0, "enter\n");
1365
1366 struct attr route_status;
1367 struct route_info *dsti;
1368 route_status.type = attr_route_status;
1369
1370 dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[0]);
1371
1372 // try harder
1373 if (dsti == NULL)
1374 {
1375 dsti = route_find_nearest_street_harder(this->vehicleprofile, this->ms, &dst[0], 16000);
1376 }
1377
1378 if (dsti)
1379 {
1380 //dbg(0, "1: x y: %i %i\n", dst[0].x, dst[0].y);
1381 //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y);
1382 //dbg(0, "3: x y: %i %i\n", dsti->lp.x, dsti->lp.y);
1383
1384 route_info_distances(dsti, dst->pro);
1385 this->destinations = g_list_append(this->destinations, dsti);
1386
1387 route_status.u.num = route_status_destination_set;
1388 }
1389
1390 callback_list_call_attr_1(this->cbl2, attr_destination, this);
1391 route_set_attr(this, &route_status);
1392
1393 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
1394 route_graph_destroy(this->graph);
1395 this->graph = NULL;
1396 this->current_dst = route_get_dst(this);
1397 this->try_harder = 0;
1398 route_path_update(this, 1, async);
1399 }
1400
1401 int route_get_destinations(struct route *this, struct pcoord *pc, int count)
1402 {
1403 // dbg(0, "enter\n");
1404
1405 int ret = 0;
1406 GList *l = this->destinations;
1407 while (l && ret < count)
1408 {
1409 struct route_info *dst = l->data;
1410 pc->x = dst->c.x;
1411 pc->y = dst->c.y;
1412 pc->pro = projection_mg; /* FIXME */
1413 pc++;
1414 ret++;
1415 l = g_list_next(l);
1416 }
1417 return ret;
1418 }
1419
1420 void route_set_destination(struct route *this, struct pcoord *dst, int async)
1421 {
1422 // dbg(0, "enter\n");
1423
1424 route_set_destinations(this, dst, dst ? 1 : 0, async);
1425 }
1426
1427 void route_remove_waypoint(struct route *this)
1428 {
1429 // dbg(0, "enter\n");
1430
1431 struct route_path *path = this->path2;
1432 this->destinations = g_list_remove(this->destinations, this->destinations->data);
1433 this->path2 = this->path2->next;
1434 route_path_destroy(path, 0);
1435
1436 if (!this->destinations)
1437 return;
1438
1439 route_graph_reset(this->graph);
1440 this->current_dst = this->destinations->data;
1441
1442 route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, this->route_graph_flood_done_cb);
1443
1444 }
1445
1446 /**
1447 * @brief Gets the route_graph_point with the specified coordinates
1448 *
1449 * @param this The route in which to search
1450 * @param c Coordinates to search for
1451 * @param last The last route graph point returned to iterate over multiple points with the same coordinates
1452 * @return The point at the specified coordinates or NULL if not found
1453 */
1454 static struct route_graph_point *
1455 route_graph_get_point_next(struct route_graph *this, struct coord *c, struct route_graph_point *last)
1456 {
1457 //// dbg(0, "enter\n");
1458
1459 struct route_graph_point *p;
1460 int seen = 0, hashval = HASHCOORD(c);
1461 p = this->hash[hashval];
1462 while (p)
1463 {
1464 if (p->c.x == c->x && p->c.y == c->y)
1465 {
1466 if (!last || seen)
1467 return p;
1468 if (p == last)
1469 seen = 1;
1470 }
1471 p = p->hash_next;
1472 }
1473 return NULL;
1474 }
1475
1476 static struct route_graph_point *
1477 route_graph_get_point(struct route_graph *this, struct coord *c)
1478 {
1479 //// dbg(0, "enter\n");
1480
1481 return route_graph_get_point_next(this, c, NULL);
1482 }
1483
1484 /**
1485 * @brief Gets the last route_graph_point with the specified coordinates
1486 *
1487 * @param this The route in which to search
1488 * @param c Coordinates to search for
1489 * @return The point at the specified coordinates or NULL if not found
1490 */
1491 static struct route_graph_point *
1492 route_graph_get_point_last(struct route_graph *this, struct coord *c)
1493 {
1494 //// dbg(0, "enter\n");
1495
1496 struct route_graph_point *p, *ret = NULL;
1497 int hashval = HASHCOORD(c);
1498 p = this->hash[hashval];
1499 while (p)
1500 {
1501 if (p->c.x == c->x && p->c.y == c->y)
1502 ret = p;
1503 p = p->hash_next;
1504 }
1505 return ret;
1506 }
1507
1508 /**
1509 * @brief Create a new point for the route graph with the specified coordinates
1510 *
1511 * @param this The route to insert the point into
1512 * @param f The coordinates at which the point should be created
1513 * @return The point created
1514 */
1515 static struct route_graph_point *
1516 route_graph_point_new(struct route_graph *this, struct coord *f)
1517 {
1518 //// dbg(0, "enter\n");
1519
1520 int hashval;
1521 struct route_graph_point *p;
1522
1523 hashval = HASHCOORD(f);
1524 //if (debug_route)
1525 // printf("p (0x%x,0x%x)\n", f->x, f->y);
1526
1527 p=g_slice_new0(struct route_graph_point);
1528 //global_route_memory_size = global_route_memory_size + sizeof(struct route_graph_point);
1529 //dbg(0,"(A)route mem=%lu\n", global_route_memory_size);
1530
1531 p->hash_next = this->hash[hashval];
1532 this->hash[hashval] = p;
1533 p->value = INT_MAX;
1534 p->c = *f;
1535
1536 return p;
1537 }
1538
1539 /**
1540 * @brief Inserts a point into the route graph at the specified coordinates
1541 *
1542 * This will insert a point into the route graph at the coordinates passed in f.
1543 * Note that the point is not yet linked to any segments.
1544 *
1545 * @param this The route to insert the point into
1546 * @param f The coordinates at which the point should be inserted
1547 * @return The point inserted or NULL on failure
1548 */
1549 static struct route_graph_point *
1550 route_graph_add_point(struct route_graph *this, struct coord *f)
1551 {
1552 //// dbg(0, "enter\n");
1553
1554 struct route_graph_point *p;
1555
1556 p = route_graph_get_point(this, f);
1557 if (!p)
1558 p = route_graph_point_new(this, f);
1559 return p;
1560 }
1561
1562 /**
1563 * @brief Frees all the memory used for points in the route graph passed
1564 *
1565 * @param this The route graph to delete all points from
1566 */
1567 static void route_graph_free_points(struct route_graph *this)
1568 {
1569 //// dbg(0, "enter\n");
1570
1571 struct route_graph_point *curr, *next;
1572 int i;
1573 for (i = 0; i < HASH_SIZE; i++)
1574 {
1575 curr = this->hash[i];
1576 while (curr)
1577 {
1578 next = curr->hash_next;
1579 g_slice_free(struct route_graph_point, curr);
1580 //global_route_memory_size = global_route_memory_size - sizeof(struct route_graph_point);
1581 //dbg(0,"(F)route mem=%lu\n", global_route_memory_size);
1582
1583 curr = next;
1584 }
1585 this->hash[i] = NULL;
1586 }
1587 }
1588
1589 /**
1590 * @brief Resets all nodes
1591 *
1592 * @param this The route graph to reset
1593 */
1594 static void route_graph_reset(struct route_graph *this)
1595 {
1596 // dbg(0, "enter\n");
1597
1598 struct route_graph_point *curr;
1599 int i;
1600 for (i = 0; i < HASH_SIZE; i++)
1601 {
1602 curr = this->hash[i];
1603 while (curr)
1604 {
1605 curr->value = INT_MAX;
1606 curr->seg = NULL;
1607 curr->el = NULL;
1608 curr = curr->hash_next;
1609 }
1610 }
1611 }
1612
1613 /**
1614 * @brief Returns the position of a certain field appended to a route graph segment
1615 *
1616 * This function returns a pointer to a field that is appended to a route graph
1617 * segment.
1618 *
1619 * @param seg The route graph segment the field is appended to
1620 * @param type Type of the field that should be returned
1621 * @return A pointer to a field of a certain type, or NULL if no such field is present
1622 */
1623 static void *
1624 route_segment_data_field_pos(struct route_segment_data *seg, enum attr_type type)
1625 {
1626 // // dbg(0, "enter\n");
1627
1628 unsigned char *ptr;
1629
1630 ptr = ((unsigned char*) seg) + sizeof(struct route_segment_data);
1631
1632 if (seg->flags & AF_SPEED_LIMIT)
1633 {
1634 if (type == attr_maxspeed)
1635 return (void*) ptr;
1636 ptr += sizeof(int);
1637 }
1638 if (seg->flags & AF_SEGMENTED)
1639 {
1640 if (type == attr_offset)
1641 return (void*) ptr;
1642 ptr += sizeof(int);
1643 }
1644 if (seg->flags & AF_SIZE_OR_WEIGHT_LIMIT)
1645 {
1646 if (type == attr_vehicle_width)
1647 return (void*) ptr;
1648 ptr += sizeof(struct size_weight_limit);
1649 }
1650 if (seg->flags & AF_DANGEROUS_GOODS)
1651 {
1652 if (type == attr_vehicle_dangerous_goods)
1653 return (void*) ptr;
1654 ptr += sizeof(int);
1655 }
1656 return NULL;
1657 }
1658
1659 /**
1660 * @brief Calculates the size of a route_segment_data struct with given flags
1661 *
1662 * @param flags The flags of the route_segment_data
1663 */
1664 static int route_segment_data_size(int flags)
1665 {
1666 //// dbg(0, "enter\n");
1667
1668 int ret = sizeof(struct route_segment_data);
1669 if (flags & AF_SPEED_LIMIT)
1670 ret += sizeof(int);
1671 if (flags & AF_SEGMENTED)
1672 ret += sizeof(int);
1673 if (flags & AF_SIZE_OR_WEIGHT_LIMIT)
1674 ret += sizeof(struct size_weight_limit);
1675 if (flags & AF_DANGEROUS_GOODS)
1676 ret += sizeof(int);
1677 return ret;
1678 }
1679
1680 static int route_graph_segment_is_duplicate(struct route_graph_point *start, struct route_graph_segment_data *data)
1681 {
1682 //// dbg(0, "enter\n");
1683
1684 struct route_graph_segment *s;
1685 s = start->start;
1686 while (s)
1687 {
1688 if (item_is_equal(*data->item, s->data.item))
1689 {
1690 if (data->flags & AF_SEGMENTED)
1691 {
1692 if (RSD_OFFSET(&s->data) == data->offset)
1693 {
1694 return 1;
1695 }
1696 }
1697 else
1698 return 1;
1699 }
1700 s = s->start_next;
1701 }
1702 return 0;
1703 }
1704
1705 /**
1706 * @brief Inserts a new segment into the route graph
1707 *
1708 * This function performs a check if a segment for the item specified already exists, and inserts
1709 * a new segment representing this item if it does not.
1710 *
1711 * @param this The route graph to insert the segment into
1712 * @param start The graph point which should be connected to the start of this segment
1713 * @param end The graph point which should be connected to the end of this segment
1714 * @param len The length of this segment
1715 * @param item The item that is represented by this segment
1716 * @param flags Flags for this segment
1717 * @param offset If the item passed in "item" is segmented (i.e. divided into several segments), this indicates the position of this segment within the item
1718 * @param maxspeed The maximum speed allowed on this segment in km/h. -1 if not known.
1719 */
1720 static void route_graph_add_segment(struct route_graph *this, struct route_graph_point *start, struct route_graph_point *end, struct route_graph_segment_data *data)
1721 {
1722 //// dbg(0, "enter\n");
1723
1724 struct route_graph_segment *s;
1725 int size;
1726
1727 size = sizeof(struct route_graph_segment) - sizeof(struct route_segment_data) + route_segment_data_size(data->flags);
1728
1729 s = g_slice_alloc0(size);
1730 //global_route_memory_size = global_route_memory_size + size;
1731 //dbg(0,"(A)route mem=%lu\n", global_route_memory_size);
1732
1733 if (!s)
1734 {
1735 printf("%s:Out of memory\n", __FUNCTION__);
1736 return;
1737 }
1738
1739 s->start = start;
1740 s->start_next = start->start;
1741 start->start = s;
1742 s->end = end;
1743 s->end_next = end->end;
1744 end->end = s;
1745 dbg_assert(data->len >= 0);
1746 s->data.len = data->len;
1747 s->data.item = *data->item;
1748 s->data.flags = data->flags;
1749
1750 if (data->flags & AF_SPEED_LIMIT)
1751 RSD_MAXSPEED(&s->data) = data->maxspeed;
1752
1753 if (data->flags & AF_SEGMENTED)
1754 RSD_OFFSET(&s->data) = data->offset;
1755
1756 if (data->flags & AF_SIZE_OR_WEIGHT_LIMIT)
1757 RSD_SIZE_WEIGHT(&s->data) = data->size_weight;
1758
1759 if (data->flags & AF_DANGEROUS_GOODS)
1760 RSD_DANGEROUS_GOODS(&s->data) = data->dangerous_goods;
1761
1762 s->next = this->route_segments;
1763 this->route_segments = s;
1764
1765 //if (debug_route)
1766 //{
1767 // printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
1768 //}
1769 }
1770
1771 /**
1772 * @brief Gets all the coordinates of an item
1773 *
1774 * This will get all the coordinates of the item i and return them in c,
1775 * up to max coordinates. Additionally it is possible to limit the coordinates
1776 * returned to all the coordinates of the item between the two coordinates
1777 * "start" and "end".
1778 *
1779 * @important Make sure that whatever c points to has enough memory allocated
1780 * @important to hold max coordinates!
1781 *
1782 * @param i The item to get the coordinates of
1783 * @param c Pointer to memory allocated for holding the coordinates
1784 * @param max Maximum number of coordinates to return
1785 * @param start First coordinate to get
1786 * @param end Last coordinate to get
1787 * @return The number of coordinates returned
1788 */
1789 static int get_item_seg_coords(struct item *i, struct coord *c, int max, struct coord *start, struct coord *end)
1790 {
1791 //// dbg(0, "enter\n");
1792
1793 struct map_rect *mr;
1794 struct item *item;
1795 int rc = 0, p = 0;
1796 struct coord c1;
1797 mr = map_rect_new(i->map, NULL);
1798
1799 if (!mr)
1800 return 0;
1801
1802 item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
1803
1804 if (item)
1805 {
1806 rc = item_coord_get(item, &c1, 1);
1807
1808 while (rc && (c1.x != start->x || c1.y != start->y))
1809 {
1810 rc = item_coord_get(item, &c1, 1);
1811 }
1812
1813 while (rc && p < max)
1814 {
1815 c[p++] = c1;
1816 if (c1.x == end->x && c1.y == end->y)
1817 break;
1818 rc = item_coord_get(item, &c1, 1);
1819 }
1820 }
1821 map_rect_destroy(mr);
1822 return p;
1823 }
1824
1825 /**
1826 * @brief Returns and removes one segment from a path
1827 *
1828 * @param path The path to take the segment from
1829 * @param item The item whose segment to remove
1830 * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
1831 * @return The segment removed
1832 */
1833 static struct route_path_segment *
1834 route_extract_segment_from_path(struct route_path *path, struct item *item, int offset)
1835 {
1836 //// dbg(0, "enter\n");
1837
1838 int soffset;
1839 struct route_path_segment *sp = NULL, *s;
1840 s = path->path;
1841 while (s)
1842 {
1843 if (item_is_equal(s->data->item, *item))
1844 {
1845 if (s->data->flags & AF_SEGMENTED)
1846 soffset = RSD_OFFSET(s->data);
1847 else
1848 soffset = 1;
1849 if (soffset == offset)
1850 {
1851 if (sp)
1852 {
1853 sp->next = s->next;
1854 break;
1855 }
1856 else
1857 {
1858 path->path = s->next;
1859 break;
1860 }
1861 }
1862 }
1863 sp = s;
1864 s = s->next;
1865 }
1866 if (s)
1867 item_hash_remove(path->path_hash, item);
1868 return s;
1869 }
1870
1871 /**
1872 * @brief Adds a segment and the end of a path
1873 *
1874 * @param this The path to add the segment to
1875 * @param segment The segment to add
1876 */
1877 static void route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
1878 {
1879 //// dbg(0, "enter\n");
1880
1881 if (!this->path)
1882 this->path = segment;
1883 if (this->path_last)
1884 this->path_last->next = segment;
1885 this->path_last = segment;
1886 }
1887
1888 /**
1889 * @brief Adds a two coordinate line to a path
1890 *
1891 * This adds a new line to a path, creating a new segment for it.
1892 *
1893 * @param this The path to add the item to
1894 * @param start coordinate to add to the start of the item. If none should be added, make this NULL.
1895 * @param end coordinate to add to the end of the item. If none should be added, make this NULL.
1896 * @param len The length of the item
1897 */
1898 static void route_path_add_line(struct route_path *this, struct coord *start, struct coord *end, int len)
1899 {
1900 //dbg(0, "enter\n");
1901
1902 int ccnt = 2;
1903 struct route_path_segment *segment;
1904 int seg_size, seg_dat_size;
1905
1906 //dbg(0, "line from 0x%x,0x%x-0x%x,0x%x\n", start->x, start->y, end->x, end->y);
1907
1908 seg_size = sizeof(*segment) + sizeof(struct coord) * ccnt;
1909 seg_dat_size = sizeof(struct route_segment_data);
1910 segment = g_malloc0(seg_size + seg_dat_size);
1911 //global_route_memory_size = global_route_memory_size + seg_size + seg_dat_size;
1912 //dbg(0,"route mem=%lu\n", global_route_memory_size);
1913
1914 segment->data = (struct route_segment_data *) ((char *) segment + seg_size);
1915 segment->ncoords = ccnt;
1916 segment->direction = 0;
1917 segment->c[0] = *start;
1918 segment->c[1] = *end;
1919 segment->data->len = len;
1920 route_path_add_segment(this, segment);
1921 }
1922
1923 /**
1924 * @brief Inserts a new item into the path
1925 *
1926 * This function does almost the same as "route_path_add_item()", but identifies
1927 * the item to add by a segment from the route graph. Another difference is that it "copies" the
1928 * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
1929 * be added to the route path, not all segments of the item.
1930 *
1931 * The function can be sped up by passing an old path already containing this segment in oldpath -
1932 * the segment will then be extracted from this old path. Please note that in this case the direction
1933 * parameter has no effect.
1934 *
1935 * @param this The path to add the item to
1936 * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
1937 * @param rgs Segment of the route graph that should be "copied" to the route path
1938 * @param dir Order in which to add the coordinates. See route_path_add_item()
1939 * @param pos Information about start point if this is the first segment
1940 * @param dst Information about end point if this is the last segment
1941 */
1942 static int route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath, struct route_graph_segment *rgs, int dir, struct route_info *pos, struct route_info *dst)
1943 {
1944 //// dbg(0, "enter\n");
1945
1946 struct route_path_segment *segment;
1947 int i, ccnt, extra = 0, ret = 0;
1948 struct coord *c, *cd, ca[2048];
1949 int offset = 1;
1950 int seg_size, seg_dat_size;
1951 int len = rgs->data.len;
1952 if (rgs->data.flags & AF_SEGMENTED)
1953 {
1954 offset = RSD_OFFSET(&rgs->data);
1955 }
1956
1957 //dbg(1, "enter (0x%x,0x%x) dir=%d pos=%p dst=%p\n", rgs->data.item.id_hi,
1958 // rgs->data.item.id_lo, dir, pos, dst);
1959 if (oldpath)
1960 {
1961 segment = item_hash_lookup(oldpath->path_hash, &rgs->data.item);
1962 if (segment && segment->direction == dir)
1963 {
1964 segment = route_extract_segment_from_path(oldpath, &rgs->data.item, offset);
1965 if (segment)
1966 {
1967 ret = 1;
1968 if (!pos)
1969 goto linkold;
1970 }
1971 }
1972 }
1973
1974 if (pos)
1975 {
1976 if (dst)
1977 {
1978 extra = 2;
1979 if (dst->lenneg >= pos->lenneg)
1980 {
1981 dir = 1;
1982 ccnt = dst->pos - pos->pos;
1983 c = pos->street->c + pos->pos + 1;
1984 len = dst->lenneg - pos->lenneg;
1985 }
1986 else
1987 {
1988 dir = -1;
1989 ccnt = pos->pos - dst->pos;
1990 c = pos->street->c + dst->pos + 1;
1991 len = pos->lenneg - dst->lenneg;
1992 }
1993 }
1994 else
1995 {
1996 extra = 1;
1997 //dbg(1, "pos dir=%d\n", dir);
1998 //dbg(1, "pos pos=%d\n", pos->pos);
1999 //dbg(1, "pos count=%d\n", pos->street->count);
2000 if (dir > 0)
2001 {
2002 c = pos->street->c + pos->pos + 1;
2003 ccnt = pos->street->count - pos->pos - 1;
2004 len = pos->lenpos;
2005 }
2006 else
2007 {
2008 c = pos->street->c;
2009 ccnt = pos->pos + 1;
2010 len = pos->lenneg;
2011 }
2012 }
2013 pos->dir = dir;
2014 }
2015 else if (dst)
2016 {
2017 extra = 1;
2018 //dbg(1, "dst dir=%d\n", dir);
2019 //dbg(1, "dst pos=%d\n", dst->pos);
2020 if (dir > 0)
2021 {
2022 c = dst->street->c;
2023 ccnt = dst->pos + 1;
2024 len = dst->lenpos;
2025 }
2026 else
2027 {
2028 c = dst->street->c + dst->pos + 1;
2029 ccnt = dst->street->count - dst->pos - 1;
2030 len = dst->lenneg;
2031 }
2032 }
2033 else
2034 {
2035 ccnt = get_item_seg_coords(&rgs->data.item, ca, 2047, &rgs->start->c, &rgs->end->c);
2036 c = ca;
2037 }
2038 seg_size = sizeof(*segment) + sizeof(struct coord) * (ccnt + extra);
2039 seg_dat_size = route_segment_data_size(rgs->data.flags);
2040 segment = g_malloc0(seg_size + seg_dat_size);
2041 //global_route_memory_size = global_route_memory_size + seg_size + seg_dat_size;
2042 //dbg(0,"route mem=%lu\n", global_route_memory_size);
2043
2044 segment->data = (struct route_segment_data *) ((char *) segment + seg_size);
2045 segment->direction = dir;
2046 cd = segment->c;
2047 if (pos && (c[0].x != pos->lp.x || c[0].y != pos->lp.y))
2048 *cd++ = pos->lp;
2049 if (dir < 0)
2050 c += ccnt - 1;
2051 for (i = 0; i < ccnt; i++)
2052 {
2053 *cd++ = *c;
2054 c += dir;
2055 }
2056 segment->ncoords += ccnt;
2057 if (dst && (cd[-1].x != dst->lp.x || cd[-1].y != dst->lp.y))
2058 *cd++ = dst->lp;
2059 segment->ncoords = cd - segment->c;
2060 if (segment->ncoords <= 1)
2061 {
2062 g_free(segment);
2063 // xxx
2064 return 1;
2065 }
2066
2067 /* We check if the route graph segment is part of a roundabout here, because this
2068 * only matters for route graph segments which form parts of the route path */
2069 if (!(rgs->data.flags & AF_ROUNDABOUT))
2070 { // We identified this roundabout earlier
2071 route_check_roundabout(rgs, 13, (dir < 1), NULL);
2072 }
2073
2074 memcpy(segment->data, &rgs->data, seg_dat_size);
2075 linkold: segment->data->len = len;
2076 segment->next = NULL;
2077 item_hash_insert(this->path_hash, &rgs->data.item, segment);
2078
2079 route_path_add_segment(this, segment);
2080
2081 return ret;
2082 }
2083
2084 /**
2085 * @brief Destroys all segments of a route graph
2086 *
2087 * @param this The graph to destroy all segments from
2088 */
2089 static void route_graph_free_segments(struct route_graph *this)
2090 {
2091 //// dbg(0, "enter\n");
2092
2093 struct route_graph_segment *curr, *next;
2094 int size;
2095 curr = this->route_segments;
2096 while (curr)
2097 {
2098 next = curr->next;
2099 size = sizeof(struct route_graph_segment) - sizeof(struct route_segment_data) + route_segment_data_size(curr->data.flags);
2100 g_slice_free1(size, curr);
2101 //global_route_memory_size = global_route_memory_size - size;
2102 //dbg(0,"(F)route mem=%lu\n", global_route_memory_size);
2103 curr = next;
2104 }
2105 this->route_segments = NULL;
2106 }
2107
2108 /**
2109 * @brief Destroys a route graph
2110 *
2111 * @param this The route graph to be destroyed
2112 */
2113 void route_graph_destroy(struct route_graph *this)
2114 {
2115 // dbg(0, "enter\n");
2116
2117 if (this)
2118 {
2119 route_graph_build_done(this, 1);
2120 route_graph_free_points(this);
2121 route_graph_free_segments(this);
2122 g_free(this);
2123 }
2124 }
2125
2126 /**
2127 * @brief Returns the estimated speed on a segment
2128 *
2129 * This function returns the estimated speed to be driven on a segment, 0=not passable
2130 *
2131 * @param profile The routing preferences
2132 * @param over The segment which is passed
2133 * @param dist A traffic distortion if applicable
2134 * @return The estimated speed
2135 */
2136 static int route_seg_speed(struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist)
2137 {
2138 //// dbg(0, "enter\n");
2139
2140 struct roadprofile *roadprofile = vehicleprofile_get_roadprofile(profile, over->item.type);
2141 int speed, maxspeed;
2142 if (!roadprofile || !roadprofile->route_weight)
2143 return 0;
2144 /* maxspeed_handling: 0=always, 1 only if maxspeed restricts the speed, 2 never */
2145 speed = roadprofile->route_weight;
2146 if (profile->maxspeed_handling != 2)
2147 {
2148 if (over->flags & AF_SPEED_LIMIT)
2149 {
2150 maxspeed = RSD_MAXSPEED(over);
2151 if (!profile->maxspeed_handling)
2152 speed = maxspeed;
2153 }
2154 else
2155 maxspeed = INT_MAX;
2156 if (dist && maxspeed > dist->maxspeed)
2157 maxspeed = dist->maxspeed;
2158 if (maxspeed != INT_MAX && (profile->maxspeed_handling != 1 || maxspeed < speed))
2159 speed = maxspeed;
2160 }
2161
2162 if (over->flags & AF_DANGEROUS_GOODS)
2163 {
2164 if (profile->dangerous_goods & RSD_DANGEROUS_GOODS(over))
2165 return 0;
2166 }
2167
2168 if (over->flags & AF_SIZE_OR_WEIGHT_LIMIT)
2169 {
2170 struct size_weight_limit *size_weight = &RSD_SIZE_WEIGHT(over);
2171 if (size_weight->width != -1 && profile->width != -1 && profile->width > size_weight->width)
2172 return 0;
2173 if (size_weight->height != -1 && profile->height != -1 && profile->height > size_weight->height)
2174 return 0;
2175 if (size_weight->length != -1 && profile->length != -1 && profile->length > size_weight->length)
2176 return 0;
2177 if (size_weight->weight != -1 && profile->weight != -1 && profile->weight > size_weight->weight)
2178 return 0;
2179 if (size_weight->axle_weight != -1 && profile->axle_weight != -1 && profile->axle_weight > size_weight->axle_weight)
2180 return 0;
2181 }
2182 return speed;
2183 }
2184
2185 /**
2186 * @brief Returns the time needed to drive len on item
2187 *
2188 * This function returns the time needed to drive len meters on
2189 * the item passed in item in tenth of seconds.
2190 *
2191 * @param profile The routing preferences
2192 * @param over The segment which is passed
2193 * @param dist A traffic distortion if applicable
2194 * @return The time needed to drive len on item in thenth of seconds
2195 */
2196 static int route_time_seg(struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist)
2197 {
2198 // // dbg(0, "enter\n");
2199
2200 int speed = route_seg_speed(profile, over, dist);
2201 if (!speed)
2202 {
2203 return INT_MAX;
2204 }
2205 return over->len * 36 / speed + (dist ? dist->delay : 0);
2206 }
2207
2208 static int route_get_traffic_distortion(struct route_graph_segment *seg, struct route_traffic_distortion *ret)
2209 {
2210 // // dbg(0, "enter\n");
2211
2212 struct route_graph_point *start = seg->start;
2213 struct route_graph_point *end = seg->end;
2214 struct route_graph_segment *tmp, *found = NULL;
2215 tmp = start->start;
2216 while (tmp && !found)
2217 {
2218 if (tmp->data.item.type == type_traffic_distortion && tmp->start == start && tmp->end == end)
2219 found = tmp;
2220 tmp = tmp->start_next;
2221 }
2222 tmp = start->end;
2223 while (tmp && !found)
2224 {
2225 if (tmp->data.item.type == type_traffic_distortion && tmp->end == start && tmp->start == end)
2226 found = tmp;
2227 tmp = tmp->end_next;
2228 }
2229 if (found)
2230 {
2231 ret->delay = found->data.len;
2232 if (found->data.flags & AF_SPEED_LIMIT)
2233 ret->maxspeed = RSD_MAXSPEED(&found->data);
2234 else
2235 ret->maxspeed = INT_MAX;
2236 return 1;
2237 }
2238 return 0;
2239 }
2240
2241 static int route_through_traffic_allowed(struct vehicleprofile *profile, struct route_graph_segment *seg)
2242 {
2243 //// dbg(0, "enter\n");
2244
2245 return (seg->data.flags & AF_THROUGH_TRAFFIC_LIMIT) == 0;
2246 }
2247
2248 /**
2249 * @brief Returns the "costs" of driving from point "from" over segment "over" in direction "dir"
2250 *
2251 * @param profile The routing preferences
2252 * @param from The point where we are starting
2253 * @param over The segment we are using
2254 * @param dir The direction of segment which we are driving
2255 * @return The "costs" needed to drive len on item
2256 */
2257 static int route_value_seg(struct vehicleprofile *profile, struct route_graph_point *from, struct route_graph_segment *over, int dir)
2258 {
2259 //// dbg(0, "enter\n");
2260
2261 int ret;
2262 struct route_traffic_distortion dist, *distp = NULL;
2263 #if 0
2264 dbg(0,"flags 0x%x mask 0x%x flags 0x%x\n", over->flags, dir >= 0 ? profile->flags_forward_mask : profile->flags_reverse_mask, profile->flags);
2265 #endif
2266 if ((over->data.flags & (dir >= 0 ? profile->flags_forward_mask : profile->flags_reverse_mask)) != profile->flags)
2267 return INT_MAX;
2268 if (dir > 0 && (over->start->flags & RP_TURN_RESTRICTION))
2269 return INT_MAX;
2270 if (dir < 0 && (over->end->flags & RP_TURN_RESTRICTION))
2271 return INT_MAX;
2272 if (from && from->seg == over)
2273 return INT_MAX;
2274 if ((over->start->flags & RP_TRAFFIC_DISTORTION) && (over->end->flags & RP_TRAFFIC_DISTORTION) && route_get_traffic_distortion(over, &dist))
2275 {
2276 distp = &dist;
2277 }
2278 ret = route_time_seg(profile, &over->data, distp);
2279 if (ret == INT_MAX)
2280 return ret;
2281
2282 if (!route_through_traffic_allowed(profile, over) && from && route_through_traffic_allowed(profile, from->seg))
2283 ret += profile->through_traffic_penalty;
2284
2285 // calc delay from traffic lights
2286 if ((from) && (global_traffic_light_delay > 0))
2287 {
2288 if (from->flags & RP_TRAFFIC_LIGHT)
2289 {
2290 // dbg(0, "traffic light delay:%d w/o:%d\n", (ret+global_traffic_light_delay), ret);
2291 // in 1/10 of a second !!
2292 ret += global_traffic_light_delay;
2293 }
2294 }
2295
2296 return ret;
2297 }
2298
2299
2300
2301
2302
2303 /**
2304 * @brief Adds a traffic light item to the route graph
2305 *
2306 * @param this The route graph to add to
2307 * @param item The item to add
2308 */
2309 static void route_process_traffic_light(struct route_graph *this, struct item *item)
2310 {
2311 struct route_graph_point *s_pnt, *e_pnt;
2312 struct coord l;
2313 struct route_graph_segment_data data;
2314
2315 data.item = item;
2316 data.len = 0;
2317 data.flags = 0;
2318 data.offset = 1;
2319 data.maxspeed = INT_MAX;
2320
2321 if (item_coord_get(item, &l, 1))
2322 {
2323 s_pnt = route_graph_add_point(this, &l);
2324 s_pnt->flags |= RP_TRAFFIC_LIGHT;
2325 }
2326 }
2327
2328
2329
2330
2331
2332 /**
2333 * @brief Adds a route distortion item to the route graph
2334 *
2335 * @param this The route graph to add to
2336 * @param item The item to add
2337 */
2338 static void route_process_traffic_distortion(struct route_graph *this, struct item *item)
2339 {
2340 // dbg(0, "enter\n");
2341
2342 struct route_graph_point *s_pnt, *e_pnt;
2343 struct coord c, l;
2344 struct attr delay_attr, maxspeed_attr;
2345 struct route_graph_segment_data data;
2346
2347 data.item = item;
2348 data.len = 0;
2349 data.flags = 0;
2350 data.offset = 1;
2351 data.maxspeed = INT_MAX;
2352
2353 if (item_coord_get(item, &l, 1))
2354 {
2355 s_pnt = route_graph_add_point(this, &l);
2356 while (item_coord_get(item, &c, 1))
2357 {
2358 l = c;
2359 }
2360
2361 e_pnt = route_graph_add_point(this, &l);
2362 s_pnt->flags |= RP_TRAFFIC_DISTORTION;
2363 e_pnt->flags |= RP_TRAFFIC_DISTORTION;
2364
2365 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr))
2366 {
2367 data.flags |= AF_SPEED_LIMIT;
2368 data.maxspeed = maxspeed_attr.u.num;
2369 }
2370
2371 if (item_attr_get(item, attr_delay, &delay_attr))
2372 {
2373 data.len = delay_attr.u.num;
2374 }
2375 //dbg(0,"add traffic distortion segment, speed=%d\n", data.maxspeed);
2376 route_graph_add_segment(this, s_pnt, e_pnt, &data);
2377 }
2378 }
2379
2380
2381 /**
2382 * @brief Adds a route distortion item to the route graph
2383 *
2384 * @param this The route graph to add to
2385 * @param item The item to add
2386 */
2387 static void route_process_turn_restriction(struct route_graph *this, struct item *item)
2388 {
2389 // dbg(0, "enter\n");
2390
2391 struct route_graph_point *pnt[4];
2392 struct coord c[5];
2393 int i, count;
2394 struct route_graph_segment_data data;
2395
2396 count = item_coord_get(item, c, 5);
2397 if (count != 3 && count != 4)
2398 {
2399 //dbg(0, "wrong count %d\n", count);
2400 return;
2401 }
2402 if (count == 4)
2403 {
2404 return;
2405 }
2406 for (i = 0; i < count; i++)
2407 {
2408 pnt[i] = route_graph_add_point(this, &c[i]);
2409 }
2410 //dbg(1, "%s: (0x%x,0x%x)-(0x%x,0x%x)-(0x%x,0x%x) %p-%p-%p\n",
2411 // item_to_name(item->type), c[0].x, c[0].y, c[1].x, c[1].y, c[2].x,
2412 // c[2].y, pnt[0], pnt[1], pnt[2]);
2413 data.item = item;
2414 data.flags = 0;
2415 data.len = 0;
2416 route_graph_add_segment(this, pnt[0], pnt[1], &data);
2417 route_graph_add_segment(this, pnt[1], pnt[2], &data);
2418 #if 1
2419 if (count == 4)
2420 {
2421 pnt[1]->flags |= RP_TURN_RESTRICTION;
2422 pnt[2]->flags |= RP_TURN_RESTRICTION;
2423 route_graph_add_segment(this, pnt[2], pnt[3], &data);
2424 }
2425 else
2426 {
2427 pnt[1]->flags |= RP_TURN_RESTRICTION;
2428 }
2429 #endif
2430 }
2431
2432 /**
2433 * @brief Adds an item to the route graph
2434 *
2435 * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
2436 * segmented item.
2437 *
2438 * @param this The route graph to add to
2439 * @param item The item to add
2440 * @param profile The vehicle profile currently in use
2441 */
2442 static void route_process_street_graph(struct route_graph *this, struct item *item, struct vehicleprofile *profile)
2443 {
2444 //// dbg(0, "enter\n");
2445
2446 #ifdef AVOID_FLOAT
2447 int len=0;
2448 #else
2449 double len = 0;
2450 #endif
2451 int segmented = 0;
2452 struct roadprofile *roadp;
2453 struct route_graph_point *s_pnt, *e_pnt;
2454 struct coord c, l;
2455 struct attr attr;
2456 struct route_graph_segment_data data;
2457 data.flags = 0;
2458 data.offset = 1;
2459 data.maxspeed = -1;
2460 data.item = item;
2461
2462 roadp = vehicleprofile_get_roadprofile(profile, item->type);
2463 if (!roadp)
2464 {
2465 //dbg(0,"*[0]type=%s\n", item_to_name(item->type));
2466 // Don't include any roads that don't have a road profile in our vehicle profile
2467 return;
2468 }
2469
2470 if (item_coord_get(item, &l, 1))
2471 {
2472 int *default_flags = item_get_default_flags(item->type);
2473 if (!default_flags)
2474 {
2475 //dbg(0,"*[1]type=%s\n", item_to_name(item->type));
2476 return;
2477 }
2478
2479 if (item_attr_get(item, attr_flags, &attr))
2480 {
2481 data.flags = attr.u.num;
2482 if (data.flags & AF_SEGMENTED)
2483 {
2484 segmented = 1;
2485 }
2486 }
2487 else
2488 {
2489 data.flags = *default_flags;
2490 }
2491
2492 if (data.flags & AF_SPEED_LIMIT)
2493 {
2494 if (item_attr_get(item, attr_maxspeed, &attr))
2495 {
2496 data.maxspeed = attr.u.num;
2497 }
2498 }
2499 if (data.flags & AF_DANGEROUS_GOODS)
2500 {
2501 if (item_attr_get(item, attr_vehicle_dangerous_goods, &attr))
2502 {
2503 data.dangerous_goods = attr.u.num;
2504 }
2505 else
2506 {
2507 data.flags &= ~AF_DANGEROUS_GOODS;
2508 }
2509 }
2510 if (data.flags & AF_SIZE_OR_WEIGHT_LIMIT)
2511 {
2512 if (item_attr_get(item, attr_vehicle_width, &attr))
2513 data.size_weight.width = attr.u.num;
2514 else
2515 data.size_weight.width = -1;
2516 if (item_attr_get(item, attr_vehicle_height, &attr))
2517 data.size_weight.height = attr.u.num;
2518 else
2519 data.size_weight.height = -1;
2520 if (item_attr_get(item, attr_vehicle_length, &attr))
2521 data.size_weight.length = attr.u.num;
2522 else
2523 data.size_weight.length = -1;
2524 if (item_attr_get(item, attr_vehicle_weight, &attr))
2525 data.size_weight.weight = attr.u.num;
2526 else
2527 data.size_weight.weight = -1;
2528 if (item_attr_get(item, attr_vehicle_axle_weight, &attr))
2529 data.size_weight.axle_weight = attr.u.num;
2530 else
2531 data.size_weight.axle_weight = -1;
2532 }
2533
2534 s_pnt = route_graph_add_point(this, &l);
2535 if (!segmented)
2536 {
2537 while (item_coord_get(item, &c, 1))
2538 {
2539 len += transform_distance(map_projection(item->map), &l, &c);
2540 l = c;
2541 }
2542 e_pnt = route_graph_add_point(this, &l);
2543 dbg_assert(len >= 0);
2544 data.len = len;
2545 if (!route_graph_segment_is_duplicate(s_pnt, &data))
2546 {
2547 route_graph_add_segment(this, s_pnt, e_pnt, &data);
2548 }
2549 }
2550 else
2551 {
2552 int isseg, rc;
2553 int sc = 0;
2554 do
2555 {
2556 isseg = item_coord_is_node(item);
2557 rc = item_coord_get(item, &c, 1);
2558 if (rc)
2559 {
2560 len += transform_distance(map_projection(item->map), &l, &c);
2561 l = c;
2562 if (isseg)
2563 {
2564 e_pnt = route_graph_add_point(this, &l);
2565 data.len = len;
2566 if (!route_graph_segment_is_duplicate(s_pnt, &data))
2567 {
2568 route_graph_add_segment(this, s_pnt, e_pnt, &data);
2569 }
2570 data.offset++;
2571 s_pnt = route_graph_add_point(this, &l);
2572 len = 0;
2573 }
2574 }
2575 }
2576 while (rc);
2577
2578 e_pnt = route_graph_add_point(this, &l);
2579 dbg_assert(len >= 0);
2580 sc++;
2581 data.len = len;
2582 if (!route_graph_segment_is_duplicate(s_pnt, &data))
2583 {
2584 route_graph_add_segment(this, s_pnt, e_pnt, &data);
2585 }
2586 }
2587 }
2588 }
2589
2590 static struct route_graph_segment *
2591 route_graph_get_segment(struct route_graph *graph, struct street_data *sd, struct route_graph_segment *last)
2592 {
2593 //// dbg(0, "enter\n");
2594
2595 struct route_graph_point *start = NULL;
2596 struct route_graph_segment *s;
2597 int seen = 0;
2598
2599 while ((start = route_graph_get_point_next(graph, &sd->c[0], start)))
2600 {
2601 s = start->start;
2602 while (s)
2603 {
2604 if (item_is_equal(sd->item, s->data.item))
2605 {
2606 if (!last || seen)
2607 return s;
2608 if (last == s)
2609 seen = 1;
2610 }
2611 s = s->start_next;
2612 }
2613 }
2614 return NULL;
2615 }
2616
2617 /**
2618 * @brief Calculates the routing costs for each point
2619 *
2620 * This function is the heart of routing. It assigns each point in the route graph a
2621 * cost at which one can reach the destination from this point on. Additionally it assigns
2622 * each point a segment one should follow from this point on to reach the destination at the
2623 * stated costs.
2624 *
2625 * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
2626 * at this algorithm.
2627 */
2628 static void route_graph_flood(struct route_graph *this, struct route_info *dst, struct vehicleprofile *profile, struct callback *cb)
2629 {
2630 //dbg(0, "enter\n");
2631
2632 struct route_graph_point *p_min;
2633 struct route_graph_segment *s = NULL;
2634 int min, new, old, val;
2635 struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
2636
2637 heap = fh_makekeyheap();
2638
2639 // start from "wanted destination" and loop until "start position" is reached
2640 while ((s = route_graph_get_segment(this, dst->street, s)))
2641 {
2642 val = route_value_seg(profile, NULL, s, -1);
2643 if (val != INT_MAX)
2644 {
2645 val = val * (100 - dst->percent) / 100;
2646 s->end->seg = s;
2647 s->end->value = val;
2648 s->end->el = fh_insertkey(heap, s->end->value, s->end);
2649 }
2650
2651 val = route_value_seg(profile, NULL, s, 1);
2652 if (val != INT_MAX)
2653 {
2654 val = val * dst->percent / 100;
2655 s->start->seg = s;
2656 s->start->value = val;
2657 s->start->el = fh_insertkey(heap, s->start->value, s->start);
2658 }
2659 }
2660
2661 for (;;)
2662 {
2663 p_min = fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
2664
2665 if (!p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
2666 {
2667 break;
2668 }
2669
2670 min = p_min->value;
2671 //if (debug_route)
2672 //{
2673 // printf("extract p=%p free el=%p min=%d, 0x%x, 0x%x\n", p_min, p_min->el, min, p_min->c.x, p_min->c.y);
2674 //}
2675
2676 p_min->el = NULL; /* This point is permanently calculated now, we've taken it out of the heap */
2677
2678 s = p_min->start;
2679
2680 while (s)
2681 { /* Iterating all the segments leading away from our point to update the points at their ends */
2682 val = route_value_seg(profile, p_min, s, -1);
2683 if (val != INT_MAX && !item_is_equal(s->data.item, p_min->seg->data.item))
2684 {
2685 new = min + val;
2686 //if (debug_route)
2687 //{
2688 // printf("begin %d len %d vs %d (0x%x,0x%x)\n", new, val, s->end->value, s->end->c.x, s->end->c.y);
2689 //}
2690
2691 if (new < s->end->value)
2692 { /* We've found a less costly way to reach the end of s, update it */
2693 s->end->value = new;
2694 s->end->seg = s;
2695 if (!s->end->el)
2696 {
2697 //if (debug_route)
2698 //{
2699 // printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
2700 //}
2701
2702 s->end->el = fh_insertkey(heap, new, s->end);
2703
2704 //if (debug_route)
2705 //{
2706 // printf("el new=%p\n", s->end->el);
2707 //}
2708 }
2709 else
2710 {
2711 //if (debug_route)
2712 //{
2713 // printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
2714 //}
2715 fh_replacekey(heap, s->end->el, new);
2716 }
2717 }
2718
2719 //if (debug_route)
2720 //{
2721 // printf("\n");
2722 //}
2723 }
2724 s = s->start_next;
2725 }
2726
2727 s = p_min->end;
2728
2729 while (s)
2730 { /* Doing the same as above with the segments leading towards our point */
2731 val = route_value_seg(profile, p_min, s, 1);
2732 if (val != INT_MAX && !item_is_equal(s->data.item, p_min->seg->data.item))
2733 {
2734 new = min + val;
2735 //if (debug_route)
2736 //{
2737 // printf("end %d len %d vs %d (0x%x,0x%x)\n", new, val, s->start->value, s->start->c.x, s->start->c.y);
2738 //}
2739
2740 if (new < s->start->value)
2741 {
2742 old = s->start->value;
2743 s->start->value = new;
2744 s->start->seg = s;
2745 if (!s->start->el)
2746 {
2747 //if (debug_route)
2748 //{
2749 // printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
2750 //}
2751 s->start->el = fh_insertkey(heap, new, s->start);
2752 //if (debug_route)
2753 //{
2754 // printf("el new=%p\n", s->start->el);
2755 //}
2756 }
2757 else
2758 {
2759 //if (debug_route)
2760 //{
2761 // printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
2762 //}
2763 fh_replacekey(heap, s->start->el, new);
2764 }
2765 }
2766 //if (debug_route)
2767 //{
2768 // printf("\n");
2769 //}
2770 }
2771 s = s->end_next;
2772 }
2773 }
2774
2775 fh_deleteheap(heap);
2776
2777 callback_call_0(cb);
2778 }
2779
2780 /**
2781 * @brief Starts an "offroad" path
2782 *
2783 * This starts a path that is not located on a street. It creates a new route path
2784 * adding only one segment, that leads from pos to dest, and which is not associated with an item.
2785 *
2786 * @param this Not used
2787 * @param pos The starting position for the new path
2788 * @param dst The destination of the new path
2789 * @param dir Not used
2790 * @return The new path
2791 */
2792 static struct route_path *
2793 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst)
2794 {
2795 // dbg(0, "enter\n");
2796
2797 struct route_path *ret;
2798
2799 ret=g_new0(struct route_path, 1);
2800 ret->in_use = 1;
2801 ret->path_hash = item_hash_new();
2802 route_path_add_line(ret, &pos->c, &dst->c, pos->lenextra + dst->lenextra);
2803 ret->updated = 1;
2804
2805 return ret;
2806 }
2807
2808 /**
2809 * @brief Returns a coordinate at a given distance
2810 *
2811 * This function returns the coordinate, where the user will be if he
2812 * follows the current route for a certain distance.
2813 *
2814 * @param this_ The route we're driving upon
2815 * @param dist The distance in meters
2816 * @return The coordinate where the user will be in that distance
2817 */
2818 struct coord route_get_coord_dist(struct route *this_, int dist)
2819 {
2820 // dbg(0, "enter\n");
2821
2822 int d, l, i, len;
2823 int dx, dy;
2824 double frac;
2825 struct route_path_segment *cur;
2826 struct coord ret;
2827 enum projection pro = route_projection(this_);
2828 struct route_info *dst = route_get_dst(this_);
2829
2830 d = dist;
2831
2832 if (!this_->path2 || pro == projection_none)
2833 {
2834 return this_->pos->c;
2835 }
2836
2837 ret = this_->pos->c;
2838 cur = this_->path2->path;
2839 while (cur)
2840 {
2841 if (cur->data->len < d)
2842 {
2843 d -= cur->data->len;
2844 }
2845 else
2846 {
2847 for (i = 0; i < (cur->ncoords - 1); i++)
2848 {
2849 l = d;
2850 len = (int) transform_polyline_length(pro, (cur->c + i), 2);
2851 d -= len;
2852 if (d <= 0)
2853 {
2854 // We interpolate a bit here...
2855 frac = (double) l / len;
2856
2857 dx = (cur->c + i + 1)->x - (cur->c + i)->x;
2858 dy = (cur->c + i + 1)->y - (cur->c + i)->y;
2859
2860 ret.x = (cur->c + i)->x + (frac * dx);
2861 ret.y = (cur->c + i)->y + (frac * dy);
2862 return ret;
2863 }
2864 }
2865 return cur->c[(cur->ncoords - 1)];
2866 }
2867 cur = cur->next;
2868 }
2869
2870 return dst->c;
2871 }
2872
2873 /**
2874 * @brief Creates a new route path
2875 *
2876 * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
2877 * make sure to run route_graph_flood() after changing the destination before using this function.
2878 *
2879 * @param this The route graph to create the route from
2880 * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
2881 * @param pos The starting position of the route
2882 * @param dst The destination of the route
2883 * @param preferences The routing preferences
2884 * @return The new route path
2885 */
2886 static struct route_path *
2887 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct vehicleprofile *profile)
2888 {
2889 //dbg(0, "enter\n");
2890
2891 struct route_graph_segment *first, *s = NULL, *s1 = NULL, *s2 = NULL;
2892 struct route_graph_point *start;
2893 struct route_info *posinfo, *dstinfo;
2894 int segs = 0;
2895 int val1 = INT_MAX, val2 = INT_MAX;
2896 int val, val1_new, val2_new;
2897 struct route_path *ret;
2898
2899 if (!pos->street || !dst->street)
2900 {
2901 // dbg(0, "pos or dest not set\n");
2902 return NULL;
2903 }
2904
2905 if (profile->mode == 2 || (profile->mode == 0 && pos->lenextra + dst->lenextra > transform_distance(map_projection(pos->street->item.map), &pos->c, &dst->c)))
2906 {
2907 return route_path_new_offroad(this, pos, dst);
2908 }
2909
2910 // ------ just calculate the smallest cost to reach destination ----------
2911 // ------ just calculate the smallest cost to reach destination ----------
2912 while ((s = route_graph_get_segment(this, pos->street, s)))
2913 {
2914 val = route_value_seg(profile, NULL, s, 1);
2915 if (val != INT_MAX && s->end->value != INT_MAX)
2916 {
2917 val = val * (100 - pos->percent) / 100;
2918 val1_new = s->end->value + val;
2919 if (val1_new < val1)
2920 {
2921 val1 = val1_new;
2922 s1 = s;
2923 }
2924 }
2925 val = route_value_seg(profile, NULL, s, -1);
2926 if (val != INT_MAX && s->start->value != INT_MAX)
2927 {
2928 val = val * pos->percent / 100;
2929 val2_new = s->start->value + val;
2930 if (val2_new < val2)
2931 {
2932 val2 = val2_new;
2933 s2 = s;
2934 }
2935 }
2936 }
2937 // ------ just calculate the smallest cost to reach destination ----------
2938 // ------ just calculate the smallest cost to reach destination ----------
2939
2940 if (val1 == INT_MAX && val2 == INT_MAX)
2941 {
2942 //dbg(0, "no route found, pos blocked\n");
2943 return NULL;
2944 }
2945
2946 if (val1 == val2)
2947 {
2948 val1 = s1->end->value;
2949 val2 = s2->start->value;
2950 }
2951
2952 if (val1 < val2)
2953 {
2954 start = s1->start;
2955 s = s1;
2956 }
2957 else
2958 {
2959 start = s2->end;
2960 s = s2;
2961 }
2962
2963 ret=g_new0(struct route_path, 1);
2964 ret->in_use = 1;
2965 ret->updated = 1;
2966
2967 if (pos->lenextra)
2968 {
2969 //dbg(0,"l extra1=%d\n", pos->lenextra);
2970 route_path_add_line(ret, &pos->c, &pos->lp, pos->lenextra);
2971 }
2972
2973 ret->path_hash = item_hash_new();
2974 dstinfo = NULL;
2975 posinfo = pos;
2976 first = s;
2977
2978 // ------- build the real route here ------------------------
2979 // ------- build the real route here ------------------------
2980 while (s && !dstinfo)
2981 { /* following start->seg, which indicates the least costly way to reach our destination */
2982 segs++;
2983 #if 0
2984 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
2985 #endif
2986 if (s->start == start)
2987 {
2988 if (item_is_equal(s->data.item, dst->street->item) && (s->end->seg == s || !posinfo))
2989 {
2990 dstinfo = dst;
2991 }
2992
2993 if (!route_path_add_item_from_graph(ret, oldpath, s, 1, posinfo, dstinfo))
2994 {
2995 ret->updated = 0;
2996 }
2997
2998 start = s->end;
2999 }
3000 else
3001 {
3002 if (item_is_equal(s->data.item, dst->street->item) && (s->start->seg == s || !posinfo))
3003 {
3004 dstinfo = dst;
3005 }
3006 if (!route_path_add_item_from_graph(ret, oldpath, s, -1, posinfo, dstinfo))
3007 {
3008 ret->updated = 0;
3009 }
3010 start = s->start;
3011 }
3012 posinfo = NULL;
3013 s = start->seg;
3014 }
3015 // ------- build the real route here ------------------------
3016 // ------- build the real route here ------------------------
3017
3018 if (dst->lenextra)
3019 {
3020 //dbg(0,"l extra2=%d\n", dst->lenextra);
3021 route_path_add_line(ret, &dst->lp, &dst->c, dst->lenextra);
3022 }
3023
3024 //dbg(1, "%d segments\n", segs);
3025 return ret;
3026 }
3027
3028 static int route_graph_build_next_map(struct route_graph *rg)
3029 {
3030 // dbg(0, "enter\n");
3031
3032 do
3033 {
3034 rg->m = mapset_next(rg->h, 2);
3035 if (!rg->m)
3036 return 0;
3037 map_rect_destroy(rg->mr);
3038 rg->mr = map_rect_new(rg->m, rg->sel);
3039 }
3040 while (!rg->mr);
3041
3042 return 1;
3043 }
3044
3045 static int is_turn_allowed(struct route_graph_point *p, struct route_graph_segment *from, struct route_graph_segment *to)
3046 {
3047 // dbg(0, "enter\n");
3048
3049 struct route_graph_point *prev, *next;
3050 struct route_graph_segment *tmp1, *tmp2;
3051 if (item_is_equal(from->data.item, to->data.item))
3052 return 0;
3053 if (from->start == p)
3054 prev = from->end;
3055 else
3056 prev = from->start;
3057 if (to->start == p)
3058 next = to->end;
3059 else
3060 next = to->start;
3061 tmp1 = p->end;
3062 while (tmp1)
3063 {
3064 if (tmp1->start->c.x == prev->c.x && tmp1->start->c.y == prev->c.y && (tmp1->data.item.type == type_street_turn_restriction_no || tmp1->data.item.type == type_street_turn_restriction_only))
3065 {
3066 tmp2 = p->start;
3067 //dbg(1, "found %s (0x%x,0x%x) (0x%x,0x%x)-(0x%x,0x%x) %p-%p\n",
3068 // item_to_name(tmp1->data.item.type), tmp1->data.item.id_hi,
3069 // tmp1->data.item.id_lo, tmp1->start->c.x, tmp1->start->c.y,
3070 // tmp1->end->c.x, tmp1->end->c.y, tmp1->start, tmp1->end);
3071 while (tmp2)
3072 {
3073 //dbg(
3074 // 1,
3075 // "compare %s (0x%x,0x%x) (0x%x,0x%x)-(0x%x,0x%x) %p-%p\n",
3076 // item_to_name(tmp2->data.item.type),
3077 // tmp2->data.item.id_hi, tmp2->data.item.id_lo,
3078 // tmp2->start->c.x, tmp2->start->c.y, tmp2->end->c.x,
3079 // tmp2->end->c.y, tmp2->start, tmp2->end);
3080 if (item_is_equal(tmp1->data.item, tmp2->data.item))
3081 {
3082 break;
3083 }
3084 tmp2 = tmp2->start_next;
3085 }
3086 //dbg(1, "tmp2=%p\n", tmp2);
3087 if (tmp2)
3088 {
3089 //dbg(1, "%s tmp2->end=%p next=%p\n",
3090 // item_to_name(tmp1->data.item.type), tmp2->end, next);
3091 }
3092 if (tmp1->data.item.type == type_street_turn_restriction_no && tmp2 && tmp2->end->c.x == next->c.x && tmp2->end->c.y == next->c.y)
3093 {
3094 //dbg(
3095 // 1,
3096 // "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x not allowed (no)\n",
3097 // prev->c.x, prev->c.y, p->c.x, p->c.y, next->c.x,
3098 // next->c.y);
3099 return 0;
3100 }
3101 if (tmp1->data.item.type == type_street_turn_restriction_only && tmp2 && (tmp2->end->c.x != next->c.x || tmp2->end->c.y != next->c.y))
3102 {
3103 //dbg(
3104 // 1,
3105 // "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x not allowed (only)\n",
3106 // prev->c.x, prev->c.y, p->c.x, p->c.y, next->c.x,
3107 // next->c.y);
3108 return 0;
3109 }
3110 }
3111 tmp1 = tmp1->end_next;
3112 }
3113 //dbg(1, "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x allowed\n", prev->c.x,
3114 // prev->c.y, p->c.x, p->c.y, next->c.x, next->c.y);
3115 return 1;
3116 }
3117
3118 static void route_graph_clone_segment(struct route_graph *this, struct route_graph_segment *s, struct route_graph_point *start, struct route_graph_point *end, int flags)
3119 {
3120 // dbg(0, "enter\n");
3121
3122 struct route_graph_segment_data data;
3123 data.flags = s->data.flags | flags;
3124 data.offset = 1;
3125 data.maxspeed = -1;
3126 data.item = &s->data.item;
3127 data.len = s->data.len + 1;
3128 if (s->data.flags & AF_SPEED_LIMIT)
3129 data.maxspeed = RSD_MAXSPEED(&s->data);
3130 if (s->data.flags & AF_SEGMENTED)
3131 data.offset = RSD_OFFSET(&s->data);
3132 //dbg(1, "cloning segment from %p (0x%x,0x%x) to %p (0x%x,0x%x)\n", start,
3133 // start->c.x, start->c.y, end, end->c.x, end->c.y);
3134 route_graph_add_segment(this, start, end, &data);
3135 }
3136
3137 static void route_graph_process_restriction_segment(struct route_graph *this, struct route_graph_point *p, struct route_graph_segment *s, int dir)
3138 {
3139 // dbg(0, "enter\n");
3140
3141 struct route_graph_segment *tmp;
3142 struct route_graph_point *pn;
3143 struct coord c = p->c;
3144 int dx = 0;
3145 int dy = 0;
3146 c.x += dx;
3147 c.y += dy;
3148 //dbg(1, "From %s %d,%d\n", item_to_name(s->data.item.type), dx, dy);
3149 pn = route_graph_point_new(this, &c);
3150 if (dir > 0)
3151 { /* going away */
3152 //dbg(1, "other 0x%x,0x%x\n", s->end->c.x, s->end->c.y);
3153 if (s->data.flags & AF_ONEWAY)
3154 {
3155 //dbg(1, "Not possible\n");
3156 return;
3157 }
3158 route_graph_clone_segment(this, s, pn, s->end, AF_ONEWAYREV);
3159 }
3160 else
3161 { /* coming in */
3162 //dbg(1, "other 0x%x,0x%x\n", s->start->c.x, s->start->c.y);
3163 if (s->data.flags & AF_ONEWAYREV)
3164 {
3165 //dbg(1, "Not possible\n");
3166 return;
3167 }
3168 route_graph_clone_segment(this, s, s->start, pn, AF_ONEWAY);
3169 }
3170
3171 tmp = p->start;
3172 while (tmp)
3173 {
3174 if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only && !(tmp->data.flags & AF_ONEWAYREV) && is_turn_allowed(p, s, tmp))
3175 {
3176 route_graph_clone_segment(this, tmp, pn, tmp->end, AF_ONEWAY);
3177 //dbg(1, "To start %s\n", item_to_name(tmp->data.item.type));
3178 }
3179 tmp = tmp->start_next;
3180 }
3181
3182 tmp = p->end;
3183 while (tmp)
3184 {
3185 if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only && !(tmp->data.flags & AF_ONEWAY) && is_turn_allowed(p, s, tmp))
3186 {
3187 route_graph_clone_segment(this, tmp, tmp->start, pn, AF_ONEWAYREV);
3188 //dbg(1, "To end %s\n", item_to_name(tmp->data.item.type));
3189 }
3190 tmp = tmp->end_next;
3191 }
3192 }
3193
3194 // -- UNUSED --
3195 // -- UNUSED --
3196 static void route_graph_process_traffic_light_segment(struct route_graph *this, struct route_graph_point *p, struct route_graph_segment *s, int dir)
3197 {
3198 //struct route_graph_segment *tmp;
3199 //s->data.len = s->data.len + global_traffic_light_delay;
3200 }
3201
3202
3203 static void route_graph_process_restriction_point(struct route_graph *this, struct route_graph_point *p)
3204 {
3205 // dbg(0, "enter\n");
3206
3207 struct route_graph_segment *tmp;
3208
3209 // -------------------------------------------------------------
3210 // p->start ==> a list of all streets that start from this point
3211 // -------------------------------------------------------------
3212 tmp = p->start;
3213 //dbg(1, "node 0x%x,0x%x\n", p->c.x, p->c.y);
3214 while (tmp)
3215 {
3216 if (tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only)
3217 {
3218 route_graph_process_restriction_segment(this, p, tmp, 1);
3219 }
3220 tmp = tmp->start_next;
3221 }
3222
3223 // -------------------------------------------------------------
3224 // p->end ==> a list of all streets that end at this point
3225 // -------------------------------------------------------------
3226 tmp = p->end;
3227 while (tmp)
3228 {
3229 if (tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only)
3230 {
3231 route_graph_process_restriction_segment(this, p, tmp, -1);
3232 }
3233 tmp = tmp->end_next;
3234 }
3235
3236 p->flags |= RP_TURN_RESTRICTION_RESOLVED;
3237 }
3238
3239 // -- UNUSED --
3240 // -- UNUSED --
3241 static void route_graph_process_traffic_light_point(struct route_graph *this, struct route_graph_point *p)
3242 {
3243 // dbg(0, "enter\n");
3244
3245 struct route_graph_segment *tmp;
3246
3247 // -------------------------------------------------------------
3248 // p->start ==> a list of all streets that start from this point
3249 // -------------------------------------------------------------
3250 tmp = p->start;
3251 while (tmp)
3252 {
3253 route_graph_process_traffic_light_segment(this, p, tmp, 1);
3254 tmp = tmp->start_next;
3255 }
3256
3257 // -------------------------------------------------------------
3258 // p->end ==> a list of all streets that end at this point
3259 // -------------------------------------------------------------
3260 tmp = p->end;
3261 while (tmp)
3262 {
3263 route_graph_process_traffic_light_segment(this, p, tmp, -1);
3264 tmp = tmp->end_next;
3265 }
3266
3267 // p->flags |= RP_TRAFFIC_LIGHT_RESOLVED;
3268 }
3269
3270
3271 static void route_graph_process_restrictions(struct route_graph *this)
3272 {
3273 // dbg(0, "enter\n");
3274
3275 struct route_graph_point *curr;
3276 int i;
3277 //dbg(1, "enter\n");
3278 for (i = 0; i < HASH_SIZE; i++)
3279 {
3280 curr = this->hash[i];
3281 while (curr)
3282 {
3283 if (curr->flags & RP_TURN_RESTRICTION)
3284 {
3285 route_graph_process_restriction_point(this, curr);
3286 }
3287 curr = curr->hash_next;
3288 }
3289 }
3290 }
3291
3292 // -- UNUSED --
3293 // -- UNUSED --
3294 static void route_graph_process_traffic_lights(struct route_graph *this)
3295 {
3296 // dbg(0, "enter\n");
3297
3298 // check if we should calc delay for traffic lights?
3299 if (global_traffic_light_delay > 0)
3300 {
3301 struct route_graph_point *curr;
3302 int i;
3303 //dbg(1, "enter\n");
3304 for (i = 0; i < HASH_SIZE; i++)
3305 {
3306 curr = this->hash[i];
3307 while (curr)
3308 {
3309 if (curr->flags & RP_TRAFFIC_LIGHT)
3310 {
3311 route_graph_process_traffic_light_point(this, curr);
3312 }
3313 curr = curr->hash_next;
3314 }
3315 }
3316 }
3317 }
3318
3319
3320 static void route_graph_build_done(struct route_graph *rg, int cancel)
3321 {
3322 //dbg(0, "enter\n");
3323
3324 //dbg(1, "cancel=%d\n", cancel);
3325 if (rg->idle_ev)
3326 {
3327 event_remove_idle(rg->idle_ev);
3328 rg->idle_ev = NULL;
3329 }
3330
3331 if (rg->idle_cb)
3332 {
3333 callback_destroy(rg->idle_cb);
3334 rg->idle_cb = NULL;
3335 }
3336
3337 map_rect_destroy(rg->mr);
3338 mapset_close(rg->h);
3339 route_free_selection(rg->sel);
3340 rg->mr = NULL;
3341 rg->h = NULL;
3342 rg->sel = NULL;
3343
3344 if (!cancel)
3345 {
3346 route_graph_process_restrictions(rg);
3347 // --unused-- route_graph_process_traffic_lights(rg);
3348 //dbg(0, "callback\n");
3349 callback_call_0(rg->done_cb);
3350 }
3351
3352 rg->busy = 0;
3353 }
3354
3355 // this function gets called in a loop until route is ready ----------
3356 // this function gets called in a loop until route is ready ----------
3357 // this function gets called in a loop until route is ready ----------
3358 static void route_graph_build_idle(struct route_graph *rg, struct vehicleprofile *profile)
3359 {
3360 //dbg(0, "enter\n");
3361
3362 #ifdef DEBUG_GLIB_MEM_FUNCTIONS
3363 g_mem_profile();
3364 #endif
3365
3366 // int count = 1000; // *ORIG* value
3367 int count = 5000; // process 5000 items in one step
3368 //int count = 15000; // process 15000 items in one step
3369 struct item *item;
3370
3371 while (count > 0)
3372 {
3373 // loop until an item is found ---------
3374 for (;;)
3375 {
3376 item = map_rect_get_item(rg->mr);
3377 if (item)
3378 {
3379 break;
3380 }
3381
3382 if (!route_graph_build_next_map(rg))
3383 {
3384 route_graph_build_done(rg, 0);
3385 return;
3386 }
3387 }
3388 // loop until an item is found ---------
3389
3390
3391 if (item->type == type_traffic_distortion)
3392 {
3393 route_process_traffic_distortion(rg, item);
3394 }
3395 /*
3396 else if (
3397 (item->type == type_street_2_city) ||
3398 (item->type == type_street_3_city) ||
3399 (item->type == type_street_4_city) ||
3400 (item->type == type_highway_city) ||
3401 (item->type == type_street_1_land) ||
3402 (item->type == type_street_2_land) ||
3403 (item->type == type_street_3_land) ||
3404 (item->type == type_street_4_land) ||
3405 (item->type == type_street_n_lanes) ||
3406 (item->type == type_highway_land) ||
3407 (item->type == type_ramp) ||
3408 )
3409 {
3410 */
3411 /*
3412 ITEM(street_0)
3413 ITEM(street_1_city)
3414 ITEM(street_2_city)
3415 ITEM(street_3_city)
3416 ITEM(street_4_city)
3417 ITEM(highway_city)
3418 ITEM(street_1_land)
3419 ITEM(street_2_land)
3420 ITEM(street_3_land)
3421 ITEM(street_4_land)
3422 ITEM(street_n_lanes)
3423 ITEM(highway_land)
3424 ITEM(ramp)
3425 */
3426 // route_process_sharp_turn(rg, item);
3427 // }
3428 else if (item->type == type_traffic_signals)
3429 {
3430 route_process_traffic_light(rg, item);
3431 }
3432 else if (item->type == type_street_turn_restriction_no || item->type == type_street_turn_restriction_only)
3433 {
3434 route_process_turn_restriction(rg, item);
3435 }
3436 else
3437 {
3438 //dbg(0,"*[xx]type=%s\n", item_to_name(item->type));
3439 route_process_street_graph(rg, item, profile);
3440 }
3441
3442 count--;
3443 }
3444
3445 //dbg(0,"leave\n");
3446 }
3447
3448 /**
3449 * @brief Builds a new route graph from a mapset
3450 *
3451 * This function builds a new route graph from a map. Please note that this function does not
3452 * add any routing information to the route graph - this has to be done via the route_graph_flood()
3453 * function.
3454 *
3455 * The function does not create a graph covering the whole map, but only covering the rectangle
3456 * between c1 and c2.
3457 *
3458 * @param ms The mapset to build the route graph from
3459 * @param c1 Corner 1 of the rectangle to use from the map
3460 * @param c2 Corner 2 of the rectangle to use from the map
3461 * @param done_cb The callback which will be called when graph is complete
3462 * @return The new route graph.
3463 */
3464 static struct route_graph *
3465 route_graph_build(struct mapset *ms, struct coord *c, int count, struct callback *done_cb, int async, struct vehicleprofile *profile, int try_harder)
3466 {
3467 //dbg(0, "enter\n");
3468
3469 struct route_graph *ret=g_new0(struct route_graph, 1);
3470
3471 ret->sel = route_calc_selection(c, count, try_harder);
3472
3473 ret->h = mapset_open(ms);
3474 ret->done_cb = done_cb;
3475 ret->busy = 1;
3476
3477 if (route_graph_build_next_map(ret))
3478 {
3479 // ------ xxxxxx ----
3480 // dbg(0,"async=%d\n", async);
3481 if (async)
3482 {
3483 //dbg(0,"route_graph_build_idle sync callback\n");
3484 ret->idle_cb = callback_new_2(callback_cast(route_graph_build_idle), ret, profile);
3485 callback_add_names(ret->idle_cb, "route_graph_build", "route_graph_build_idle");
3486 ret->idle_ev = event_add_idle(10, ret->idle_cb);
3487 }
3488 else
3489 {
3490 // ?? do we need this ?? // route_graph_build_idle(ret, profile);
3491 }
3492 }
3493 else
3494 {
3495 route_graph_build_done(ret, 0);
3496 }
3497
3498 return ret;
3499 }
3500
3501 static void route_graph_update_done(struct route *this, struct callback *cb)
3502 {
3503 //dbg(0, "enter\n");
3504 route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, cb);
3505 }
3506
3507 /**
3508 * @brief Updates the route graph
3509 *
3510 * This updates the route graph after settings in the route have changed. It also
3511 * adds routing information afterwards by calling route_graph_flood().
3512 *
3513 * @param this The route to update the graph for
3514 */
3515 static void route_graph_update(struct route *this, struct callback *cb, int async)
3516 {
3517 //dbg(0, "enter\n");
3518
3519 struct attr route_status;
3520 struct coord *c = g_alloca(sizeof(struct coord) * (1 + g_list_length(this->destinations)));
3521 int i = 0;
3522 GList *tmp;
3523
3524 route_status.type = attr_route_status;
3525 route_graph_destroy(this->graph);
3526 this->graph = NULL;
3527 callback_destroy(this->route_graph_done_cb);
3528
3529 this->route_graph_done_cb = callback_new_2(callback_cast(route_graph_update_done), this, cb);
3530 callback_add_names(this->route_graph_done_cb, "route_graph_update", "route_graph_update_done");
3531
3532 route_status.u.num = route_status_building_graph;
3533 route_set_attr(this, &route_status);
3534 c[i++] = this->pos->c;
3535 tmp = this->destinations;
3536 while (tmp)
3537 {
3538 struct route_info *dst = tmp->data;
3539 c[i++] = dst->c;
3540 tmp = g_list_next(tmp);
3541 }
3542
3543 this->graph = route_graph_build(this->ms, c, i, this->route_graph_done_cb, async, this->vehicleprofile, this->try_harder);
3544
3545 if (!async)
3546 {
3547 while (this->graph->busy)
3548 {
3549 route_graph_build_idle(this->graph, this->vehicleprofile);
3550 }
3551 }
3552
3553 //dbg(0,"leave\n");
3554 }
3555
3556 /**
3557 * @brief Gets street data for an item
3558 *
3559 * @param item The item to get the data for
3560 * @return Street data for the item
3561 */
3562 struct street_data *
3563 street_get_data(struct item *item)
3564 {
3565 //// dbg(0, "enter\n");
3566
3567 int count = 0, *flags;
3568 struct street_data *ret = NULL, *ret1;
3569 struct attr flags_attr, maxspeed_attr;
3570 const int step = 128;
3571 int c;
3572
3573 do
3574 {
3575 ret1 = g_realloc(ret, sizeof(struct street_data) + (count + step) * sizeof(struct coord));
3576 if (!ret1)
3577 {
3578 if (ret)
3579 g_free(ret);
3580 return NULL;
3581 }
3582 ret = ret1;
3583 c = item_coord_get(item, &ret->c[count], step);
3584 count += c;
3585 }
3586 while (c && c == step);
3587
3588 ret1 = g_realloc(ret, sizeof(struct street_data) + count * sizeof(struct coord));
3589 if (ret1)
3590 ret = ret1;
3591 ret->item = *item;
3592 ret->count = count;
3593 if (item_attr_get(item, attr_flags, &flags_attr))
3594 ret->flags = flags_attr.u.num;
3595 else
3596 {
3597 flags = item_get_default_flags(item->type);
3598 if (flags)
3599 ret->flags = *flags;
3600 else
3601 ret->flags = 0;
3602 }
3603
3604 ret->maxspeed = -1;
3605 if (ret->flags & AF_SPEED_LIMIT)
3606 {
3607 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr))
3608 {
3609 ret->maxspeed = maxspeed_attr.u.num;
3610 }
3611 }
3612
3613 return ret;
3614 }
3615
3616 /**
3617 * @brief Copies street data
3618 *
3619 * @param orig The street data to copy
3620 * @return The copied street data
3621 */
3622 struct street_data *
3623 street_data_dup(struct street_data *orig)
3624 {
3625 //// dbg(0, "enter\n");
3626
3627 struct street_data *ret;
3628 int size = sizeof(struct street_data) + orig->count * sizeof(struct coord);
3629
3630 ret = g_malloc(size);
3631 // xxx global_route_memory_size = global_route_memory_size + seg_size + seg_dat_size;
3632 // xxx dbg(0,"route mem=%lu\n", global_route_memory_size);
3633 memcpy(ret, orig, size);
3634
3635 return ret;
3636 }
3637
3638 /**
3639 * @brief Frees street data
3640 *
3641 * @param sd Street data to be freed
3642 */
3643 void street_data_free(struct street_data *sd)
3644 {
3645 //// dbg(0, "enter\n");
3646
3647 g_free(sd);
3648 }
3649
3650 /**
3651 * @brief Finds the nearest street to a given coordinate (result should be a road that is in vehicle profile for routing!)
3652 *
3653 * @param ms The mapset to search in for the street
3654 * @param pc The coordinate to find a street nearby
3655 * @return The nearest street
3656 */
3657 static struct route_info *
3658 route_find_nearest_street(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc)
3659 {
3660 //dbg(0, "enter\n");
3661
3662 struct route_info *ret = NULL;
3663 int max_dist = 1000; // was 1000 originally!!
3664 struct map_selection *sel;
3665 int dist, mindist = 0, pos;
3666 struct mapset_handle *h;
3667 struct map *m;
3668 struct map_rect *mr;
3669 struct item *item;
3670 struct coord lp;
3671 struct street_data *sd;
3672 struct coord c;
3673 struct coord_geo g;
3674
3675 ret=g_new0(struct route_info, 1);
3676 mindist = INT_MAX;
3677
3678 h = mapset_open(ms);
3679 while ((m = mapset_next(h, 2)))
3680 {
3681 c.x = pc->x;
3682 c.y = pc->y;
3683
3684 if (map_projection(m) != pc->pro)
3685 {
3686 transform_to_geo(pc->pro, &c, &g);
3687 transform_from_geo(map_projection(m), &g, &c);
3688 }
3689
3690 sel = route_rect(18, &c, &c, 0, max_dist);
3691
3692 if (!sel)
3693 {
3694 continue;
3695 }
3696
3697 mr = map_rect_new(m, sel);
3698 //dbg(0, "sel lu=%d,%d rl=%d,%d\n", sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y);
3699
3700 if (!mr)
3701 {
3702 map_selection_destroy(sel);
3703 continue;
3704 }
3705
3706 while ((item = map_rect_get_item(mr)))
3707 {
3708 if (item_get_default_flags(item->type))
3709 {
3710 sd = street_get_data(item);
3711 if (!sd)
3712 {
3713 continue;
3714 }
3715
3716 //dbg(0,"*type=%s\n", item_to_name(item->type));
3717
3718 dist = transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
3719
3720 if (dist < mindist && ((sd->flags & vehicleprofile->flags_forward_mask) == vehicleprofile->flags || (sd->flags & vehicleprofile->flags_reverse_mask) == vehicleprofile->flags))
3721 {
3722 mindist = dist;
3723 if (ret->street)
3724 {
3725 street_data_free(ret->street);
3726 }
3727 ret->c = c;
3728 ret->lp = lp;
3729 ret->pos = pos;
3730 ret->street = sd;
3731
3732 //dbg(0,"*(N)type=%s\n", item_to_name(item->type));
3733 /*
3734 struct attr street_name_attr;
3735 if (item_attr_get(item, attr_label, &street_name_attr))
3736 {
3737 dbg(0, "*name=%s\n", street_name_attr.u.str);
3738 }
3739 else if (item_attr_get(item, attr_street_name, &street_name_attr))
3740 {
3741 dbg(0, "*name=%s\n", street_name_attr.u.str);
3742 }
3743 */
3744 //dbg(0, "dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
3745 }
3746 else
3747 {
3748 street_data_free(sd);
3749 }
3750 }
3751 }
3752 map_selection_destroy(sel);
3753 map_rect_destroy(mr);
3754 }
3755 mapset_close(h);
3756
3757 if (!ret->street || mindist > max_dist * max_dist)
3758 {
3759 if (ret->street)
3760 {
3761 street_data_free(ret->street);
3762 //dbg(0, "Much too far %d > %d\n", mindist, max_dist);
3763 }
3764
3765 //dbg(0,"return NULL\n");
3766
3767 g_free(ret);
3768 ret = NULL;
3769 }
3770
3771 return ret;
3772 }
3773
3774
3775
3776 static struct route_info *
3777 route_find_nearest_street_harder(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc, int max_dist_wanted)
3778 {
3779 //dbg(0, "enter %d\n", max_dist_wanted);
3780
3781 struct route_info *ret = NULL;
3782 int max_dist = max_dist_wanted; // was 1000 originally!!
3783 struct map_selection *sel;
3784 int dist, mindist = 0, pos;
3785 struct mapset_handle *h;
3786 struct map *m;
3787 struct map_rect *mr;
3788 struct item *item;
3789 struct coord lp;
3790 struct street_data *sd;
3791 struct coord c;
3792 struct coord_geo g;
3793
3794 ret=g_new0(struct route_info, 1);
3795 mindist = INT_MAX;
3796
3797 h = mapset_open(ms);
3798 while ((m = mapset_next(h, 2)))
3799 {
3800 c.x = pc->x;
3801 c.y = pc->y;
3802
3803 if (map_projection(m) != pc->pro)
3804 {
3805 transform_to_geo(pc->pro, &c, &g);
3806 transform_from_geo(map_projection(m), &g, &c);
3807 }
3808
3809 sel = route_rect(18, &c, &c, 0, max_dist);
3810
3811 if (!sel)
3812 {
3813 continue;
3814 }
3815
3816 //dbg(0, "sel lu=%d,%d rl=%d,%d\n", sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y);
3817
3818 mr = map_rect_new(m, sel);
3819
3820 if (!mr)
3821 {
3822 map_selection_destroy(sel);
3823 continue;
3824 }
3825
3826 while ((item = map_rect_get_item(mr)))
3827 {
3828 if (item_get_default_flags(item->type))
3829 {
3830 sd = street_get_data(item);
3831 if (!sd)
3832 {
3833 continue;
3834 }
3835
3836 //dbg(0,"*type=%s\n", item_to_name(item->type));
3837
3838 dist = transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
3839
3840 if (dist < mindist && ((sd->flags & vehicleprofile->flags_forward_mask) == vehicleprofile->flags || (sd->flags & vehicleprofile->flags_reverse_mask) == vehicleprofile->flags))
3841 {
3842 mindist = dist;
3843 if (ret->street)
3844 {
3845 street_data_free(ret->street);
3846 }
3847 ret->c = c;
3848 ret->lp = lp;
3849 ret->pos = pos;
3850 ret->street = sd;
3851
3852 /*
3853 dbg(0,"*(h)type=%s\n", item_to_name(item->type));
3854 struct attr street_name_attr;
3855 if (item_attr_get(item, attr_label, &street_name_attr))
3856 {
3857 dbg(0, "*name=%s\n", street_name_attr.u.str);
3858 }
3859 else if (item_attr_get(item, attr_street_name, &street_name_attr))
3860 {
3861 dbg(0, "*name=%s\n", street_name_attr.u.str);
3862 }
3863 */
3864 //dbg(0, "dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
3865 }
3866 else
3867 {
3868 street_data_free(sd);
3869 }
3870 }
3871 }
3872 map_selection_destroy(sel);
3873 map_rect_destroy(mr);
3874 }
3875 mapset_close(h);
3876
3877 if (!ret->street || mindist > (max_dist * max_dist))
3878 {
3879
3880 //dbg(0,"no street found!\n");
3881
3882 if (ret->street)
3883 {
3884 street_data_free(ret->street);
3885 //dbg(0, "Much too far %d > %d\n", mindist, max_dist);
3886 }
3887 g_free(ret);
3888 ret = NULL;
3889 }
3890
3891 return ret;
3892 }
3893
3894
3895 /**
3896 * @brief Destroys a route_info
3897 *
3898 * @param info The route info to be destroyed
3899 */
3900 void route_info_free(struct route_info *inf)
3901 {
3902 //// dbg(0, "enter\n");
3903
3904 if (!inf)
3905 return;
3906 if (inf->street)
3907 street_data_free(inf->street);
3908 g_free(inf);
3909 }
3910
3911 #include "point.h"
3912
3913 /**
3914 * @brief Returns street data for a route info
3915 *
3916 * @param rinf The route info to return the street data for
3917 * @return Street data for the route info
3918 */
3919 struct street_data *
3920 route_info_street(struct route_info *rinf)
3921 {
3922 // dbg(0, "enter\n");
3923
3924 return rinf->street;
3925 }
3926
3927 #if 0
3928 struct route_crossings *
3929 route_crossings_get(struct route *this, struct coord *c)
3930 {
3931 struct route_point *pnt;
3932 struct route_segment *seg;
3933 int crossings=0;
3934 struct route_crossings *ret;
3935
3936 pnt=route_graph_get_point(this, c);
3937 seg=pnt->start;
3938 while (seg)
3939 {
3940 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
3941 crossings++;
3942 seg=seg->start_next;
3943 }
3944 seg=pnt->end;
3945 while (seg)
3946 {
3947 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
3948 crossings++;
3949 seg=seg->end_next;
3950 }
3951 ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
3952 ret->count=crossings;
3953 return ret;
3954 }
3955 #endif
3956
3957 struct map_rect_priv
3958 {
3959 struct route_info_handle *ri;
3960 enum attr_type attr_next;
3961 int pos;
3962 struct map_priv *mpriv;
3963 struct item item;
3964 unsigned int last_coord;
3965 struct route_path *path;
3966 struct route_path_segment *seg, *seg_next;
3967 struct route_graph_point *point;
3968 struct route_graph_segment *rseg;
3969 char *str;
3970 int hash_bucket;
3971 struct coord *coord_sel; /**< Set this to a coordinate if you want to filter for just a single route graph point */
3972 struct route_graph_point_iterator it;
3973 };
3974
3975 static void rm_coord_rewind(void *priv_data)
3976 {
3977 //// dbg(0, "enter\n");
3978
3979 struct map_rect_priv *mr = priv_data;
3980 mr->last_coord = 0;
3981 }
3982
3983 static void rm_attr_rewind(void *priv_data)
3984 {
3985 //// dbg(0, "enter\n");
3986
3987 struct map_rect_priv *mr = priv_data;
3988 mr->attr_next = attr_street_item;
3989 }
3990
3991 static int rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
3992 {
3993 //// dbg(0, "enter\n");
3994
3995 struct map_rect_priv *mr = priv_data;
3996 struct route_path_segment *seg = mr->seg;
3997 struct route *route = mr->mpriv->route;
3998 if (mr->item.type != type_street_route)
3999 return 0;
4000 attr->type = attr_type;
4001 switch (attr_type)
4002 {
4003 case attr_any:
4004 while (mr->attr_next != attr_none)
4005 {
4006 if (rm_attr_get(priv_data, mr->attr_next, attr))
4007 return 1;
4008 }
4009 return 0;
4010 case attr_maxspeed:
4011 mr->attr_next = attr_street_item;
4012 if (seg && seg->data->flags & AF_SPEED_LIMIT)
4013 {
4014 attr->u.num = RSD_MAXSPEED(seg->data);
4015
4016 }
4017 else
4018 {
4019 return 0;
4020 }
4021 return 1;
4022 case attr_street_item:
4023 mr->attr_next = attr_direction;
4024 if (seg && seg->data->item.map)
4025 attr->u.item = &seg->data->item;
4026 else
4027 return 0;
4028 return 1;
4029 case attr_direction:
4030 mr->attr_next = attr_route;
4031 if (seg)
4032 attr->u.num = seg->direction;
4033 else
4034 return 0;
4035 return 1;
4036 case attr_route:
4037 mr->attr_next = attr_length;
4038 attr->u.route = mr->mpriv->route;
4039 return 1;
4040 case attr_length:
4041 mr->attr_next = attr_time;
4042 if (seg)
4043 attr->u.num = seg->data->len;
4044 else
4045 return 0;
4046 return 1;
4047 case attr_time:
4048 mr->attr_next = attr_speed;
4049 if (seg)
4050 attr->u.num = route_time_seg(route->vehicleprofile, seg->data, NULL);
4051 else
4052 return 0;
4053 return 1;
4054 case attr_speed:
4055 mr->attr_next = attr_none;
4056 if (seg)
4057 attr->u.num = route_seg_speed(route->vehicleprofile, seg->data, NULL);
4058 else
4059 return 0;
4060 return 1;
4061 case attr_label:
4062 mr->attr_next = attr_none;
4063 return 0;
4064 default:
4065 mr->attr_next = attr_none;
4066 attr->type = attr_none;
4067 return 0;
4068 }
4069 return 0;
4070 }
4071
4072 static int rm_coord_get(void *priv_data, struct coord *c, int count)
4073 {
4074 //// dbg(0, "enter\n");
4075
4076 struct map_rect_priv *mr = priv_data;
4077 struct route_path_segment *seg = mr->seg;
4078 int i, rc = 0;
4079 struct route *r = mr->mpriv->route;
4080 enum projection pro = route_projection(r);
4081
4082 if (pro == projection_none)
4083 return 0;
4084 if (mr->item.type == type_route_start || mr->item.type == type_route_start_reverse || mr->item.type == type_route_end)
4085 {
4086 if (!count || mr->last_coord)
4087 return 0;
4088 mr->last_coord = 1;
4089 if (mr->item.type == type_route_start || mr->item.type == type_route_start_reverse)
4090 c[0] = r->pos->c;
4091 else
4092 {
4093 c[0] = route_get_dst(r)->c;
4094 }
4095 return 1;
4096 }
4097 if (!seg)
4098 return 0;
4099 for (i = 0; i < count; i++)
4100 {
4101 if (mr->last_coord >= seg->ncoords)
4102 break;
4103 if (i >= seg->ncoords)
4104 break;
4105 if (pro != projection_mg)
4106 transform_from_to(&seg->c[mr->last_coord++], pro, &c[i], projection_mg);
4107 else
4108 c[i] = seg->c[mr->last_coord++];
4109 rc++;
4110 }
4111 //dbg(1, "return %d\n", rc);
4112 return rc;
4113 }
4114
4115 static struct item_methods methods_route_item = { rm_coord_rewind, rm_coord_get, rm_attr_rewind, rm_attr_get, };
4116
4117 static void rp_attr_rewind(void *priv_data)
4118 {
4119 //// dbg(0, "enter\n");
4120
4121 struct map_rect_priv *mr = priv_data;
4122 mr->attr_next = attr_label;
4123 }
4124
4125 static int rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
4126 {
4127 //// dbg(0, "enter\n");
4128
4129 struct map_rect_priv *mr = priv_data;
4130 struct route_graph_point *p = mr->point;
4131 struct route_graph_segment *seg = mr->rseg;
4132 struct route *route = mr->mpriv->route;
4133
4134 attr->type = attr_type;
4135 switch (attr_type)
4136 {
4137 case attr_any: // works only with rg_points for now
4138 while (mr->attr_next != attr_none)
4139 {
4140 //dbg(0, "querying %s\n", attr_to_name(mr->attr_next));
4141 if (rp_attr_get(priv_data, mr->attr_next, attr))
4142 return 1;
4143 }
4144 return 0;
4145 case attr_maxspeed:
4146 mr->attr_next = attr_label;
4147 if (mr->item.type != type_rg_segment)
4148 return 0;
4149 if (seg && (seg->data.flags & AF_SPEED_LIMIT))
4150 {
4151 attr->type = attr_maxspeed;
4152 attr->u.num = RSD_MAXSPEED(&seg->data);
4153 return 1;
4154 }
4155 else
4156 {
4157 return 0;
4158 }
4159 case attr_label:
4160 mr->attr_next = attr_street_item;
4161 if (mr->item.type != type_rg_point)
4162 return 0;
4163 attr->type = attr_label;
4164 if (mr->str)
4165 g_free(mr->str);
4166 if (p->value != INT_MAX)
4167 mr->str = g_strdup_printf("%d", p->value);
4168 else
4169 mr->str = g_strdup("-");
4170 attr->u.str = mr->str;
4171 return 1;
4172 case attr_street_item:
4173 mr->attr_next = attr_flags;
4174 if (mr->item.type != type_rg_segment)
4175 return 0;
4176 if (seg && seg->data.item.map)
4177 attr->u.item = &seg->data.item;
4178 else
4179 return 0;
4180 return 1;
4181 case attr_flags:
4182 mr->attr_next = attr_direction;
4183 if (mr->item.type != type_rg_segment)
4184 return 0;
4185 if (seg)
4186 {
4187 attr->u.num = seg->data.flags;
4188 }
4189 else
4190 {
4191 return 0;
4192 }
4193 return 1;
4194 case attr_direction:
4195 mr->attr_next = attr_debug;
4196 // This only works if the map has been opened at a single point, and in that case indicates if the
4197 // segment returned last is connected to this point via its start (1) or its end (-1)
4198 if (!mr->coord_sel || (mr->item.type != type_rg_segment))
4199 return 0;
4200 if (seg->start == mr->point)
4201 {
4202 attr->u.num = 1;
4203 }
4204 else if (seg->end == mr->point)
4205 {
4206 attr->u.num = -1;
4207 }
4208 else
4209 {
4210 return 0;
4211 }
4212 return 1;
4213 case attr_debug:
4214 mr->attr_next = attr_none;
4215 if (mr->str)
4216 g_free(mr->str);
4217 switch (mr->item.type)
4218 {
4219 case type_rg_point:
4220 {
4221 struct route_graph_segment *tmp;
4222 int start = 0;
4223 int end = 0;
4224 tmp = p->start;
4225 while (tmp)
4226 {
4227 start++;
4228 tmp = tmp->start_next;
4229 }
4230 tmp = p->end;
4231 while (tmp)
4232 {
4233 end++;
4234 tmp = tmp->end_next;
4235 }
4236 mr->str = g_strdup_printf("%d %d %p (0x%x,0x%x)", start, end, p, p->c.x, p->c.y);
4237 attr->u.str = mr->str;
4238 }
4239 return 1;
4240 case type_rg_segment:
4241 if (!seg)
4242 return 0;
4243 mr->str = g_strdup_printf("len %d time %d start %p end %p", seg->data.len, route_time_seg(route->vehicleprofile, &seg->data, NULL), seg->start, seg->end);
4244 attr->u.str = mr->str;
4245 return 1;
4246 default:
4247 return 0;
4248 }
4249 default:
4250 mr->attr_next = attr_none;
4251 attr->type = attr_none;
4252 return 0;
4253 }
4254 }
4255
4256 /**
4257 * @brief Returns the coordinates of a route graph item
4258 *
4259 * @param priv_data The route graph item's private data
4260 * @param c Pointer where to store the coordinates
4261 * @param count How many coordinates to get at a max?
4262 * @return The number of coordinates retrieved
4263 */
4264 static int rp_coord_get(void *priv_data, struct coord *c, int count)
4265 {
4266 //// dbg(0, "enter\n");
4267
4268 struct map_rect_priv *mr = priv_data;
4269 struct route_graph_point *p = mr->point;
4270 struct route_graph_segment *seg = mr->rseg;
4271 int rc = 0, i, dir;
4272 struct route *r = mr->mpriv->route;
4273 enum projection pro = route_projection(r);
4274
4275 if (pro == projection_none)
4276 {
4277 return 0;
4278 }
4279
4280 for (i = 0; i < count; i++)
4281 {
4282 if (mr->item.type == type_rg_point)
4283 {
4284 if (mr->last_coord >= 1)
4285 break;
4286 if (pro != projection_mg)
4287 transform_from_to(&p->c, pro, &c[i], projection_mg);
4288 else
4289 c[i] = p->c;
4290 }
4291 else
4292 {
4293 if (mr->last_coord >= 2)
4294 break;
4295 dir = 0;
4296 if (seg->end->seg == seg)
4297 dir = 1;
4298 if (mr->last_coord)
4299 dir = 1 - dir;
4300 if (dir)
4301 {
4302 if (pro != projection_mg)
4303 transform_from_to(&seg->end->c, pro, &c[i], projection_mg);
4304 else
4305 c[i] = seg->end->c;
4306 }
4307 else
4308 {
4309 if (pro != projection_mg)
4310 transform_from_to(&seg->start->c, pro, &c[i], projection_mg);
4311 else
4312 c[i] = seg->start->c;
4313 }
4314 }
4315 mr->last_coord++;
4316 rc++;
4317 }
4318 return rc;
4319 }
4320
4321 static struct item_methods methods_point_item = { rm_coord_rewind, rp_coord_get, rp_attr_rewind, rp_attr_get, };
4322
4323 static void rp_destroy(struct map_priv *priv)
4324 {
4325 //// dbg(0, "enter\n");
4326
4327 g_free(priv);
4328 }
4329
4330 static void rm_destroy(struct map_priv *priv)
4331 {
4332 //// dbg(0, "enter\n");
4333
4334 g_free(priv);
4335 }
4336
4337 static struct map_rect_priv *
4338 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
4339 {
4340 //// dbg(0, "enter\n");
4341
4342 struct map_rect_priv * mr;
4343 //dbg(1, "enter\n");
4344
4345 #if 0
4346 if (! route_get_pos(priv->route))
4347 return NULL;
4348 if (! route_get_dst(priv->route))
4349 return NULL;
4350 #endif
4351
4352 #if 0
4353 if (! priv->route->path2)
4354 return NULL;
4355 #endif
4356
4357 mr=g_new0(struct map_rect_priv, 1);
4358 mr->mpriv = priv;
4359 mr->item.priv_data = mr;
4360 mr->item.type = type_none;
4361 mr->item.meth = &methods_route_item;
4362 if (priv->route->path2)
4363 {
4364 mr->path = priv->route->path2;
4365 mr->seg_next = mr->path->path;
4366 mr->path->in_use++;
4367 }
4368 else
4369 mr->seg_next = NULL;
4370 return mr;
4371 }
4372
4373 /**
4374 * @brief Opens a new map rectangle on the route graph's map
4375 *
4376 * This function opens a new map rectangle on the route graph's map.
4377 * The "sel" parameter enables you to only search for a single route graph
4378 * point on this map (or exactly: open a map rectangle that only contains
4379 * this one point). To do this, pass here a single map selection, whose
4380 * c_rect has both coordinates set to the same point. Otherwise this parameter
4381 * has no effect.
4382 *
4383 * @param priv The route graph map's private data
4384 * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
4385 * @return A new map rect's private data
4386 */
4387 static struct map_rect_priv *
4388 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
4389 {
4390 //// dbg(0, "enter\n");
4391
4392 struct map_rect_priv * mr;
4393
4394 if (!priv->route->graph)
4395 {
4396 return NULL;
4397 }
4398
4399 mr=g_new0(struct map_rect_priv, 1);
4400 mr->mpriv = priv;
4401 mr->item.priv_data = mr;
4402 mr->item.type = type_rg_point;
4403 mr->item.meth = &methods_point_item;
4404
4405 if (sel)
4406 {
4407 if ((sel->u.c_rect.lu.x == sel->u.c_rect.rl.x) && (sel->u.c_rect.lu.y == sel->u.c_rect.rl.y))
4408 {
4409 mr->coord_sel = g_malloc(sizeof(struct coord));
4410 // xxx
4411 *(mr->coord_sel) = sel->u.c_rect.lu;
4412 }
4413 }
4414 return mr;
4415 }
4416
4417 static void rm_rect_destroy(struct map_rect_priv *mr)
4418 {
4419 //// dbg(0, "enter\n");
4420
4421 if (mr->str)
4422 g_free(mr->str);
4423 if (mr->coord_sel)
4424 {
4425 g_free(mr->coord_sel);
4426 }
4427 if (mr->path)
4428 {
4429 mr->path->in_use--;
4430 if (mr->path->update_required && (mr->path->in_use == 1))
4431 route_path_update_done(mr->mpriv->route, mr->path->update_required - 1);
4432 else if (!mr->path->in_use)
4433 g_free(mr->path);
4434 }
4435
4436 g_free(mr);
4437 }
4438
4439 static struct item *
4440 rp_get_item(struct map_rect_priv *mr)
4441 {
4442 //// dbg(0, "enter\n");
4443
4444 struct route *r = mr->mpriv->route;
4445 struct route_graph_point *p = mr->point;
4446 struct route_graph_segment *seg = mr->rseg;
4447
4448 if (mr->item.type == type_rg_point)
4449 {
4450 if (mr->coord_sel)
4451 {
4452 // We are supposed to return only the point at one specified coordinate...
4453 if (!p)
4454 {
4455 p = route_graph_get_point_last(r->graph, mr->coord_sel);
4456 if (!p)
4457 {
4458 mr->point = NULL; // This indicates that no point has been found
4459 }
4460 else
4461 {
4462 mr->it = rp_iterator_new(p);
4463 }
4464 }
4465 else
4466 {
4467 p = NULL;
4468 }
4469 }
4470 else
4471 {
4472 if (!p)
4473 {
4474 mr->hash_bucket = 0;
4475 p = r->graph->hash[0];
4476 }
4477 else
4478 p = p->hash_next;
4479 while (!p)
4480 {
4481 mr->hash_bucket++;
4482 if (mr->hash_bucket >= HASH_SIZE)
4483 break;
4484 p = r->graph->hash[mr->hash_bucket];
4485 }
4486 }
4487 if (p)
4488 {
4489 mr->point = p;
4490 mr->item.id_lo++;
4491 rm_coord_rewind(mr);
4492 rp_attr_rewind(mr);
4493 return &mr->item;
4494 }
4495 else
4496 mr->item.type = type_rg_segment;
4497 }
4498
4499 if (mr->coord_sel)
4500 {
4501 if (!mr->point)
4502 { // This means that no point has been found
4503 return NULL;
4504 }
4505 seg = rp_iterator_next(&(mr->it));
4506 }
4507 else
4508 {
4509 if (!seg)
4510 seg = r->graph->route_segments;
4511 else
4512 seg = seg->next;
4513 }
4514
4515 if (seg)
4516 {
4517 mr->rseg = seg;
4518 mr->item.id_lo++;
4519 rm_coord_rewind(mr);
4520 rp_attr_rewind(mr);
4521 return &mr->item;
4522 }
4523 return NULL;
4524
4525 }
4526
4527 static struct item *
4528 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
4529 {
4530 //// dbg(0, "enter\n");
4531
4532 struct item *ret = NULL;
4533 while (id_lo-- > 0)
4534 ret = rp_get_item(mr);
4535 return ret;
4536 }
4537
4538 static struct item *
4539 rm_get_item(struct map_rect_priv *mr)
4540 {
4541 //// dbg(0, "enter\n");
4542
4543 struct route *route = mr->mpriv->route;
4544
4545 switch (mr->item.type)
4546 {
4547 case type_none:
4548 if (route->pos && route->pos->street_direction && route->pos->street_direction != route->pos->dir)
4549 mr->item.type = type_route_start_reverse;
4550 else
4551 mr->item.type = type_route_start;
4552 if (route->pos)
4553 break;
4554 default:
4555 mr->item.type = type_street_route;
4556 mr->seg = mr->seg_next;
4557 if (!mr->seg && mr->path && mr->path->next)
4558 {
4559 struct route_path *p = NULL;
4560 mr->path->in_use--;
4561 if (!mr->path->in_use)
4562 p = mr->path;
4563 mr->path = mr->path->next;
4564 mr->path->in_use++;
4565 mr->seg = mr->path->path;
4566 if (p)
4567 g_free(p);
4568 }
4569 if (mr->seg)
4570 {
4571 mr->seg_next = mr->seg->next;
4572 break;
4573 }
4574 mr->item.type = type_route_end;
4575 // dbg(0,"* set route_end *\n");
4576 if (mr->mpriv->route->destinations)
4577 break;
4578 case type_route_end:
4579 return NULL;
4580 }
4581 mr->last_coord = 0;
4582 mr->item.id_lo++;
4583 rm_attr_rewind(mr);
4584 return &mr->item;
4585 }
4586
4587 static struct item *
4588 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
4589 {
4590 //// dbg(0, "enter\n");
4591
4592 struct item *ret = NULL;
4593 while (id_lo-- > 0)
4594 ret = rm_get_item(mr);
4595 return ret;
4596 }
4597
4598 static struct map_methods route_meth = { projection_mg, "utf-8", rm_destroy, rm_rect_new, rm_rect_destroy, rm_get_item, rm_get_item_byid, NULL, NULL, NULL, };
4599
4600 static struct map_methods route_graph_meth = { projection_mg, "utf-8", rp_destroy, rp_rect_new, rm_rect_destroy, rp_get_item, rp_get_item_byid, NULL, NULL, NULL, };
4601
4602 static struct map_priv *
4603 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
4604 {
4605 // dbg(0, "enter\n");
4606
4607 struct map_priv *ret;
4608 struct attr *route_attr;
4609
4610 route_attr = attr_search(attrs, NULL, attr_route);
4611 if (!route_attr)
4612 return NULL;ret=g_new0(struct map_priv, 1);
4613 if (graph)
4614 *meth = route_graph_meth;
4615 else
4616 *meth = route_meth;
4617 ret->route = route_attr->u.route;
4618
4619 return ret;
4620 }
4621
4622 static struct map_priv *
4623 route_map_new(struct map_methods *meth, struct attr **attrs, struct callback_list *cbl)
4624 {
4625 // dbg(0, "enter\n");
4626
4627 return route_map_new_helper(meth, attrs, 0);
4628 }
4629
4630 static struct map_priv *
4631 route_graph_map_new(struct map_methods *meth, struct attr **attrs, struct callback_list *cbl)
4632 {
4633 // dbg(0, "enter\n");
4634
4635 return route_map_new_helper(meth, attrs, 1);
4636 }
4637
4638 static struct map *
4639 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
4640 {
4641 //// dbg(0, "enter\n");
4642
4643 struct attr *attrs[5];
4644 struct attr a_type, navigation, data, a_description;
4645 a_type.type = attr_type;
4646 a_type.u.str = type;
4647 navigation.type = attr_route;
4648 navigation.u.route = this_;
4649 data.type = attr_data;
4650 data.u.str = "";
4651 a_description.type = attr_description;
4652 a_description.u.str = description;
4653
4654 attrs[0] = &a_type;
4655 attrs[1] = &navigation;
4656 attrs[2] = &data;
4657 attrs[3] = &a_description;
4658 attrs[4] = NULL;
4659
4660 if (!*map)
4661 {
4662 *map = map_new(NULL, attrs);
4663 map_ref(*map);
4664 }
4665
4666 return *map;
4667 }
4668
4669 /**
4670 * @brief Returns a new map containing the route path
4671 *
4672 * This function returns a new map containing the route path.
4673 *
4674 * @important Do not map_destroy() this!
4675 *
4676 * @param this_ The route to get the map of
4677 * @return A new map containing the route path
4678 */
4679 struct map *
4680 route_get_map(struct route *this_)
4681 {
4682 //// dbg(0, "enter\n");
4683
4684 return route_get_map_helper(this_, &this_->map, "route", "Route");
4685 }
4686
4687 /**
4688 * @brief Returns a new map containing the route graph
4689 *
4690 * This function returns a new map containing the route graph.
4691 *
4692 * @important Do not map_destroy() this!
4693 *
4694 * @param this_ The route to get the map of
4695 * @return A new map containing the route graph
4696 */
4697 struct map *
4698 route_get_graph_map(struct route *this_)
4699 {
4700 //// dbg(0, "enter\n");
4701
4702 return route_get_map_helper(this_, &this_->graph_map, "route_graph", "Route Graph");
4703 }
4704
4705 void route_set_projection(struct route *this_, enum projection pro)
4706 {
4707 }
4708
4709 int route_set_attr(struct route *this_, struct attr *attr)
4710 {
4711 //// dbg(0, "enter\n");
4712
4713 int attr_updated = 0;
4714 switch (attr->type)
4715 {
4716 case attr_route_status:
4717 // update global route_status notifier
4718 //dbg(0,"previous=%d\n", route_status_previous);
4719 //dbg(0,"this_->route_status=%d attr->u.num=%d\n", this_->route_status, attr->u.num);
4720
4721 if (this_->route_status != attr->u.num)
4722 {
4723 if (attr->u.num == 5)
4724 {
4725 }
4726 else
4727 {
4728 if (route_status_previous != attr->u.num)
4729 {
4730 //dbg(0,"update\n");
4731 this_->route_status_was_updated = 1;
4732 }
4733 route_status_previous = attr->u.num;
4734 }
4735 }
4736
4737 attr_updated = (this_->route_status != attr->u.num);
4738 this_->route_status = attr->u.num;
4739 break;
4740 case attr_destination:
4741 route_set_destination(this_, attr->u.pcoord, 1);
4742 return 1;
4743 case attr_vehicle:
4744 attr_updated = (this_->v != attr->u.vehicle);
4745 this_->v = attr->u.vehicle;
4746 if (attr_updated)
4747 {
4748 struct attr g;
4749 struct pcoord pc;
4750 struct coord c;
4751 if (vehicle_get_attr(this_->v, attr_position_coord_geo, &g, NULL))
4752 {
4753 pc.pro = projection_mg;
4754 transform_from_geo(projection_mg, g.u.coord_geo, &c);
4755 pc.x = c.x;
4756 pc.y = c.y;
4757 route_set_position(this_, &pc);
4758 }
4759 }
4760 break;
4761 default:
4762 // dbg(0, "unsupported attribute: %s\n", attr_to_name(attr->type));
4763 return 0;
4764 }
4765
4766 if (attr_updated)
4767 {
4768 callback_list_call_attr_2(this_->cbl2, attr->type, this_, attr);
4769 }
4770 return 1;
4771 }
4772
4773 int route_add_attr(struct route *this_, struct attr *attr)
4774 {
4775 //// dbg(0, "enter\n");
4776
4777 switch (attr->type)
4778 {
4779 case attr_callback:
4780 callback_list_add(this_->cbl2, attr->u.callback);
4781 return 1;
4782 default:
4783 return 0;
4784 }
4785 }
4786
4787 int route_remove_attr(struct route *this_, struct attr *attr)
4788 {
4789 //// dbg(0, "enter\n");
4790
4791 switch (attr->type)
4792 {
4793 case attr_callback:
4794 callback_list_remove(this_->cbl2, attr->u.callback);
4795 return 1;
4796 case attr_vehicle:
4797 this_->v = NULL;
4798 return 1;
4799 default:
4800 return 0;
4801 }
4802 }
4803
4804 int route_get_attr(struct route *this_, enum attr_type type, struct attr *attr, struct attr_iter *iter)
4805 {
4806 //// dbg(0, "enter\n");
4807
4808 int ret = 1;
4809 switch (type)
4810 {
4811 case attr_map:
4812 attr->u.map = route_get_map(this_);
4813 ret = (attr->u.map != NULL);
4814 break;
4815 case attr_destination:
4816 if (this_->destinations)
4817 {
4818 struct route_info *dst;
4819 if (iter)
4820 {
4821 if (iter->u.list)
4822 {
4823 iter->u.list = g_list_next(iter->u.list);
4824 }
4825 else
4826 {
4827 iter->u.list = this_->destinations;
4828 }
4829 if (!iter->u.list)
4830 {
4831 return 0;
4832 }
4833 dst = (struct route_info*) iter->u.list->data;
4834 }
4835 else
4836 { //No iter handling
4837 dst = route_get_dst(this_);
4838 }
4839 attr->u.pcoord = &this_->pc;
4840 this_->pc.pro = projection_mg; /* fixme */
4841 this_->pc.x = dst->c.x;
4842 this_->pc.y = dst->c.y;
4843 }
4844 else
4845 ret = 0;
4846 break;
4847 case attr_vehicle:
4848 attr->u.vehicle = this_->v;
4849 ret = (this_->v != NULL);
4850 //dbg(0,"get vehicle %p\n",this_->v);
4851 break;
4852 case attr_vehicleprofile:
4853 attr->u.vehicleprofile = this_->vehicleprofile;
4854 ret = (this_->vehicleprofile != NULL);
4855 break;
4856 case attr_route_status:
4857 attr->u.num = this_->route_status;
4858 break;
4859 case attr_destination_time:
4860 if (this_->path2 && (this_->route_status == route_status_path_done_new || this_->route_status == route_status_path_done_incremental))
4861 {
4862
4863 attr->u.num = this_->path2->path_time;
4864 //dbg(1, "path_time %d\n", attr->u.num);
4865 }
4866 else
4867 ret = 0;
4868 break;
4869 case attr_destination_length:
4870 if (this_->path2 && (this_->route_status == route_status_path_done_new || this_->route_status == route_status_path_done_incremental))
4871 attr->u.num = this_->path2->path_len;
4872 else
4873 ret = 0;
4874 break;
4875 default:
4876 return 0;
4877 }
4878 attr->type = type;
4879 return ret;
4880 }
4881
4882 struct attr_iter *
4883 route_attr_iter_new(void)
4884 {
4885 //// dbg(0, "enter\n");
4886
4887 return g_new0(struct attr_iter, 1);
4888 }
4889
4890 void route_attr_iter_destroy(struct attr_iter *iter)
4891 {
4892 //// dbg(0, "enter\n");
4893
4894 g_free(iter);
4895 }
4896
4897 void route_init(void)
4898 {
4899 //// dbg(0, "enter\n");
4900
4901 plugin_register_map_type("route", route_map_new);
4902 plugin_register_map_type("route_graph", route_graph_map_new);
4903 }
4904
4905 void route_destroy(struct route *this_)
4906 {
4907 // dbg(0, "enter\n");
4908
4909 route_path_destroy(this_->path2, 1);
4910 route_graph_destroy(this_->graph);
4911 route_clear_destinations(this_);
4912 route_info_free(this_->pos);
4913 map_destroy(this_->map);
4914 map_destroy(this_->graph_map);
4915 g_free(this_);
4916 }

   
Visit the ZANavi Wiki