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

Contents of /navit/navit/route.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 50 - (show annotations) (download)
Wed Jun 22 07:33:35 2016 UTC (7 years, 9 months ago) by zoff99
File MIME type: text/plain
File size: 160953 byte(s)
v2.0.51
1 /* jandegr 2016 : try to merge the relevant changes from my Navit ext_graph_prep branch
2 * to allow P-turns and to allow for later turn cost calculation
3 */
4
5 /**
6 * ZANavi, Zoff Android Navigation system.
7 * Copyright (C) 2011-2015 Zoff <zoff@zoff.cc>
8 *
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * version 2 as published by the Free Software Foundation.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the
20 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21 * Boston, MA 02110-1301, USA.
22 */
23
24 /**
25 * Navit, a modular navigation system.
26 * Copyright (C) 2005-2008 Navit Team
27 *
28 * This program is free software; you can redistribute it and/or
29 * modify it under the terms of the GNU General Public License
30 * version 2 as published by the Free Software Foundation.
31 *
32 * This program is distributed in the hope that it will be useful,
33 * but WITHOUT ANY WARRANTY; without even the implied warranty of
34 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
35 * GNU General Public License for more details.
36 *
37 * You should have received a copy of the GNU General Public License
38 * along with this program; if not, write to the
39 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
40 * Boston, MA 02110-1301, USA.
41 */
42
43 /** @file
44 * @brief Contains code related to finding a route from a position to a destination
45 *
46 * Routing uses segments, points and items. Items are items from the map: Streets, highways, etc.
47 * Segments represent such items, or parts of it. Generally, a segment is a driveable path. An item
48 * can be represented by more than one segment - in that case it is "segmented". Each segment has an
49 * "offset" associated, that indicates at which position in a segmented item this segment is - a
50 * segment representing a not-segmented item always has the offset 1.
51 * A point is located at the end of segments, often connecting several segments.
52 *
53 * The code in this file will make navit find a route between a position and a destination.
54 * It accomplishes this by first building a "route graph". This graph contains segments and
55 * points.
56 *
57 * After building this graph in route_graph_build(), the function route_graph_flood() assigns every
58 * point and segment a "value" which represents the "costs" of traveling from this point to the
59 * destination. This is done by Dijkstra's algorithm.
60 *
61 * When the graph is built a "route path" is created, which is a path in this graph from a given
62 * position to the destination determined at time of building the graph.
63 */
64
65 #include <stdio.h>
66 #include <stdlib.h>
67 #include <string.h>
68
69 #if 0
70 #include <math.h>
71 #include <assert.h>
72 #include <unistd.h>
73 #include <sys/time.h>
74 #endif
75
76 #include "glib_slice.h"
77 #include "config.h"
78 #include "point.h"
79 #include "graphics.h"
80 #include "profile.h"
81 #include "coord.h"
82 #include "projection.h"
83 #include "item.h"
84 #include "map.h"
85 #include "mapset.h"
86 #include "route.h"
87 #include "track.h"
88 #include "transform.h"
89 #include "plugin.h"
90 #include "fib.h"
91 #include "event.h"
92 #include "callback.h"
93 #include "vehicle.h"
94 #include "vehicleprofile.h"
95 #include "roadprofile.h"
96 #include "debug.h"
97
98 #include "navit.h"
99
100
101
102 // #define NAVIT_FUNC_CALLS_DEBUG_PRINT 1
103
104
105 // --------------- debug function calls ------------------
106 // --------------- debug function calls ------------------
107 #ifdef NAVIT_FUNC_CALLS_DEBUG_PRINT
108 #undef return2
109 #define return2 dbg_func(0, global_func_indent_counter, "return(%d)\n", __LINE__);global_func_indent_counter--;return
110
111 #define __F_START__ global_func_indent_counter++;dbg_func(0, global_func_indent_counter, "enter\n");
112 #define __F_END__ dbg_func(0, global_func_indent_counter, "leave\n");global_func_indent_counter--;
113 #else
114 #undef return2
115 #define return2 return
116
117 #define __F_START__
118 #define __F_END__
119 #endif
120 // --------------- debug function calls ------------------
121 // --------------- debug function calls ------------------
122
123
124
125 struct map_priv
126 {
127 struct route *route;
128 };
129
130 int debug_route = 0;
131
132
133 #define RP_TRAFFIC_DISTORTION 1
134 #define RP_TURN_RESTRICTION 2
135 #define RP_TURN_RESTRICTION_RESOLVED 4
136 #define RP_TRAFFIC_LIGHT 8
137 #define RP_TRAFFIC_LIGHT_RESOLVED 16
138
139
140
141 #define RSD_OFFSET(x) *((int *)route_segment_data_field_pos((x), attr_offset))
142 #define RSD_MAXSPEED(x) *((int *)route_segment_data_field_pos((x), attr_maxspeed))
143 #define RSD_SIZE_WEIGHT(x) *((struct size_weight_limit *)route_segment_data_field_pos((x), attr_vehicle_width))
144 #define RSD_DANGEROUS_GOODS(x) *((int *)route_segment_data_field_pos((x), attr_vehicle_dangerous_goods))
145
146
147
148 /**
149 * @brief A traffic distortion
150 *
151 * This is distortion in the traffic where you can't drive as fast as usual or have to wait for some time
152 */
153 struct route_traffic_distortion
154 {
155 int maxspeed; /**< Maximum speed possible in km/h */
156 int delay; /**< Delay in tenths of seconds */
157 };
158
159 /**
160 * @brief A segment in the route path
161 *
162 * This is a segment in the route path.
163 */
164 struct route_path_segment
165 {
166 struct route_path_segment *next; /**< Pointer to the next segment in the path */
167 struct route_segment_data *data; /**< The segment data */
168 int direction; /**< Order in which the coordinates are ordered. >0 means "First
169 * coordinate of the segment is the first coordinate of the item", <=0
170 * means reverse. */
171 unsigned ncoords; /**< How many coordinates does this segment have? */
172 struct coord c[0]; /**< Pointer to the ncoords coordinates of this segment */
173 /* WARNING: There will be coordinates following here, so do not create new fields after c! */
174 };
175
176 /**
177 * @brief A complete route path
178 *
179 * This structure describes a whole routing path
180 */
181 struct route_path
182 {
183 int in_use; /**< The path is in use and can not be updated */
184 int update_required; /**< The path needs to be updated after it is no longer in use */
185 int updated; /**< The path has only been updated */
186 int path_time; /**< Time to pass the path */
187 int path_len; /**< Length of the path */
188 struct route_path_segment *path; /**< The first segment in the path, i.e. the segment one should
189 * drive in next */
190 struct route_path_segment *path_last; /**< The last segment in the path */
191 /* XXX: path_hash is not necessery now */
192 struct item_hash *path_hash; /**< A hashtable of all the items represented by this route's segements */
193 struct route_path *next; /**< Next route path in case of intermediate destinations */
194 };
195
196 /**
197 * @brief A complete route
198 *
199 * This struct holds all information about a route.
200 */
201
202 /**
203 * @brief A complete route graph
204 *
205 * This structure describes a whole routing graph
206 */
207 struct route_graph
208 {
209 int busy; /**< The graph is being built */
210 struct map_selection *sel; /**< The rectangle selection for the graph */
211 struct mapset_handle *h; /**< Handle to the mapset */
212 struct map *m; /**< Pointer to the currently active map */
213 struct map_rect *mr; /**< Pointer to the currently active map rectangle */
214 struct vehicleprofile *vehicleprofile; /**< The vehicle profile */
215 struct callback *idle_cb; /**< Idle callback to process the graph */
216 struct callback *done_cb; /**< Callback when graph is done */
217 struct event_idle *idle_ev; /**< The pointer to the idle event */
218 struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */
219 // *ORIG* #define HASH_SIZE 8192
220 // #define HASH_SIZE 65536
221 #define HASH_SIZE 16384
222 struct route_graph_point *hash[HASH_SIZE]; /**< A hashtable containing all route_graph_points in this graph */
223 };
224
225 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
226
227 /**
228 * @brief Iterator to iterate through all route graph segments in a route graph point
229 *
230 * This structure can be used to iterate through all route graph segments connected to a
231 * route graph point. Use this with the rp_iterator_* functions.
232 */
233 struct route_graph_point_iterator
234 {
235 struct route_graph_point *p; /**< The route graph point whose segments should be iterated */
236 int end; /**< Indicates if we have finished iterating through the "start" segments */
237 struct route_graph_segment *next; /**< The next segment to be returned */
238 };
239
240 struct attr_iter
241 {
242 union
243 {
244 GList *list;
245 } u;
246 };
247
248 static struct route_info * route_find_nearest_street(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *c);
249 static struct route_info * route_find_nearest_street_harder(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc, int max_dist_wanted);
250 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
251 static void route_graph_update(struct route *this, struct callback *cb, int async);
252 static void route_graph_build_done(struct route_graph *rg, int cancel);
253 static struct route_path *route_path_new(struct route *rr, struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct vehicleprofile *profile);
254 static void route_process_street_graph(struct route_graph *this, struct item *item, struct vehicleprofile *profile);
255 //static void route_graph_destroy(struct route_graph *this);
256 void route_path_update(struct route *this, int cancel, int async);
257 static int route_time_seg(struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist);
258 static void route_graph_flood(struct route_graph *this, struct route_info *dst, struct route_info *pos, struct vehicleprofile *profile, struct callback *cb);
259 static void route_graph_reset(struct route_graph *this);
260
261
262 char *route_status_to_name(enum route_status s)
263 {
264 if (s == route_status_no_destination)
265 {
266 return "route_status_no_destination";
267 }
268 else if (s == route_status_destination_set)
269 {
270 return "route_status_destination_set";
271 }
272 else if (s == route_status_not_found)
273 {
274 return "route_status_not_found";
275 }
276 else if (s == route_status_building_path)
277 {
278 return "route_status_building_path";
279 }
280 else if (s == route_status_building_graph)
281 {
282 return "route_status_building_graph";
283 }
284 else if (s == route_status_path_done_new)
285 {
286 return "route_status_path_done_new";
287 }
288 else if (s == route_status_path_done_incremental)
289 {
290 return "route_status_path_done_incremental";
291 }
292
293 return NULL;
294 }
295
296
297 /**
298 * @brief Returns the projection used for this route
299 *
300 * @param route The route to return the projection for
301 * @return The projection used for this route
302 */
303 static enum projection route_projection(struct route *route)
304 {
305 struct street_data *street;
306 struct route_info *dst = route_get_dst(route);
307 if (!route->pos && !dst)
308 {
309 return projection_none;
310 }
311 street = route->pos ? route->pos->street : dst->street;
312 if (!street || !street->item.map)
313 {
314 return projection_none;
315 }
316 return map_projection(street->item.map);
317 }
318
319 /**
320 * @brief Creates a new graph point iterator
321 *
322 * This function creates a new route graph point iterator, that can be used to
323 * iterate through all segments connected to the point.
324 *
325 * @param p The route graph point to create the iterator from
326 * @return A new iterator.
327 */
328 static struct route_graph_point_iterator rp_iterator_new(struct route_graph_point *p)
329 {
330 //// dbg(0, "enter\n");
331
332 struct route_graph_point_iterator it;
333
334 it.p = p;
335 if (p->start)
336 {
337 it.next = p->start;
338 it.end = 0;
339 }
340 else
341 {
342 it.next = p->end;
343 it.end = 1;
344 }
345
346 return it;
347 }
348
349 /**
350 * @brief Gets the next segment connected to a route graph point from an iterator
351 *
352 * @param it The route graph point iterator to get the segment from
353 * @return The next segment or NULL if there are no more segments
354 */
355 static struct route_graph_segment *rp_iterator_next(struct route_graph_point_iterator *it)
356 {
357 //// dbg(0, "enter\n");
358
359 struct route_graph_segment *ret;
360
361 ret = it->next;
362 if (!ret)
363 {
364 return NULL;
365 }
366
367 if (!it->end)
368 {
369 if (ret->start_next)
370 {
371 it->next = ret->start_next;
372 }
373 else
374 {
375 it->next = it->p->end;
376 it->end = 1;
377 }
378 }
379 else
380 {
381 it->next = ret->end_next;
382 }
383
384 return ret;
385 }
386
387 /**
388 * @brief Checks if the last segment returned from a route_graph_point_iterator comes from the end
389 *
390 * @param it The route graph point iterator to be checked
391 * @return 1 if the last segment returned comes from the end of the route graph point, 0 otherwise
392 */
393 static int rp_iterator_end(struct route_graph_point_iterator *it)
394 {
395 //// dbg(0, "enter\n");
396
397 if (it->end && (it->next != it->p->end))
398 {
399 return 1;
400 }
401 else
402 {
403 return 0;
404 }
405 }
406
407 /**
408 * @brief Destroys a route_path
409 *
410 * @param this The route_path to be destroyed
411 */
412 void route_path_destroy(struct route_path *this, int recurse)
413 {
414 __F_START__
415
416 struct route_path_segment *c, *n;
417 struct route_path *next;
418
419 while (this)
420 {
421 next = this->next;
422 if (this->path_hash)
423 {
424 item_hash_destroy(this->path_hash);
425 this->path_hash = NULL;
426 }
427 c = this->path;
428 while (c)
429 {
430 n = c->next;
431 g_free(c);
432 c = n;
433 }
434
435 this->in_use--;
436
437 if (!this->in_use)
438 g_free(this);
439
440 if (!recurse)
441 break;
442
443 this = next;
444 }
445
446 __F_END__
447 }
448
449 /**
450 * @brief Creates a completely new route structure
451 *
452 * @param attrs Not used
453 * @return The newly created route
454 */
455 struct route *
456 route_new(struct attr *parent, struct attr **attrs)
457 {
458 __F_START__
459
460 struct route *this=g_new0(struct route, 1);
461 struct attr dest_attr;
462
463 if (attr_generic_get_attr(attrs, NULL, attr_destination_distance, &dest_attr, NULL))
464 {
465 this->destination_distance = dest_attr.u.num;
466 }
467 else
468 {
469 this->destination_distance = 50; // Default value
470 }
471 this->cbl2 = callback_list_new("route_new:this->cbl2");
472
473 return2 this;
474 //dbg(0, "return(%d)\n", __LINE__);return this;
475
476 __F_END__
477 }
478
479 int route_get_real_oneway_mask(int road_flag, int mask)
480 {
481 //dbg(0, "road_flag = %x mask = %x gvp = %d\n", road_flag, mask, global_vehicle_profile);
482
483 if (global_vehicle_profile == 2) // bicycle no one-ways
484 {
485 // dont care about one-ways
486 return mask;
487 }
488 else if (global_vehicle_profile == 1) // bicycle
489 {
490 if (road_flag & NAVIT_AF_ONEWAY_BICYCLE_NO)
491 {
492 // one-ways does not apply to bicycles here
493 //dbg(0, "ret01m = %x\n", (mask & ~NAVIT_AF_ONEWAYMASK));
494 return (mask & ~NAVIT_AF_ONEWAYMASK);
495 }
496 else
497 {
498 //dbg(0, "ret02 = %x\n", mask);
499 return mask;
500 }
501 }
502 else // normal one-way handling
503 {
504 //dbg(0, "ret03 = %x\n", (mask));
505 return mask;
506 }
507 }
508
509 int route_get_real_oneway_flag(int road_flag, int oneway_flag_value)
510 {
511 //dbg(0, "road_flag = %x oneway_flag = %x\n", road_flag, oneway_flag_value);
512
513 if (global_vehicle_profile == 2) // bicycle no one-ways
514 {
515 // dont care about one-ways
516 //dbg(0, "ret00 = 0\n");
517 return 0;
518 }
519 else if (global_vehicle_profile == 1) // bicycle
520 {
521 if (road_flag & NAVIT_AF_ONEWAY_BICYCLE_NO)
522 {
523 // one-ways does not apply to bicycles here
524 //dbg(0, "ret01 = 0\n");
525 return 0;
526 }
527 else
528 {
529 //dbg(0, "ret02 = %x\n", (road_flag & oneway_flag_value));
530 return (road_flag & oneway_flag_value);
531 }
532 }
533 else // normal one-way handling
534 {
535 //dbg(0, "ret03 = %x\n", (road_flag & oneway_flag_value));
536 return (road_flag & oneway_flag_value);
537 }
538 }
539
540
541 /**
542 * @brief Checks if a segment is part of a roundabout
543 *
544 * This function checks if a segment is part of a roundabout.
545 *
546 * @param seg The segment to be checked
547 * @param level How deep to scan the route graph
548 * @param direction Set this to 1 if we're entering the segment through its end, to 0 otherwise
549 * @param origin Used internally, set to NULL
550 * @return 1 If a roundabout was detected, 0 otherwise
551 */
552 static int route_check_roundabout(struct route_graph_segment *seg, int level, int direction, struct route_graph_segment *origin)
553 {
554 //// dbg(0, "enter\n");
555
556 struct route_graph_point_iterator it, it2;
557 struct route_graph_segment *cur;
558 int count = 0;
559
560 if (!level)
561 {
562 return 0;
563 }
564 if (!direction && !(route_get_real_oneway_flag(seg->data.flags, NAVIT_AF_ONEWAY)))
565 {
566 return 0;
567 }
568 if (direction && !(route_get_real_oneway_flag(seg->data.flags, NAVIT_AF_ONEWAYREV)))
569 {
570 return 0;
571 }
572 if (seg->data.flags & NAVIT_AF_ROUNDABOUT_VALID)
573 {
574 return 0;
575 }
576
577 if (!origin)
578 {
579 origin = seg;
580 }
581
582 if (!direction)
583 {
584 it = rp_iterator_new(seg->end);
585 }
586 else
587 {
588 it = rp_iterator_new(seg->start);
589 }
590 it2 = it;
591
592 while ((cur = rp_iterator_next(&it2)))
593 {
594 count++;
595 }
596
597 if (count > 3) // 3 z8z8
598 {
599 return 0;
600 }
601
602 cur = rp_iterator_next(&it);
603 while (cur)
604 {
605 if (cur == seg)
606 {
607 cur = rp_iterator_next(&it);
608 continue;
609 }
610
611
612 if (cur->data.item.type != origin->data.item.type)
613 {
614 // This street is of another type, can't be part of the roundabout
615 cur = rp_iterator_next(&it);
616 continue;
617 }
618
619 if (cur == origin)
620 {
621 seg->data.flags |= NAVIT_AF_ROUNDABOUT;
622 return 1;
623 }
624
625 if (route_check_roundabout(cur, (level - 1), rp_iterator_end(&it), origin))
626 {
627 seg->data.flags |= NAVIT_AF_ROUNDABOUT;
628 return 1;
629 }
630
631 cur = rp_iterator_next(&it);
632 }
633
634 return 0;
635 }
636
637 /**
638 * @brief Sets the mapset of the route passed
639 *
640 * @param this The route to set the mapset for
641 * @param ms The mapset to set for this route
642 */
643 void route_set_mapset(struct route *this, struct mapset *ms)
644 {
645 __F_START__
646
647 this->ms = ms;
648
649 __F_END__
650 }
651
652 /**
653 * @brief Sets the vehicle profile of a route
654 *
655 * @param this The route to set the profile for
656 * @param prof The vehicle profile
657 */
658
659 void route_set_profile(struct route *this, struct vehicleprofile *prof)
660 {
661 __F_START__
662
663 if (this->vehicleprofile != prof)
664 {
665 this->vehicleprofile = prof;
666 route_path_update(this, 1, 1);
667 }
668 __F_END__
669 }
670
671 /**
672 * @brief Returns the mapset of the route passed
673 *
674 * @param this The route to get the mapset of
675 * @return The mapset of the route passed
676 */
677 struct mapset *
678 route_get_mapset(struct route *this)
679 {
680 __F_START__
681
682 return2 this->ms;
683
684 __F_END__
685 }
686
687 /**
688 * @brief Returns the current position within the route passed
689 *
690 * @param this The route to get the position for
691 * @return The position within the route passed
692 */
693 struct route_info *
694 route_get_pos(struct route *this)
695 {
696 __F_START__
697
698 return2 this->pos;
699
700 __F_END__
701 }
702
703 /**
704 * @brief Returns the destination of the route passed
705 *
706 * @param this The route to get the destination for
707 * @return The destination of the route passed
708 */
709 struct route_info *
710 route_get_dst(struct route *this)
711 {
712 //// dbg(0, "enter\n");
713
714 struct route_info *dst = NULL;
715
716 if (this->destinations)
717 dst = g_list_last(this->destinations)->data;
718 return dst;
719 }
720
721 /**
722 * @brief Checks if the path is calculated for the route passed
723 *
724 * @param this The route to check
725 * @return True if the path is calculated, false if not
726 */
727 int route_get_path_set(struct route *this)
728 {
729 __F_START__
730
731 return2 this->path2 != NULL;
732 __F_END__
733 }
734
735 /**
736 * @brief Checks if the route passed contains a certain item within the route path
737 *
738 * This function checks if a certain items exists in the path that navit will guide
739 * the user to his destination. It does *not* check if this item exists in the route
740 * graph!
741 *
742 * @param this The route to check for this item
743 * @param item The item to search for
744 * @return True if the item was found, false if the item was not found or the route was not calculated
745 */
746 int route_contains(struct route *this, struct item *item)
747 {
748 if (!this->path2 || !this->path2->path_hash)
749 {
750 return 0;
751 }
752
753 if (item_hash_lookup(this->path2->path_hash, item))
754 {
755 return 1;
756 }
757
758 if (!this->pos || !this->pos->street)
759 {
760 return 0;
761 }
762
763 return item_is_equal(this->pos->street->item, *item);
764 }
765
766 static struct route_info *
767 route_next_destination(struct route *this)
768 {
769 __F_START__
770
771 if (!this->destinations)
772 {
773 return2 NULL;
774 }
775
776 return2 this->destinations->data;
777 __F_END__
778 }
779
780 /**
781 * @brief Checks if a route has reached its destination
782 *
783 * @param this The route to be checked
784 * @return True if the destination is "reached", false otherwise.
785 */
786 int route_destination_reached(struct route *this)
787 {
788 __F_START__
789
790 struct street_data *sd = NULL;
791 enum projection pro;
792 struct route_info *dst = route_next_destination(this);
793
794 if (!this->pos)
795 {
796 return2 0;
797 }
798
799 if (!dst)
800 {
801 return2 0;
802 }
803
804 sd = this->pos->street;
805
806 if (!this->path2)
807 {
808 return2 0;
809 }
810
811 // this fixed a crash for large offroad start segments
812 if (!this->pos->street)
813 {
814 return2 0;
815 }
816
817 if (!item_is_equal(this->pos->street->item, dst->street->item))
818 {
819 return2 0;
820 }
821
822 if ((route_get_real_oneway_flag(sd->flags, NAVIT_AF_ONEWAY)) && (this->pos->lenneg >= dst->lenneg))
823 { // We would have to drive against the one-way road
824 return2 0;
825 }
826
827 if ((route_get_real_oneway_flag(sd->flags, NAVIT_AF_ONEWAYREV)) && (this->pos->lenpos >= dst->lenpos))
828 {
829 return2 0;
830 }
831
832 pro = route_projection(this);
833 if (pro == projection_none)
834 {
835 return2 0;
836 }
837
838 if (transform_distance(pro, &this->pos->c, &dst->lp) > this->destination_distance)
839 {
840 return2 0;
841 }
842
843 if (g_list_next(this->destinations))
844 {
845 return2 1;
846 }
847 else
848 {
849 return2 2;
850 }
851 __F_END__
852 }
853
854
855 static struct route_info *
856 route_previous_destination(struct route *this)
857 {
858 __F_START__
859
860 GList *l = g_list_find(this->destinations, this->current_dst);
861 if (!l)
862 {
863 return2 this->pos;
864 }
865
866 l = g_list_previous(l);
867 if (!l)
868 {
869 return2 this->pos;
870 }
871
872 return2 l->data;
873
874 __F_END__
875
876 }
877
878 static void route_path_update_done(struct route *this, int new_graph)
879 {
880 __F_START__
881
882 struct route_path *oldpath = this->path2;
883 struct attr route_status;
884 struct route_info *prev_dst;
885 route_status.type = attr_route_status;
886
887 if (this->path2 && (this->path2->in_use > 1))
888 {
889 this->path2->update_required = 1 + new_graph;
890 return2;
891 }
892
893 route_status.u.num = route_status_building_path;
894 // this call is needed to update navigation and speak directions!!
895 route_set_attr(this, &route_status);
896
897 prev_dst = route_previous_destination(this);
898
899 dbg(0, "AAA:001 lp=%d\n", this->link_path);
900
901 if (this->link_path)
902 {
903 dbg(0, "AAA:002 lp=%d\n", this->link_path);
904
905 // generate route path from "prev_dst" to "this->current_dst"
906
907 dbg(0, "RPNEW:CALL 001\n");
908
909 this->path2 = route_path_new(this, this->graph, NULL, prev_dst, this->current_dst, this->vehicleprofile);
910 if (this->path2)
911 {
912 this->path2->next = oldpath;
913 }
914 }
915 else
916 {
917 dbg(0, "AAA:003 lp=%d\n", this->link_path);
918
919 dbg(0, "RPNEW:CALL 002\n");
920
921 // generate route path from "prev_dst" to "this->current_dst"
922 this->path2 = route_path_new(this, this->graph, oldpath, prev_dst, this->current_dst, this->vehicleprofile);
923 if (oldpath && this->path2)
924 {
925 this->path2->next = oldpath->next;
926 route_path_destroy(oldpath, 0);
927 }
928 }
929
930 dbg(0, "AAA:004 lp=%d\n", this->link_path);
931
932 if (this->path2)
933 {
934 struct route_path_segment *seg = this->path2->path;
935 int path_time = 0, path_len = 0;
936 while (seg)
937 {
938 /* FIXME */
939 int seg_time = route_time_seg(this->vehicleprofile, seg->data, NULL);
940
941 if (seg_time == INT_MAX)
942 {
943 // dbg(1, "error\n");
944 }
945 else
946 {
947 path_time += seg_time;
948 }
949 path_len += seg->data->len;
950 seg = seg->next;
951 }
952
953 this->path2->path_time = path_time;
954 this->path2->path_len = path_len;
955
956 dbg(0, "AAA:005 lp=%d\n", this->link_path);
957 if (prev_dst != this->pos) // do we have more destinations? (waypoints)
958 {
959 dbg(0, "AAA:006 lp=%d\n", this->link_path);
960
961 dbg(0, "RPNEW:SET PREV DEST -1\n");
962
963 this->link_path = 1;
964 this->current_dst = prev_dst; // set current destination back 1 waypoint, to calculate the next part of the route
965 // (actually previous part, since we walk backwards to position)
966 route_graph_reset(this->graph);
967 // generate next route graph (and later route path)
968 route_graph_flood(this->graph, this->current_dst, this->pos, this->vehicleprofile, this->route_graph_flood_done_cb);
969
970 return2;
971 }
972
973 if (!new_graph && this->path2->updated)
974 {
975 // this is called on every GPS update!!
976 route_status.u.num = route_status_path_done_incremental;
977
978 //#ifdef NAVIT_ROUTING_DEBUG_PRINT
979 // dbg(0,"== DRAW MAP 001 ==\n");
980 //#endif
981 // // need to paint map 1 time here!!
982 // if (global_navit)
983 // {
984 // navit_draw(global_navit);
985 // }
986 }
987 else
988 {
989 // this is called only when the route has been calculated
990 route_status.u.num = route_status_path_done_new;
991
992 #ifdef NAVIT_ROUTING_DEBUG_PRINT
993 dbg(0,"== DRAW MAP 002 ==\n");
994 #endif
995 // need to paint map 1 time here!!
996 if (global_navit)
997 {
998 navit_draw(global_navit);
999 }
1000 }
1001 }
1002 else
1003 {
1004 dbg(0, "AAA:007 lp=%d\n", this->link_path);
1005
1006 // dbg(0, "try harder\n");
1007 // Try to rebuild the graph with smaller roads
1008 if (this->try_harder == 0)
1009 {
1010 this->try_harder = 1;
1011 route_graph_destroy(this->graph);
1012 this->graph = NULL;
1013 route_path_update(this, 1, 1);
1014 }
1015 else
1016 {
1017 route_status.u.num = route_status_not_found;
1018 }
1019 }
1020
1021 dbg(0, "AAA:099 lp=%d\n", this->link_path);
1022
1023
1024 this->link_path = 0;
1025 route_set_attr(this, &route_status);
1026
1027 __F_END__
1028 }
1029
1030 /**
1031 * @brief Updates the route graph and the route path if something changed with the route
1032 *
1033 * This will update the route graph and the route path of the route if some of the
1034 * route's settings (destination, position) have changed.
1035 *
1036 * @attention For this to work the route graph has to be destroyed if the route's
1037 * @attention destination is changed somewhere!
1038 *
1039 * @param this The route to update
1040 */
1041 void route_path_update(struct route *this, int cancel, int async)
1042 {
1043 __F_START__
1044
1045 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1046 dbg(0, "ROUTExxPOSxx:route_path_update:enter\n");
1047 #endif
1048
1049 //dbg(0, "enter\n");
1050
1051 //dbg(1, "enter %d\n", cancel);
1052 if (!this->pos || !this->destinations)
1053 {
1054 //dbg(0, "destroy\n");
1055 route_path_destroy(this->path2, 1);
1056 this->path2 = NULL;
1057
1058 return2;
1059 }
1060
1061 if (cancel)
1062 {
1063 route_graph_destroy(this->graph);
1064 this->graph = NULL;
1065 }
1066
1067 /* the graph is destroyed when setting the destination */
1068 if (this->graph)
1069 {
1070 if (this->graph->busy)
1071 {
1072 //dbg(0, "busy building graph\n");
1073 return2;
1074 }
1075 // we can try to update
1076 //dbg(0, "try update\n");
1077 route_path_update_done(this, 0); // calls route_set_attr -> navigation_update !! (first loop)
1078 }
1079 else
1080 {
1081 route_path_destroy(this->path2, 1);
1082 this->path2 = NULL;
1083 }
1084
1085 if (!this->graph || !this->path2)
1086 {
1087 //dbg(0, "rebuild graph\n");
1088 if (!this->route_graph_flood_done_cb)
1089 {
1090 this->route_graph_flood_done_cb = callback_new_2(callback_cast(route_path_update_done), this, (long) 1);
1091 callback_add_names(this->route_graph_flood_done_cb, "route_path_update", "route_path_update_done");
1092 }
1093 //dbg(0, "route_graph_update\n");
1094 route_graph_update(this, this->route_graph_flood_done_cb, async); // calls route_set_attr -> navigation_update !! (2nd loop)
1095 }
1096
1097 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1098 dbg(0, "ROUTExxPOSxx:route_path_update:leave\n");
1099 #endif
1100
1101 __F_END__
1102 }
1103
1104 /**
1105 * @brief This will calculate all the distances stored in a route_info
1106 *
1107 * @param ri The route_info to calculate the distances for
1108 * @param pro The projection used for this route
1109 */
1110 static void route_info_distances(struct route_info *ri, enum projection pro)
1111 {
1112 __F_START__
1113
1114 int npos = ri->pos + 1;
1115 struct street_data *sd = ri->street;
1116
1117 /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
1118
1119 ri->lenextra = transform_distance(pro, &ri->lp, &ri->c);
1120
1121 ri->lenneg = transform_polyline_length(pro, sd->c, npos) + transform_distance(pro, &sd->c[ri->pos], &ri->lp);
1122
1123 ri->lenpos = transform_polyline_length(pro, sd->c + npos, sd->count - npos) + transform_distance(pro, &sd->c[npos], &ri->lp);
1124
1125 if (ri->lenneg || ri->lenpos)
1126 {
1127 ri->percent = (ri->lenneg * 100) / (ri->lenneg + ri->lenpos);
1128 }
1129 else
1130 {
1131 ri->percent = 50;
1132 }
1133
1134 dbg(0,"AAA:(1)len extra=%d\n", ri->lenextra);
1135
1136 if (ri->lenextra < 1)
1137 {
1138 ri->lenextra = 1; // always set this, to avoid holes in route path display
1139 }
1140
1141 dbg(0,"AAA:(2)len extra=%d\n", ri->lenextra);
1142
1143 __F_END__
1144
1145 }
1146
1147 /**
1148 * @brief This sets the current position of the route passed
1149 *
1150 * This will set the current position of the route passed to the street that is nearest to the
1151 * passed coordinates. It also automatically updates the route.
1152 *
1153 * @param this The route to set the position of
1154 * @param pos Coordinates to set as position
1155 */
1156 void route_set_position(struct route *this, struct pcoord *pos)
1157 {
1158 __F_START__
1159
1160 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1161 dbg(0, "ROUTExxPOSxx:route_set_position: enter\n");
1162 #endif
1163
1164
1165 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1166 // pcoord to geo
1167 struct coord_geo g22;
1168 struct coord c22;
1169 c22.x = pos->x;
1170 c22.y = pos->y;
1171 transform_to_geo(projection_mg, &c22, &g22);
1172
1173 dbg(0, "ROUTExxPOSxx:route_set_position: %d %d %f %f\n", pos->x, pos->y, g22.lat, g22.lng);
1174 #endif
1175
1176 if (this->pos)
1177 {
1178 route_info_free(this->pos);
1179 }
1180
1181 this->pos = NULL;
1182 this->pos = route_find_nearest_street(this->vehicleprofile, this->ms, pos);
1183
1184 //dbg(0,"this->pos=%p\n", this->pos);
1185
1186 // try harder
1187 if (this->pos == NULL)
1188 {
1189 this->pos = route_find_nearest_street_harder(this->vehicleprofile, this->ms, pos, 5000);
1190 //dbg(0,"this->pos=%p\n", this->pos);
1191 }
1192
1193 // If there is no nearest street, bail out.
1194 if (!this->pos)
1195 {
1196 //dbg(0,"this->pos=%p\n", this->pos);
1197 // this->pos=g_new0(struct route_info, 1); *******
1198 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1199 //dbg(0,"ROUTExxPOSxx:route_set_position:return 001\n");
1200 dbg(0, "ROUTExxPOSxx:route_set_position:(there is no nearest street, bail out) return 001\n");
1201 #endif
1202 return2;
1203 }
1204
1205 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1206 dbg(0, "ROUTExxPOSxx:route_set_position:1: x y: %d %d\n", pos->x, pos->y);
1207 //dbg(0, "2: x y: %i %i\n", this->pos->c.x, this->pos->c.y);
1208 //dbg(0, "3: x y: %i %i\n", this->pos->lp.x, this->pos->lp.y);
1209 #endif
1210
1211 this->pos->street_direction = 0;
1212 //dbg(1, "this->pos=%p\n", this->pos);
1213 route_info_distances(this->pos, pos->pro);
1214
1215 //dbg(0,"sp 002\n");
1216
1217 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1218 dbg(0, "ROUTExxPOSxx:route_path_update: 004\n");
1219 #endif
1220 route_path_update(this, 0, 1);
1221 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1222 dbg(0, "ROUTExxPOSxx:route_path_update: 004-a\n");
1223 #endif
1224
1225 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1226 dbg(0, "ROUTExxPOSxx:route_set_position: leave\n");
1227 #endif
1228
1229 __F_END__
1230 }
1231
1232 /**
1233 * @brief Sets a route's current position based on coordinates from tracking
1234 *
1235 * @param this The route to set the current position of
1236 * @param tracking The tracking to get the coordinates from
1237 */
1238 void route_set_position_from_tracking(struct route *this, struct tracking *tracking, enum projection pro)
1239 {
1240 __F_START__
1241
1242 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1243 dbg(0, "ROUTExxPOSxx:route_set_position_from_tracking: enter\n");
1244 #endif
1245
1246 struct coord *c;
1247 struct route_info *ret;
1248 struct street_data *sd;
1249
1250 //dbg(2, "enter\n");
1251 c = tracking_get_pos(tracking);
1252 ret=g_new0(struct route_info, 1);
1253
1254 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1255 dbg(0, "ROUTExxPOSxx:route_set_position_from_tracking: %d %d\n", c->x, c->y);
1256 #endif
1257
1258 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1259 // ------- DEBUG --------
1260 // ------- DEBUG --------
1261 // ------- DEBUG --------
1262 struct coord_geo gg4;
1263 transform_to_geo(pro, c, &gg4);
1264 dbg(0, "ROUTExxPOSxx:1:http://maps.google.com/maps/api/staticmap?size=512x512&markers=color:blue|label:CC|%4.6f,%4.6f\n", gg4.lat, gg4.lng);
1265 // ------- DEBUG --------
1266 // ------- DEBUG --------
1267 // ------- DEBUG --------
1268 #endif
1269
1270 if (!ret)
1271 {
1272 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1273 dbg(0, "ROUTExxPOSxx:(Out of memory) return 001\n");
1274 #endif
1275 return2;
1276 }
1277
1278 if (this->pos)
1279 {
1280 route_info_free(this->pos);
1281 }
1282
1283 this->pos = NULL;
1284 ret->c = *c;
1285 ret->lp = *c;
1286 ret->pos = tracking_get_segment_pos(tracking);
1287 ret->street_direction = tracking_get_street_direction(tracking);
1288 sd = tracking_get_street_data(tracking);
1289
1290 // int road_angle = tracking_get_angle(tracking);
1291 //dbg(0, "ROAD angle=%d\n", road_angle);
1292
1293 if (sd)
1294 {
1295 ret->street = street_data_dup(sd);
1296 route_info_distances(ret, pro);
1297 }
1298 //dbg(
1299 // 3,
1300 // "position 0x%x,0x%x item 0x%x,0x%x direction %d pos %d lenpos %d lenneg %d\n",
1301 // c->x, c->y, sd ? sd->item.id_hi : 0, sd ? sd->item.id_lo : 0,
1302 // ret->street_direction, ret->pos, ret->lenpos, ret->lenneg);
1303 //dbg(3, "c->x=0x%x, c->y=0x%x pos=%d item=(0x%x,0x%x)\n", c->x, c->y,
1304 // ret->pos, ret->street ? ret->street->item.id_hi : 0,
1305 // ret->street ? ret->street->item.id_lo : 0);
1306 //dbg(3, "street 0=(0x%x,0x%x) %d=(0x%x,0x%x)\n",
1307 // ret->street ? ret->street->c[0].x : 0,
1308 // ret->street ? ret->street->c[0].y : 0,
1309 // ret->street ? ret->street->count - 1 : 0,
1310 // ret->street ? ret->street->c[ret->street->count - 1].x : 0,
1311 // ret->street ? ret->street->c[ret->street->count - 1].y : 0);
1312 this->pos = ret;
1313
1314 if (this->destinations)
1315 {
1316 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1317 dbg(0, "ROUTExxPOSxx:route_path_update: 001\n");
1318 #endif
1319 route_path_update(this, 0, 1);
1320 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1321 dbg(0, "ROUTExxPOSxx:route_path_update: 001-a\n");
1322 #endif
1323 }
1324 //dbg(2, "ret\n");
1325
1326 #ifdef NAVIT_ROUTING_DEBUG_PRINT
1327 dbg(0, "ROUTExxPOSxx:route_set_position_from_tracking: leave\n");
1328 #endif
1329
1330 __F_END__
1331
1332 }
1333
1334 /* Used for debuging of route_rect, what routing sees */
1335 struct map_selection *route_selection;
1336
1337 /**
1338 * @brief Returns a single map selection
1339 */
1340 struct map_selection *
1341 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
1342 {
1343 //// dbg(0, "enter\n");
1344
1345 int dx, dy, sx = 1, sy = 1, d, m;
1346 struct map_selection *sel=g_new0(struct map_selection, 1);
1347
1348 if (!sel)
1349 {
1350 dbg(0, "Out of memory\n");
1351 // printf("%s:Out of memory\n", __FUNCTION__);
1352 return sel;
1353 }
1354
1355 sel->order = order;
1356 sel->range.min = route_item_first;
1357 sel->range.max = route_item_last;
1358 // dbg(1, "%p %p\n", c1, c2);
1359 dx = c1->x - c2->x;
1360 dy = c1->y - c2->y;
1361
1362 if (dx < 0)
1363 {
1364 sx = -1;
1365 sel->u.c_rect.lu.x = c1->x;
1366 sel->u.c_rect.rl.x = c2->x;
1367 }
1368 else
1369 {
1370 sel->u.c_rect.lu.x = c2->x;
1371 sel->u.c_rect.rl.x = c1->x;
1372 }
1373
1374 if (dy < 0)
1375 {
1376 sy = -1;
1377 sel->u.c_rect.lu.y = c2->y;
1378 sel->u.c_rect.rl.y = c1->y;
1379 }
1380 else
1381 {
1382 sel->u.c_rect.lu.y = c1->y;
1383 sel->u.c_rect.rl.y = c2->y;
1384 }
1385
1386 if (dx * sx > dy * sy)
1387 {
1388 d = dx * sx;
1389 }
1390 else
1391 {
1392 d = dy * sy;
1393 }
1394
1395 m = d * rel / 100 + abs;
1396
1397 //dbg(0,"m=%d d=%d rel=%d abs=%d\n",m,d,rel,abs);
1398
1399 sel->u.c_rect.lu.x -= m;
1400 sel->u.c_rect.rl.x += m;
1401 sel->u.c_rect.lu.y += m;
1402 sel->u.c_rect.rl.y -= m;
1403 sel->next = NULL;
1404 return sel;
1405 }
1406
1407 /**
1408 * @brief Returns a list of map selections useable to create a route graph
1409 *
1410 * Returns a list of map selections useable to get a map rect from which items can be
1411 * retrieved to build a route graph. The selections are a rectangle with
1412 * c1 and c2 as two corners.
1413 *
1414 * @param c1 Corner 1 of the rectangle
1415 * @param c2 Corder 2 of the rectangle
1416 */
1417 static struct map_selection *
1418 route_calc_selection(struct coord *c, int count, int try_harder)
1419 {
1420 // dbg(0, "enter\n");
1421
1422 struct map_selection *ret, *sel;
1423 int i;
1424 struct coord_rect r;
1425
1426 if (!count)
1427 {
1428 return NULL;
1429 }
1430
1431 r.lu = c[0];
1432 r.rl = c[0];
1433 for (i = 1; i < count; i++)
1434 {
1435 // extend the rectangle to include all waypoints -> make 1 big rectangle
1436 coord_rect_extend(&r, &c[i]);
1437 }
1438
1439 // the route selection rectangle will be extened further, to find all routes (by 25%)
1440 #ifdef HAVE_API_ANDROID
1441 if (global_show_route_rectangles)
1442 {
1443 send_route_rect_to_java(r.lu.x, r.lu.y, r.rl.x, r.rl.y, -99);
1444 }
1445 #endif
1446
1447
1448 double len_from_start_to_dest = transform_distance(projection_mg, &c[0], &c[count - 1]);
1449 dbg(0, "distdist=%f\n", len_from_start_to_dest);
1450
1451
1452 if ((global_vehicle_profile == 1) || (global_vehicle_profile == 2)) // ------------ BICYCLE MODE -----------
1453 {
1454 if (len_from_start_to_dest > 100000)
1455 {
1456 sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0);
1457 }
1458 else
1459 {
1460 sel = route_rect(try_harder ? 18 : 16, &r.lu, &r.rl, 25, 0);
1461 }
1462
1463 } // ------------ BICYCLE MODE -----------
1464
1465
1466
1467 else // ------------ CAR MODE -----------
1468 {
1469
1470 if (routing_mode == 0)
1471 {
1472 // normal highway routing
1473 // sel=route_rect(4, &r.lu, &r.rl, 25, 0);
1474 if (len_from_start_to_dest > 100000)
1475 {
1476 sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0); // ORIG: try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0
1477 }
1478 else
1479 {
1480 sel = route_rect(try_harder ? 8 : 7, &r.lu, &r.rl, 25, 0);
1481 }
1482
1483 // the route selection rectangle will be extened further, to find all routes (by 25%)
1484 #ifdef HAVE_API_ANDROID
1485 if (global_show_route_rectangles)
1486 {
1487 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);
1488 }
1489 #endif
1490 }
1491 else if (routing_mode == 1)
1492 {
1493 // normal roads routing (should take longer and use more roads)
1494 // sel=route_rect(6, &r.lu, &r.rl, 25, 0);
1495 sel = route_rect(try_harder ? 7 : 6, &r.lu, &r.rl, 25, 0);
1496
1497 #ifdef HAVE_API_ANDROID
1498 if (global_show_route_rectangles)
1499 {
1500 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);
1501 }
1502 #endif
1503 }
1504 else
1505 {
1506 // DEFAULT setting
1507 // normal highway routing
1508 // sel=route_rect(4, &r.lu, &r.rl, 25, 0);
1509 if (len_from_start_to_dest > 100000)
1510 {
1511 sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0); // ORIG: try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0
1512 }
1513 else
1514 {
1515 sel = route_rect(try_harder ? 8 : 7, &r.lu, &r.rl, 25, 0);
1516 }
1517
1518 // the route selection rectangle will be extened further, to find all routes (by 25%)
1519 #ifdef HAVE_API_ANDROID
1520 if (global_show_route_rectangles)
1521 {
1522 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);
1523 }
1524 #endif
1525
1526 }
1527 } // ------------ CAR MODE -----------
1528
1529
1530
1531
1532
1533
1534
1535 ret = sel;
1536 for (i = 0; i < count; i++)
1537 {
1538 // make 2 rectangles around every waypoint
1539 // 1 rect small but with high detail (every small street)
1540 // 1 rect a bit bigger but with lower detail
1541
1542 if (global_routing_engine != 1) // not OSRM routing
1543 {
1544 sel->next = route_rect(8, &c[i], &c[i], 0, try_harder ? 40000 : 8500); // DEFAULT = 0, 40000
1545 }
1546 else
1547 {
1548 if (i < (count -1))
1549 {
1550 // sel->next = route_rect(8, &c[i], &c[i + 1], 0, 2);
1551 sel->next = route_rect(8, &c[i], &c[i], 0, try_harder ? 140 : 220);
1552 }
1553 else
1554 {
1555 sel->next = route_rect(8, &c[i], &c[i], 0, try_harder ? 140 : 220);
1556 }
1557 }
1558 sel = sel->next;
1559 #ifdef HAVE_API_ANDROID
1560 if (global_show_route_rectangles)
1561 {
1562 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);
1563 }
1564 #endif
1565
1566 if (global_routing_engine != 1) // not OSRM routing
1567 {
1568 sel->next = route_rect(18, &c[i], &c[i], 0, try_harder ? 10000 : 2500); // DEFAULT = 0, 10000
1569 }
1570 else
1571 {
1572 if (i < (count -1))
1573 {
1574 // sel->next = route_rect(18, &c[i], &c[i + 1], 0, 2);
1575 sel->next = route_rect(18, &c[i], &c[i], 0, try_harder ? 100 : 120);
1576 }
1577 else
1578 {
1579 sel->next = route_rect(18, &c[i], &c[i], 0, try_harder ? 100 : 120);
1580 }
1581 }
1582 sel = sel->next;
1583 #ifdef HAVE_API_ANDROID
1584 if (global_show_route_rectangles)
1585 {
1586 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);
1587 }
1588 #endif
1589 }
1590 /* route_selection=ret; */
1591 return ret;
1592 }
1593
1594 /**
1595 * @brief Destroys a list of map selections
1596 *
1597 * @param sel Start of the list to be destroyed
1598 */
1599 static void route_free_selection(struct map_selection *sel)
1600 {
1601 __F_START__
1602
1603 struct map_selection *next;
1604 while (sel)
1605 {
1606 next = sel->next;
1607 g_free(sel);
1608 sel = next;
1609 }
1610 __F_END__
1611 }
1612
1613 static void route_clear_destinations(struct route *this_)
1614 {
1615 __F_START__
1616
1617 g_list_foreach(this_->destinations, (GFunc) route_info_free, NULL);
1618 g_list_free(this_->destinations);
1619 this_->destinations = NULL;
1620 __F_END__
1621 }
1622
1623 /**
1624 * @brief Sets the destination of a route
1625 *
1626 * This sets the destination of a route to the street nearest to the coordinates passed
1627 * and updates the route.
1628 *
1629 * @param this The route to set the destination for
1630 * @param dst Coordinates to set as destination
1631 * @param count: Number of destinations (last one is final)
1632 * @param async: If set, do routing asynchronously
1633 */
1634
1635 void route_set_destinations(struct route *this, struct pcoord *dst, int count, int async)
1636 {
1637 __F_START__
1638
1639 struct attr route_status;
1640 struct route_info *dsti;
1641 int i;
1642 route_status.type = attr_route_status;
1643
1644 //profile(0,NULL);
1645 route_clear_destinations(this);
1646
1647 if (dst && count)
1648 {
1649 for (i = 0; i < count; i++)
1650 {
1651 dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[i]);
1652
1653 // try harder
1654 if (dsti == NULL)
1655 {
1656 dsti = route_find_nearest_street_harder(this->vehicleprofile, this->ms, &dst[i], 16000);
1657 }
1658
1659 if (dsti)
1660 {
1661
1662 //dbg(0, "1: x y: %i %i\n", dst[i].x, dst[i].y);
1663 //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y);
1664 //dbg(0, "3: x y: %i %i\n", dsti->lp.x, dsti->lp.y);
1665 route_info_distances(dsti, dst->pro);
1666 this->destinations = g_list_append(this->destinations, dsti);
1667 }
1668 }
1669 route_status.u.num = route_status_destination_set;
1670 }
1671 else
1672 {
1673 route_status.u.num = route_status_no_destination;
1674 }
1675
1676
1677 dbg(0, "zzz3.1\n");
1678 //zzz3//
1679 // callback_list_call_attr_1(this->cbl2, attr_destination, this);
1680 route_set_attr(this, &route_status);
1681 //profile(1,"find_nearest_street");
1682
1683 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
1684 route_graph_destroy(this->graph);
1685 this->graph = NULL;
1686 this->current_dst = route_get_dst(this);
1687 this->try_harder = 0;
1688 route_path_update(this, 1, async);
1689 //profile(0,"end");
1690
1691 __F_END__
1692 }
1693
1694
1695
1696
1697 void route_add_destination_no_calc(struct route *this, struct pcoord *dst, int async)
1698 {
1699 __F_START__
1700
1701 // struct attr route_status;
1702 struct route_info *dsti;
1703 // route_status.type = attr_route_status;
1704
1705 dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[0]);
1706
1707 // try harder
1708 if (dsti == NULL)
1709 {
1710 dsti = route_find_nearest_street_harder(this->vehicleprofile, this->ms, &dst[0], 16000);
1711 }
1712
1713 if (dsti)
1714 {
1715 //dbg(0, "1: x y: %i %i\n", dst[0].x, dst[0].y);
1716 //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y);
1717 //dbg(0, "3: x y: %i %i\n", dsti->lp.x, dsti->lp.y);
1718
1719 route_info_distances(dsti, dst->pro);
1720 this->destinations = g_list_append(this->destinations, dsti);
1721
1722 }
1723
1724 this->try_harder = 0;
1725
1726 __F_END__
1727 }
1728
1729
1730
1731 void route_set_destination_no_calc(struct route *this, struct pcoord *dst, int async)
1732 {
1733 __F_START__
1734
1735 // route_set_destinations(this, dst, dst ? 1 : 0, async);
1736
1737 route_clear_destinations(this);
1738 route_add_destination_no_calc(this, dst, async);
1739
1740 __F_END__
1741 }
1742
1743
1744
1745 void route_after_destination_start_calc(struct route *this, int async)
1746 {
1747 __F_START__
1748
1749 struct attr route_status;
1750 route_status.u.num = route_status_destination_set;
1751
1752 dbg(0, "zzz3.1\n");
1753 //zzz3//
1754 // callback_list_call_attr_1(this->cbl2, attr_destination, this);
1755 route_set_attr(this, &route_status);
1756 //profile(1,"find_nearest_street");
1757
1758 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
1759 route_graph_destroy(this->graph);
1760 this->graph = NULL;
1761 this->current_dst = route_get_dst(this);
1762 this->try_harder = 0;
1763 route_path_update(this, 1, async);
1764
1765 __F_END__
1766 }
1767
1768
1769
1770
1771
1772
1773
1774 void route_add_destination(struct route *this, struct pcoord *dst, int async)
1775 {
1776 __F_START__
1777
1778 struct attr route_status;
1779 struct route_info *dsti;
1780 route_status.type = attr_route_status;
1781
1782 dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[0]);
1783
1784 // try harder
1785 if (dsti == NULL)
1786 {
1787 dsti = route_find_nearest_street_harder(this->vehicleprofile, this->ms, &dst[0], 16000);
1788 }
1789
1790 if (dsti)
1791 {
1792 //dbg(0, "1: x y: %i %i\n", dst[0].x, dst[0].y);
1793 //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y);
1794 //dbg(0, "3: x y: %i %i\n", dsti->lp.x, dsti->lp.y);
1795
1796 route_info_distances(dsti, dst->pro);
1797 this->destinations = g_list_append(this->destinations, dsti);
1798
1799 route_status.u.num = route_status_destination_set;
1800 }
1801
1802 dbg(0, "zzz3.2\n");
1803 //zzz3//
1804 // callback_list_call_attr_1(this->cbl2, attr_destination, this);
1805 route_set_attr(this, &route_status);
1806
1807 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
1808 route_graph_destroy(this->graph);
1809 this->graph = NULL;
1810 this->current_dst = route_get_dst(this);
1811 this->try_harder = 0;
1812 route_path_update(this, 1, async);
1813 __F_END__
1814 }
1815
1816 int route_get_destinations(struct route *this, struct pcoord *pc, int count)
1817 {
1818 __F_START__
1819
1820 int ret = 0;
1821 GList *l = this->destinations;
1822 while (l && ret < count)
1823 {
1824 struct route_info *dst = l->data;
1825 pc->x = dst->c.x;
1826 pc->y = dst->c.y;
1827 pc->pro = projection_mg; /* FIXME */
1828 pc++;
1829 ret++;
1830 l = g_list_next(l);
1831 }
1832
1833 return2 ret;
1834
1835 __F_END__
1836
1837 }
1838
1839 void route_set_destination(struct route *this, struct pcoord *dst, int async)
1840 {
1841 __F_START__
1842
1843 route_set_destinations(this, dst, dst ? 1 : 0, async);
1844
1845 __F_END__
1846 }
1847
1848 void route_remove_waypoint(struct route *this)
1849 {
1850 __F_START__
1851
1852 struct route_path *path = this->path2;
1853 this->destinations = g_list_remove(this->destinations, this->destinations->data);
1854 this->path2 = this->path2->next;
1855 route_path_destroy(path, 0);
1856
1857 if (!this->destinations)
1858 {
1859 return2;
1860 }
1861
1862 route_graph_reset(this->graph);
1863 this->current_dst = this->destinations->data;
1864
1865 route_graph_flood(this->graph, this->current_dst, this->pos, this->vehicleprofile, this->route_graph_flood_done_cb);
1866
1867 __F_END__
1868
1869 }
1870
1871 /**
1872 * @brief Gets the route_graph_point with the specified coordinates
1873 *
1874 * @param this The route in which to search
1875 * @param c Coordinates to search for
1876 * @param last The last route graph point returned to iterate over multiple points with the same coordinates
1877 * @return The point at the specified coordinates or NULL if not found
1878 */
1879 static struct route_graph_point *
1880 route_graph_get_point_next(struct route_graph *this, struct coord *c, struct route_graph_point *last)
1881 {
1882 //// dbg(0, "enter\n");
1883
1884 struct route_graph_point *p;
1885 int seen = 0, hashval = HASHCOORD(c);
1886 p = this->hash[hashval];
1887 while (p)
1888 {
1889 if (p->c.x == c->x && p->c.y == c->y)
1890 {
1891 if (!last || seen)
1892 return p;
1893
1894 if (p == last)
1895 seen = 1;
1896
1897 }
1898 p = p->hash_next;
1899 }
1900 return NULL;
1901 }
1902
1903 static struct route_graph_point *
1904 route_graph_get_point(struct route_graph *this, struct coord *c)
1905 {
1906 //// dbg(0, "enter\n");
1907
1908 return route_graph_get_point_next(this, c, NULL);
1909 }
1910
1911 /**
1912 * @brief Gets the last route_graph_point with the specified coordinates
1913 *
1914 * @param this The route in which to search
1915 * @param c Coordinates to search for
1916 * @return The point at the specified coordinates or NULL if not found
1917 */
1918 static struct route_graph_point *
1919 route_graph_get_point_last(struct route_graph *this, struct coord *c)
1920 {
1921 //// dbg(0, "enter\n");
1922
1923 struct route_graph_point *p, *ret = NULL;
1924 int hashval = HASHCOORD(c);
1925 p = this->hash[hashval];
1926 while (p)
1927 {
1928 if (p->c.x == c->x && p->c.y == c->y)
1929 ret = p;
1930 p = p->hash_next;
1931 }
1932 return ret;
1933 }
1934
1935 /**
1936 * @brief Create a new point for the route graph with the specified coordinates
1937 *
1938 * @param this The route to insert the point into
1939 * @param f The coordinates at which the point should be created
1940 * @return The point created
1941 */
1942 static struct route_graph_point *
1943 route_graph_point_new(struct route_graph *this, struct coord *f)
1944 {
1945 //// dbg(0, "enter\n");
1946
1947 int hashval;
1948 struct route_graph_point *p;
1949
1950 hashval = HASHCOORD(f);
1951 //if (debug_route)
1952 // printf("p (0x%x,0x%x)\n", f->x, f->y);
1953
1954 p=g_slice_new0(struct route_graph_point);
1955 //global_route_memory_size = global_route_memory_size + sizeof(struct route_graph_point);
1956 //dbg(0,"(A)route mem=%lu\n", global_route_memory_size);
1957
1958 p->hash_next = this->hash[hashval];
1959 this->hash[hashval] = p;
1960 p->c = *f;
1961
1962 return p;
1963 }
1964
1965 /**
1966 * @brief Inserts a point into the route graph at the specified coordinates
1967 *
1968 * This will insert a point into the route graph at the coordinates passed in f.
1969 * Note that the point is not yet linked to any segments.
1970 *
1971 * @param this The route to insert the point into
1972 * @param f The coordinates at which the point should be inserted
1973 * @return The point inserted or NULL on failure
1974 */
1975 static struct route_graph_point *
1976 route_graph_add_point(struct route_graph *this, struct coord *f)
1977 {
1978 //// dbg(0, "enter\n");
1979
1980 struct route_graph_point *p;
1981
1982 p = route_graph_get_point(this, f);
1983
1984 if (!p)
1985 {
1986 p = route_graph_point_new(this, f);
1987 }
1988
1989 return p;
1990 }
1991
1992 /**
1993 * @brief Frees all the memory used for points in the route graph passed
1994 *
1995 * @param this The route graph to delete all points from
1996 */
1997 static void route_graph_free_points(struct route_graph *this)
1998 {
1999 //// dbg(0, "enter\n");
2000
2001 struct route_graph_point *curr, *next;
2002 int i;
2003 for (i = 0; i < HASH_SIZE; i++)
2004 {
2005 curr = this->hash[i];
2006 while (curr)
2007 {
2008 next = curr->hash_next;
2009 g_slice_free(struct route_graph_point, curr);
2010 //global_route_memory_size = global_route_memory_size - sizeof(struct route_graph_point);
2011 //dbg(0,"(F)route mem=%lu\n", global_route_memory_size);
2012
2013 curr = next;
2014 }
2015 this->hash[i] = NULL;
2016 }
2017 }
2018
2019 /**
2020 * @brief Resets all nodes
2021 *
2022 * @param this The route graph to reset
2023 */
2024 static void route_graph_reset(struct route_graph *this)
2025 {
2026 __F_START__
2027
2028 struct route_graph_point *curr;
2029 struct route_graph_segment *seg;
2030
2031 int i;
2032 for (i = 0; i < HASH_SIZE; i++)
2033 {
2034 curr = this->hash[i];
2035 while (curr)
2036 {
2037 seg = curr->start;
2038 while (seg)
2039 {
2040 seg->end_from_seg = NULL;
2041 seg->start_from_seg = NULL;
2042 seg->seg_end_out_cost = INT_MAX;
2043 seg->seg_start_out_cost = INT_MAX;
2044 seg = seg->start_next;
2045 }
2046
2047
2048 seg = curr->end;
2049 // overkill ?
2050 while (seg)
2051 {
2052 seg->end_from_seg = NULL;
2053 seg->start_from_seg = NULL;
2054 seg->seg_end_out_cost = INT_MAX;
2055 seg->seg_start_out_cost = INT_MAX;
2056 seg = seg->end_next;
2057 }
2058
2059 curr=curr->hash_next;
2060 }
2061 }
2062
2063 __F_END__
2064 }
2065
2066 /**
2067 * @brief Returns the position of a certain field appended to a route graph segment
2068 *
2069 * This function returns a pointer to a field that is appended to a route graph
2070 * segment.
2071 *
2072 * @param seg The route graph segment the field is appended to
2073 * @param type Type of the field that should be returned
2074 * @return A pointer to a field of a certain type, or NULL if no such field is present
2075 */
2076 static void *
2077 route_segment_data_field_pos(struct route_segment_data *seg, enum attr_type type)
2078 {
2079 // // dbg(0, "enter\n");
2080
2081 unsigned char *ptr;
2082
2083 ptr = ((unsigned char*) seg) + sizeof(struct route_segment_data);
2084
2085 if (seg->flags & NAVIT_AF_SPEED_LIMIT)
2086 {
2087 if (type == attr_maxspeed)
2088 return (void*) ptr;
2089
2090 ptr += sizeof(int);
2091 }
2092 if (seg->flags & NAVIT_AF_SEGMENTED)
2093 {
2094 if (type == attr_offset)
2095 return (void*) ptr;
2096
2097 ptr += sizeof(int);
2098 }
2099 if (seg->flags & NAVIT_AF_SIZE_OR_WEIGHT_LIMIT)
2100 {
2101 if (type == attr_vehicle_width)
2102 return (void*) ptr;
2103
2104 ptr += sizeof(struct size_weight_limit);
2105 }
2106 if (seg->flags & NAVIT_AF_DANGEROUS_GOODS)
2107 {
2108 if (type == attr_vehicle_dangerous_goods)
2109 return (void*) ptr;
2110
2111 ptr += sizeof(int);
2112 }
2113 return NULL;
2114 }
2115
2116 /**
2117 * @brief Calculates the size of a route_segment_data struct with given flags
2118 *
2119 * @param flags The flags of the route_segment_data
2120 */
2121 static int route_segment_data_size(int flags)
2122 {
2123 //// dbg(0, "enter\n");
2124
2125 int ret = sizeof(struct route_segment_data);
2126
2127 if (flags & NAVIT_AF_SPEED_LIMIT)
2128 ret += sizeof(int);
2129
2130 if (flags & NAVIT_AF_SEGMENTED)
2131 ret += sizeof(int);
2132
2133 if (flags & NAVIT_AF_SIZE_OR_WEIGHT_LIMIT)
2134 ret += sizeof(struct size_weight_limit);
2135
2136 if (flags & NAVIT_AF_DANGEROUS_GOODS)
2137 ret += sizeof(int);
2138
2139 return ret;
2140 }
2141
2142 static int route_graph_segment_is_duplicate(struct route_graph_point *start, struct route_graph_segment_data *data)
2143 {
2144 //// dbg(0, "enter\n");
2145
2146 struct route_graph_segment *s;
2147 s = start->start;
2148 while (s)
2149 {
2150 if (item_is_equal(*data->item, s->data.item))
2151 {
2152 if (data->flags & NAVIT_AF_SEGMENTED)
2153 {
2154 if (RSD_OFFSET(&s->data) == data->offset)
2155 {
2156 return 1;
2157 }
2158 }
2159 else
2160 return 1;
2161 }
2162 s = s->start_next;
2163 }
2164 return 0;
2165 }
2166
2167 /**
2168 * @brief Inserts a new segment into the route graph
2169 *
2170 * This function performs a check if a segment for the item specified already exists, and inserts
2171 * a new segment representing this item if it does not.
2172 *
2173 * @param this The route graph to insert the segment into
2174 * @param start The graph point which should be connected to the start of this segment
2175 * @param end The graph point which should be connected to the end of this segment
2176 * @param len The length of this segment
2177 * @param item The item that is represented by this segment
2178 * @param flags Flags for this segment
2179 * @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
2180 * @param maxspeed The maximum speed allowed on this segment in km/h. -1 if not known.
2181 */
2182 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)
2183 {
2184 //// dbg(0, "enter\n");
2185
2186 struct route_graph_segment *s;
2187 int size;
2188
2189 size = sizeof(struct route_graph_segment) - sizeof(struct route_segment_data) + route_segment_data_size(data->flags);
2190
2191 s = g_slice_alloc0(size);
2192 //global_route_memory_size = global_route_memory_size + size;
2193 //dbg(0,"(A)route mem=%lu\n", global_route_memory_size);
2194
2195 if (!s)
2196 {
2197 printf("%s:Out of memory\n", __FUNCTION__);
2198 return;
2199 }
2200
2201 s->seg_end_out_cost = INT_MAX;
2202 s->seg_start_out_cost = INT_MAX;
2203 s->start = start;
2204 s->start_next = start->start;
2205 start->start = s;
2206
2207 s->end = end;
2208 s->end_next = end->end;
2209 end->end = s;
2210
2211 dbg_assert(data->len >= 0);
2212
2213 s->data.len = data->len;
2214 s->data.item = *data->item;
2215 s->data.flags = data->flags;
2216
2217 // save coords to calculate road angles later -------------
2218 s->c_start_plus_1.x = 0;
2219 s->c_start_plus_1.y = 0;
2220 s->c_end_minus_1.x = 0;
2221 s->c_end_minus_1.y = 0;
2222 // save coords to calculate road angles later -------------
2223
2224 if (data->flags & NAVIT_AF_SPEED_LIMIT)
2225 RSD_MAXSPEED(&s->data) = data->maxspeed;
2226
2227 if (data->flags & NAVIT_AF_SEGMENTED)
2228 RSD_OFFSET(&s->data) = data->offset;
2229
2230 if (data->flags & NAVIT_AF_SIZE_OR_WEIGHT_LIMIT)
2231 RSD_SIZE_WEIGHT(&s->data) = data->size_weight;
2232
2233 if (data->flags & NAVIT_AF_DANGEROUS_GOODS)
2234 RSD_DANGEROUS_GOODS(&s->data) = data->dangerous_goods;
2235
2236 s->next = this->route_segments;
2237 this->route_segments = s;
2238
2239 //if (debug_route)
2240 //{
2241 // printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
2242 //}
2243 }
2244
2245 static void route_graph_add_segment_with_coords(struct route_graph *this, struct route_graph_point *start, struct route_graph_point *end, struct route_graph_segment_data *data, struct coord *c2, struct coord *c98)
2246 {
2247 //// dbg(0, "enter\n");
2248
2249 struct route_graph_segment *s;
2250 int size;
2251
2252 size = sizeof(struct route_graph_segment) - sizeof(struct route_segment_data) + route_segment_data_size(data->flags);
2253
2254 s = g_slice_alloc0(size);
2255 //global_route_memory_size = global_route_memory_size + size;
2256 //dbg(0,"(A)route mem=%lu\n", global_route_memory_size);
2257
2258 if (!s)
2259 {
2260 printf("%s:Out of memory\n", __FUNCTION__);
2261 return;
2262 }
2263
2264 s->seg_end_out_cost = INT_MAX;
2265 s->seg_start_out_cost = INT_MAX;
2266 s->start = start;
2267 s->start_next = start->start;
2268 start->start = s;
2269
2270 s->end = end;
2271 s->end_next = end->end;
2272 end->end = s;
2273
2274 dbg_assert(data->len >= 0);
2275
2276 s->data.len = data->len;
2277 s->data.item = *data->item;
2278 s->data.flags = data->flags;
2279
2280 // save coords to calculate road angles later -------------
2281 s->c_start_plus_1.x = c2->x;
2282 s->c_start_plus_1.y = c2->y;
2283 s->c_end_minus_1.x = c98->x;
2284 s->c_end_minus_1.y = c98->y;
2285 // save coords to calculate road angles later -------------
2286
2287 if (data->flags & NAVIT_AF_SPEED_LIMIT)
2288 RSD_MAXSPEED(&s->data) = data->maxspeed;
2289
2290 if (data->flags & NAVIT_AF_SEGMENTED)
2291 RSD_OFFSET(&s->data) = data->offset;
2292
2293 if (data->flags & NAVIT_AF_SIZE_OR_WEIGHT_LIMIT)
2294 RSD_SIZE_WEIGHT(&s->data) = data->size_weight;
2295
2296 if (data->flags & NAVIT_AF_DANGEROUS_GOODS)
2297 RSD_DANGEROUS_GOODS(&s->data) = data->dangerous_goods;
2298
2299 s->next = this->route_segments;
2300 this->route_segments = s;
2301 }
2302
2303
2304 /**
2305 * @brief Gets all the coordinates of an item
2306 *
2307 * This will get all the coordinates of the item i and return them in c,
2308 * up to max coordinates. Additionally it is possible to limit the coordinates
2309 * returned to all the coordinates of the item between the two coordinates
2310 * "start" and "end".
2311 *
2312 * @important Make sure that whatever c points to has enough memory allocated
2313 * @important to hold max coordinates!
2314 *
2315 * @param i The item to get the coordinates of
2316 * @param c Pointer to memory allocated for holding the coordinates
2317 * @param max Maximum number of coordinates to return
2318 * @param start First coordinate to get
2319 * @param end Last coordinate to get
2320 * @return The number of coordinates returned
2321 */
2322 static int get_item_seg_coords(struct item *i, struct coord *c, int max, struct coord *start, struct coord *end)
2323 {
2324 //// dbg(0, "enter\n");
2325
2326 struct map_rect *mr;
2327 struct item *item;
2328 int rc = 0, p = 0;
2329 struct coord c1;
2330 mr = map_rect_new(i->map, NULL);
2331
2332 if (!mr)
2333 {
2334 return 0;
2335 }
2336
2337 item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
2338
2339 if (item)
2340 {
2341 rc = item_coord_get(item, &c1, 1);
2342
2343 while (rc && (c1.x != start->x || c1.y != start->y))
2344 {
2345 rc = item_coord_get(item, &c1, 1);
2346 }
2347
2348 while (rc && p < max)
2349 {
2350 c[p++] = c1;
2351 if (c1.x == end->x && c1.y == end->y)
2352 {
2353 break;
2354 }
2355 rc = item_coord_get(item, &c1, 1);
2356 }
2357 }
2358 map_rect_destroy(mr);
2359 return p;
2360 }
2361
2362 /**
2363 * @brief Returns and removes one segment from a path
2364 *
2365 * @param path The path to take the segment from
2366 * @param item The item whose segment to remove
2367 * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
2368 * @return The segment removed
2369 */
2370 static struct route_path_segment *
2371 route_extract_segment_from_path(struct route_path *path, struct item *item, int offset)
2372 {
2373 //// dbg(0, "enter\n");
2374
2375 int soffset;
2376 struct route_path_segment *sp = NULL, *s;
2377 s = path->path;
2378
2379 while (s)
2380 {
2381 if (item_is_equal(s->data->item, *item))
2382 {
2383 if (s->data->flags & NAVIT_AF_SEGMENTED)
2384 soffset = RSD_OFFSET(s->data);
2385 else
2386 soffset = 1;
2387
2388 if (soffset == offset)
2389 {
2390 if (sp)
2391 {
2392 sp->next = s->next;
2393 break;
2394 }
2395 else
2396 {
2397 path->path = s->next;
2398 break;
2399 }
2400 }
2401 }
2402 sp = s;
2403 s = s->next;
2404 }
2405
2406 // if (s)
2407 // item_hash_remove(path->path_hash, item);
2408
2409 return s;
2410 }
2411
2412 /**
2413 * @brief Adds a segment and the end of a path
2414 *
2415 * @param this The path to add the segment to
2416 * @param segment The segment to add
2417 */
2418 static void route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
2419 {
2420 //// dbg(0, "enter\n");
2421
2422 if (!this->path)
2423 this->path = segment;
2424
2425 if (this->path_last)
2426 this->path_last->next = segment;
2427
2428 this->path_last = segment;
2429 }
2430
2431 /**
2432 * @brief Adds a two coordinate line to a path
2433 *
2434 * This adds a new line to a path, creating a new segment for it.
2435 *
2436 * @param this The path to add the item to
2437 * @param start coordinate to add to the start of the item. If none should be added, make this NULL.
2438 * @param end coordinate to add to the end of the item. If none should be added, make this NULL.
2439 * @param len The length of the item
2440 */
2441 static void route_path_add_line(struct route_path *this, struct coord *start, struct coord *end, int len)
2442 {
2443 //dbg(0, "enter\n");
2444
2445 int ccnt = 2;
2446 struct route_path_segment *segment;
2447 int seg_size, seg_dat_size;
2448
2449 //dbg(0, "line from 0x%x,0x%x-0x%x,0x%x\n", start->x, start->y, end->x, end->y);
2450
2451 seg_size = sizeof(*segment) + sizeof(struct coord) * ccnt;
2452 seg_dat_size = sizeof(struct route_segment_data);
2453 segment = g_malloc0(seg_size + seg_dat_size);
2454 //global_route_memory_size = global_route_memory_size + seg_size + seg_dat_size;
2455 //dbg(0,"route mem=%lu\n", global_route_memory_size);
2456
2457 segment->data = (struct route_segment_data *) ((char *) segment + seg_size);
2458 segment->ncoords = ccnt;
2459 segment->direction = 0;
2460 segment->c[0] = *start;
2461 segment->c[1] = *end;
2462 segment->data->len = len;
2463 route_path_add_segment(this, segment);
2464 }
2465
2466
2467 static void route_path_add_line_as_waypoint(struct route_path *this, struct coord *start, struct coord *end, int len)
2468 {
2469 //dbg(0, "enter\n");
2470
2471 int ccnt = 2;
2472 struct route_path_segment *segment;
2473 int seg_size, seg_dat_size;
2474
2475 //dbg(0, "line from 0x%x,0x%x-0x%x,0x%x\n", start->x, start->y, end->x, end->y);
2476
2477 seg_size = sizeof(*segment) + sizeof(struct coord) * ccnt;
2478 seg_dat_size = sizeof(struct route_segment_data);
2479 segment = g_malloc0(seg_size + seg_dat_size);
2480 //global_route_memory_size = global_route_memory_size + seg_size + seg_dat_size;
2481 //dbg(0,"route mem=%lu\n", global_route_memory_size);
2482
2483 segment->data = (struct route_segment_data *) ((char *) segment + seg_size);
2484 segment->ncoords = ccnt;
2485 segment->direction = 0;
2486 segment->c[0] = *start;
2487 segment->c[1] = *end;
2488 segment->data->len = len;
2489
2490 dbg(0, "RPNEW:WW:add type_street_route_waypoint prev type=%s\n", item_to_name(segment->data->item.type));
2491 segment->data->item.type = type_street_route_waypoint; // mark waypoint item
2492
2493 route_path_add_segment(this, segment);
2494 }
2495
2496 /**
2497 * @brief Inserts a new item into the path
2498 *
2499 * This function does almost the same as "route_path_add_item()", but identifies
2500 * the item to add by a segment from the route graph. Another difference is that it "copies" the
2501 * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
2502 * be added to the route path, not all segments of the item.
2503 *
2504 * The function can be sped up by passing an old path already containing this segment in oldpath -
2505 * the segment will then be extracted from this old path. Please note that in this case the direction
2506 * parameter has no effect.
2507 *
2508 * @param this The path to add the item to
2509 * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
2510 * @param rgs Segment of the route graph that should be "copied" to the route path
2511 * @param dir Order in which to add the coordinates. See route_path_add_item()
2512 * @param pos Information about start point if this is the first segment
2513 * @param dst Information about end point if this is the last segment
2514 */
2515 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)
2516 {
2517 //// dbg(0, "enter\n");
2518
2519 struct route_path_segment *segment = NULL;
2520 int i, ccnt, extra = 0, ret = 0;
2521 struct coord *c, *cd, ca[2048];
2522 int offset = 1;
2523 int seg_size, seg_dat_size;
2524 int len = rgs->data.len;
2525 if (rgs->data.flags & NAVIT_AF_SEGMENTED)
2526 {
2527 offset = RSD_OFFSET(&rgs->data);
2528 }
2529
2530
2531 if (oldpath)
2532 {
2533 segment = item_hash_lookup(oldpath->path_hash, &rgs->data.item);
2534 if (segment && !(dst && segment->direction != dir)) // testen als het het laatste segment betreft of dir wel gelijk is
2535 {
2536 segment = route_extract_segment_from_path(oldpath, &rgs->data.item, offset);
2537 if (segment)
2538 {
2539 ret = 1;
2540 if (!pos)
2541 {
2542 segment->data->len = len;
2543 segment->next = NULL;
2544 item_hash_insert(this->path_hash, &rgs->data.item, segment);
2545 route_path_add_segment(this, segment);
2546 return ret;
2547 }
2548 }
2549 }
2550 }
2551
2552 if (pos)
2553 {
2554 if (dst)
2555 {
2556 extra = 2;
2557 if (dst->lenneg >= pos->lenneg)
2558 {
2559 dir = 1;
2560 ccnt = dst->pos - pos->pos;
2561 c = pos->street->c + pos->pos + 1;
2562 len = dst->lenneg - pos->lenneg;
2563 }
2564 else
2565 {
2566 dir = -1;
2567 ccnt = pos->pos - dst->pos;
2568 c = pos->street->c + dst->pos + 1;
2569 len = pos->lenneg - dst->lenneg;
2570 }
2571 }
2572 else
2573 {
2574 extra = 1;
2575 //dbg(1, "pos dir=%d\n", dir);
2576 //dbg(1, "pos pos=%d\n", pos->pos);
2577 //dbg(1, "pos count=%d\n", pos->street->count);
2578 if (dir > 0)
2579 {
2580 c = pos->street->c + pos->pos + 1;
2581 ccnt = pos->street->count - pos->pos - 1;
2582 len = pos->lenpos;
2583 }
2584 else
2585 {
2586 c = pos->street->c;
2587 ccnt = pos->pos + 1;
2588 len = pos->lenneg;
2589 }
2590 }
2591 pos->dir = dir;
2592 }
2593 else if (dst)
2594 {
2595 extra = 1;
2596 //dbg(1, "dst dir=%d\n", dir);
2597 //dbg(1, "dst pos=%d\n", dst->pos);
2598 if (dir > 0)
2599 {
2600 c = dst->street->c;
2601 ccnt = dst->pos + 1;
2602 len = dst->lenneg;
2603 }
2604 else
2605 {
2606 c = dst->street->c + dst->pos + 1;
2607 ccnt = dst->street->count - dst->pos - 1;
2608 len = dst->lenpos;
2609 }
2610 }
2611 else
2612 {
2613 ccnt = get_item_seg_coords(&rgs->data.item, ca, 2047, &rgs->start->c, &rgs->end->c);
2614 c = ca;
2615 }
2616 seg_size = sizeof(*segment) + sizeof(struct coord) * (ccnt + extra);
2617 seg_dat_size = route_segment_data_size(rgs->data.flags);
2618 segment = g_malloc0(seg_size + seg_dat_size);
2619 //global_route_memory_size = global_route_memory_size + seg_size + seg_dat_size;
2620 //dbg(0,"route mem=%lu\n", global_route_memory_size);
2621
2622 segment->data = (struct route_segment_data *) ((char *) segment + seg_size);
2623 segment->direction = dir;
2624 cd = segment->c;
2625
2626 if (pos && (c[0].x != pos->lp.x || c[0].y != pos->lp.y))
2627 *cd++ = pos->lp;
2628
2629 if (dir < 0)
2630 c += ccnt - 1;
2631
2632 for (i = 0; i < ccnt; i++)
2633 {
2634 *cd++ = *c;
2635 c += dir;
2636 }
2637
2638 segment->ncoords += ccnt;
2639
2640 if (dst && (cd[-1].x != dst->lp.x || cd[-1].y != dst->lp.y))
2641 *cd++ = dst->lp;
2642
2643 segment->ncoords = cd - segment->c;
2644
2645 if (segment->ncoords <= 1)
2646 {
2647 g_free(segment);
2648 return 1;
2649 }
2650
2651 /* We check if the route graph segment is part of a roundabout here, because this
2652 * only matters for route graph segments which form parts of the route path */
2653 if (!(rgs->data.flags & NAVIT_AF_ROUNDABOUT))
2654 {
2655 // We identified this roundabout earlier
2656 route_check_roundabout(rgs, 13, (dir < 1), NULL); // 13 z8z8
2657 }
2658
2659 memcpy(segment->data, &rgs->data, seg_dat_size);
2660 segment->data->len = len;
2661 segment->next = NULL;
2662 item_hash_insert(this->path_hash, &rgs->data.item, segment);
2663
2664 route_path_add_segment(this, segment);
2665
2666 return ret;
2667 }
2668
2669 /**
2670 * @brief Destroys all segments of a route graph
2671 *
2672 * @param this The graph to destroy all segments from
2673 */
2674 static void route_graph_free_segments(struct route_graph *this)
2675 {
2676 //// dbg(0, "enter\n");
2677
2678 struct route_graph_segment *curr, *next;
2679 int size;
2680 curr = this->route_segments;
2681 while (curr)
2682 {
2683 next = curr->next;
2684 size = sizeof(struct route_graph_segment) - sizeof(struct route_segment_data) + route_segment_data_size(curr->data.flags);
2685 g_slice_free1(size, curr);
2686 //global_route_memory_size = global_route_memory_size - size;
2687 //dbg(0,"(F)route mem=%lu\n", global_route_memory_size);
2688 curr = next;
2689 }
2690 this->route_segments = NULL;
2691 }
2692
2693 /**
2694 * @brief Destroys a route graph
2695 *
2696 * @param this The route graph to be destroyed
2697 */
2698 void route_graph_destroy(struct route_graph *this)
2699 {
2700 __F_START__
2701
2702 if (this)
2703 {
2704 route_graph_build_done(this, 1);
2705 route_graph_free_points(this);
2706 route_graph_free_segments(this);
2707 g_free(this);
2708 }
2709
2710 __F_END__
2711 }
2712
2713 /**
2714 * @brief Returns the estimated speed on a segment
2715 *
2716 * This function returns the estimated speed to be driven on a segment, 0=not passable
2717 *
2718 * @param profile The routing preferences
2719 * @param over The segment which is passed
2720 * @param dist A traffic distortion if applicable
2721 * @return The estimated speed
2722 */
2723 static int route_seg_speed(struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist)
2724 {
2725 // dbg(0, "enter\n");
2726
2727 struct roadprofile *roadprofile = vehicleprofile_get_roadprofile(profile, over->item.type);
2728 int speed, maxspeed;
2729
2730 if (!roadprofile || !roadprofile->route_weight)
2731 {
2732 return 0;
2733 }
2734
2735 /* maxspeed_handling: 0=always, 1 only if maxspeed restricts the speed, 2 never */
2736 speed = roadprofile->route_weight;
2737
2738 if (profile->maxspeed_handling != 2) // "0" or "1"
2739 {
2740 if (over->flags & NAVIT_AF_SPEED_LIMIT)
2741 {
2742 maxspeed = RSD_MAXSPEED(over);
2743
2744 if (!profile->maxspeed_handling) // "0"
2745 {
2746 speed = maxspeed;
2747 }
2748 }
2749 else
2750 {
2751 maxspeed = INT_MAX;
2752 }
2753
2754 if (dist && maxspeed > dist->maxspeed)
2755 {
2756 maxspeed = dist->maxspeed;
2757 }
2758
2759 if (maxspeed != INT_MAX && (profile->maxspeed_handling != 1 || maxspeed < speed))
2760 {
2761 speed = maxspeed;
2762 }
2763 }
2764
2765 // -- bicycle mode START --
2766 if ((global_vehicle_profile == 1) || (global_vehicle_profile == 2))
2767 {
2768 }
2769 else
2770 {
2771 if (speed < 150) // in km/h
2772 {
2773 // to calcuate the time to drive on street, speed should be reduced to <global_road_speed_factor> (~ 85%)
2774 speed = (int)((float)speed * global_road_speed_factor);
2775 }
2776 }
2777
2778
2779 if (over->flags & NAVIT_AF_DANGEROUS_GOODS)
2780 {
2781 if (profile->dangerous_goods & RSD_DANGEROUS_GOODS(over))
2782 {
2783 return 0;
2784 }
2785 }
2786
2787 if (over->flags & NAVIT_AF_SIZE_OR_WEIGHT_LIMIT)
2788 {
2789 struct size_weight_limit *size_weight = &RSD_SIZE_WEIGHT(over);
2790
2791 if (size_weight->width != -1 && profile->width != -1 && profile->width > size_weight->width)
2792 return 0;
2793
2794 if (size_weight->height != -1 && profile->height != -1 && profile->height > size_weight->height)
2795 return 0;
2796
2797 if (size_weight->length != -1 && profile->length != -1 && profile->length > size_weight->length)
2798 return 0;
2799
2800 if (size_weight->weight != -1 && profile->weight != -1 && profile->weight > size_weight->weight)
2801 return 0;
2802
2803 if (size_weight->axle_weight != -1 && profile->axle_weight != -1 && profile->axle_weight > size_weight->axle_weight)
2804 return 0;
2805
2806 }
2807
2808 return speed;
2809 }
2810
2811
2812 static int route_seg_speed_real(struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist)
2813 {
2814 // dbg(0, "enter\n");
2815
2816 struct roadprofile *roadprofile = vehicleprofile_get_roadprofile(profile, over->item.type);
2817 int speed, maxspeed;
2818
2819 if (!roadprofile || !roadprofile->route_weight)
2820 {
2821 return 0;
2822 }
2823
2824 /* maxspeed_handling: 0=always, 1 only if maxspeed restricts the speed, 2 never */
2825 speed = roadprofile->route_weight;
2826
2827 if (profile->maxspeed_handling != 2) // "0" or "1"
2828 {
2829 if (over->flags & NAVIT_AF_SPEED_LIMIT)
2830 {
2831 maxspeed = RSD_MAXSPEED(over);
2832
2833 if (!profile->maxspeed_handling) // "0"
2834 {
2835 speed = maxspeed;
2836 }
2837 }
2838 else
2839 {
2840 maxspeed = INT_MAX;
2841 }
2842
2843 if (dist && maxspeed > dist->maxspeed)
2844 {
2845 maxspeed = dist->maxspeed;
2846 }
2847
2848 if (maxspeed != INT_MAX && (profile->maxspeed_handling != 1 || maxspeed < speed))
2849 {
2850 speed = maxspeed;
2851 }
2852 }
2853
2854 if (over->flags & NAVIT_AF_DANGEROUS_GOODS)
2855 {
2856 if (profile->dangerous_goods & RSD_DANGEROUS_GOODS(over))
2857 {
2858 return 0;
2859 }
2860 }
2861
2862 if (over->flags & NAVIT_AF_SIZE_OR_WEIGHT_LIMIT)
2863 {
2864 struct size_weight_limit *size_weight = &RSD_SIZE_WEIGHT(over);
2865
2866 if (size_weight->width != -1 && profile->width != -1 && profile->width > size_weight->width)
2867 return 0;
2868
2869 if (size_weight->height != -1 && profile->height != -1 && profile->height > size_weight->height)
2870 return 0;
2871
2872 if (size_weight->length != -1 && profile->length != -1 && profile->length > size_weight->length)
2873 return 0;
2874
2875 if (size_weight->weight != -1 && profile->weight != -1 && profile->weight > size_weight->weight)
2876 return 0;
2877
2878 if (size_weight->axle_weight != -1 && profile->axle_weight != -1 && profile->axle_weight > size_weight->axle_weight)
2879 return 0;
2880
2881 }
2882
2883 return speed;
2884 }
2885
2886
2887 /**
2888 * @brief Returns the time needed to drive len on item
2889 *
2890 * This function returns the time needed to drive len meters on
2891 * the item passed in item in tenth of seconds.
2892 *
2893 * @param profile The routing preferences
2894 * @param over The segment which is passed
2895 * @param dist A traffic distortion if applicable
2896 * @return The time needed to drive len on item in thenth of seconds
2897 */
2898 static int route_time_seg(struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist)
2899 {
2900 // dbg(0, "enter\n");
2901
2902 int speed = route_seg_speed(profile, over, dist);
2903 if (!speed)
2904 {
2905 return INT_MAX;
2906 }
2907 return over->len * 36 / speed + (dist ? dist->delay : 0);
2908 }
2909
2910 static int route_get_traffic_distortion(struct route_graph_segment *seg, struct route_traffic_distortion *ret)
2911 {
2912 // // dbg(0, "enter\n");
2913
2914 struct route_graph_point *start = seg->start;
2915 struct route_graph_point *end = seg->end;
2916 struct route_graph_segment *tmp, *found = NULL;
2917
2918 tmp = start->start;
2919
2920 while (tmp && !found)
2921 {
2922 if (tmp->data.item.type == type_traffic_distortion && tmp->start == start && tmp->end == end)
2923 found = tmp;
2924 tmp = tmp->start_next;
2925 }
2926
2927 tmp = start->end;
2928 while (tmp && !found)
2929 {
2930 if (tmp->data.item.type == type_traffic_distortion && tmp->end == start && tmp->start == end)
2931 found = tmp;
2932 tmp = tmp->end_next;
2933 }
2934
2935 if (found)
2936 {
2937 ret->delay = found->data.len;
2938
2939 if (found->data.flags & NAVIT_AF_SPEED_LIMIT)
2940 ret->maxspeed = RSD_MAXSPEED(&found->data);
2941 else
2942 ret->maxspeed = INT_MAX;
2943
2944 return 1;
2945 }
2946
2947 return 0;
2948 }
2949
2950 static int route_through_traffic_allowed(struct vehicleprofile *profile, struct route_graph_segment *seg)
2951 {
2952 return (seg->data.flags & NAVIT_AF_THROUGH_TRAFFIC_LIMIT) == 0;
2953 }
2954
2955 /**
2956 * @brief Returns the "costs" of driving from point "from" over segment "over" in direction "dir"
2957 *
2958 * @param profile The routing preferences
2959 * @param from The point where we are starting (can be NULL)
2960 * @param over The segment we are using
2961 * @param dir The direction of segment which we are driving
2962 * @return The "costs" needed to drive len on item
2963 */
2964 static int route_value_seg(struct vehicleprofile *profile, struct route_graph_segment *from, struct route_graph_segment *over, int dir)
2965 {
2966 //// dbg(0, "enter\n");
2967
2968 int ret;
2969 struct route_traffic_distortion dist, *distp = NULL;
2970
2971 #if 0
2972 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);
2973 #endif
2974
2975 //dbg(0, "over data fl = %x\n", over->data.flags);
2976 if ((over->data.flags & (dir >= 0 ? route_get_real_oneway_mask(over->data.flags, profile->flags_forward_mask) : route_get_real_oneway_mask(over->data.flags, profile->flags_reverse_mask))) != profile->flags)
2977 {
2978 //dbg(0, "one way:001: INT_MAX\n");
2979 return INT_MAX;
2980 }
2981
2982 if (dir > 0 && (over->start->flags & RP_TURN_RESTRICTION))
2983 {
2984 return INT_MAX;
2985 }
2986
2987 if (dir < 0 && (over->end->flags & RP_TURN_RESTRICTION))
2988 {
2989 return INT_MAX;
2990 }
2991
2992 if (from && from == over)
2993 {
2994 return INT_MAX;
2995 }
2996
2997 if ((over->start->flags & RP_TRAFFIC_DISTORTION) && (over->end->flags & RP_TRAFFIC_DISTORTION) && route_get_traffic_distortion(over, &dist))
2998 {
2999 distp = &dist;
3000 }
3001
3002 ret = route_time_seg(profile, &over->data, distp);
3003
3004
3005 // add new "route_prio_weight" attr here ----------------------------------------------------------
3006 struct roadprofile *roadprofile = vehicleprofile_get_roadprofile(profile, (&over->data)->item.type);
3007
3008 if (!roadprofile || !roadprofile->route_prio_weight)
3009 {
3010 }
3011 else
3012 {
3013 // cycle track is the same as real cycleway, its not on the road!
3014 if ((over->data.flags & NAVIT_AF_BICYCLE_TRACK) && ((global_vehicle_profile == 1) || (global_vehicle_profile == 2)))
3015 {
3016 roadprofile = vehicleprofile_get_roadprofile(profile, type_cycleway);
3017 if ((roadprofile) && (roadprofile->route_prio_weight))
3018 {
3019 ret = (int)( (float)ret * ((float)roadprofile->route_prio_weight / 10.0f ));
3020 }
3021 else
3022 {
3023 ret = (int)( (float)ret * ((float)roadprofile->route_prio_weight / 10.0f ));
3024 }
3025 }
3026 else if ((over->data.flags & NAVIT_AF_BICYCLE_LANE) && ((global_vehicle_profile == 1) || (global_vehicle_profile == 2)))
3027 {
3028 // road with cyclelane is a bit better than normal road!
3029 ret = (int)( (float)ret * ((float)(roadprofile->route_prio_weight - global_cycle_lanes_prio) / 10.0f ));
3030 }
3031 else
3032 {
3033 //dbg(0, "ret =%d w=%d\n", ret, roadprofile->route_prio_weight);
3034 //int ret2 = ( ret * 100 * (roadprofile->route_prio_weight * 10.0 ) / 10000);
3035 //dbg(0, "ret2 new=%d\n", ret2);
3036
3037 ret = (int)( (float)ret * ((float)roadprofile->route_prio_weight / 10.0f ));
3038 //dbg(0, "ret new=%d\n", ret);
3039 }
3040 }
3041 // add new "route_prio_weight" attr here ----------------------------------------------------------
3042
3043
3044
3045 // sharp turn penalty ------------
3046 // sharp turn penalty ------------
3047 if (from)
3048 {
3049 int delta = 0;
3050
3051 if (from->end == over->end)
3052 {
3053 // c_start_plus_1
3054 //delta = from->data.angle_end - over->data.angle_end + 180;
3055 }
3056 else if (from->start == over->end)
3057 {
3058 //delta = from->data.angle_start - over->data.angle_end;
3059 }
3060 else if (from->end == over->start)
3061 {
3062 //delta = from->data.angle_end - over->data.angle_start;
3063 }
3064 else if (from->start == over->start)
3065 {
3066 //delta = from->data.angle_start - over->data.angle_start - 180;
3067 }
3068
3069 if (delta < -180)
3070 {
3071 delta += 360;
3072 }
3073
3074 if (delta > 180)
3075 {
3076 delta -= 360;
3077 }
3078
3079 #define TURN_ANGLE_THRESHOLD 95
3080
3081 if (abs(delta) > TURN_ANGLE_THRESHOLD) // threshold
3082 {
3083 /* add 2 tenths of a second per degree above threshold */
3084 ret = ret + abs(delta - TURN_ANGLE_THRESHOLD) + abs(delta - TURN_ANGLE_THRESHOLD);
3085 }
3086 }
3087 // sharp turn penalty ------------
3088 // sharp turn penalty ------------
3089
3090
3091
3092 if (ret == INT_MAX)
3093 {
3094 return ret;
3095 }
3096
3097 if (!route_through_traffic_allowed(profile, over) && from && route_through_traffic_allowed(profile, from))
3098 {
3099 ret += profile->through_traffic_penalty;
3100 }
3101
3102 // calc delay from traffic lights
3103 if ((from) && (global_traffic_light_delay > 0))
3104 {
3105
3106 // fix this later
3107
3108 // if (from->flags & RP_TRAFFIC_LIGHT)
3109 // {
3110 // dbg(0, "traffic light delay:%d w/o:%d\n", (ret+global_traffic_light_delay), ret);
3111 // in 1/10 of a second !!
3112 // ret += global_traffic_light_delay;
3113 // }
3114 }
3115
3116 return ret;
3117 }
3118
3119
3120 #if 0
3121 // !!was for dijkstra reverse!!
3122 static int route_value_seg_r(struct vehicleprofile *profile, struct route_graph_point *from, struct route_graph_segment *over, int dir)
3123 {
3124 //// dbg(0, "enter\n");
3125
3126 int ret;
3127 struct route_traffic_distortion dist, *distp = NULL;
3128
3129 #if 0
3130 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);
3131 #endif
3132
3133 //dbg(0, "over data fl = %x\n", over->data.flags);
3134 if ((over->data.flags & (dir >= 0 ? route_get_real_oneway_mask(over->data.flags, profile->flags_forward_mask) : route_get_real_oneway_mask(over->data.flags, profile->flags_reverse_mask))) != profile->flags)
3135 {
3136 //dbg(0, "one way:001: INT_MAX\n");
3137 return INT_MAX;
3138 }
3139
3140 if (dir > 0 && (over->start->flags & RP_TURN_RESTRICTION))
3141 {
3142 return INT_MAX;
3143 }
3144
3145 if (dir < 0 && (over->end->flags & RP_TURN_RESTRICTION))
3146 {
3147 return INT_MAX;
3148 }
3149
3150 if (from && from->seg_rev == over)
3151 {
3152 return INT_MAX;
3153 }
3154
3155 if ((over->start->flags & RP_TRAFFIC_DISTORTION) && (over->end->flags & RP_TRAFFIC_DISTORTION) && route_get_traffic_distortion(over, &dist))
3156 {
3157 distp = &dist;
3158 }
3159
3160 ret = route_time_seg(profile, &over->data, distp);
3161
3162
3163 // add new "route_prio_weight" attr here ----------------------------------------------------------
3164 struct roadprofile *roadprofile = vehicleprofile_get_roadprofile(profile, (&over->data)->item.type);
3165
3166 if (!roadprofile || !roadprofile->route_prio_weight)
3167 {
3168 }
3169 else
3170 {
3171 // cycle track is the same as real cycleway, its not on the road!
3172 if ((over->data.flags & NAVIT_AF_BICYCLE_TRACK) && ((global_vehicle_profile == 1) || (global_vehicle_profile == 2)))
3173 {
3174 roadprofile = vehicleprofile_get_roadprofile(profile, type_cycleway);
3175 if ((roadprofile) && (roadprofile->route_prio_weight))
3176 {
3177 ret = (int)( (float)ret * ((float)roadprofile->route_prio_weight / 10.0f ));
3178 }
3179 else
3180 {
3181 ret = (int)( (float)ret * ((float)roadprofile->route_prio_weight / 10.0f ));
3182 }
3183 }
3184 else if ((over->data.flags & NAVIT_AF_BICYCLE_LANE) && ((global_vehicle_profile == 1) || (global_vehicle_profile == 2)))
3185 {
3186 // road with cyclelane is a bit better than normal road!
3187 ret = (int)( (float)ret * ((float)(roadprofile->route_prio_weight - global_cycle_lanes_prio) / 10.0f ));
3188 }
3189 else
3190 {
3191 //dbg(0, "ret =%d w=%d\n", ret, roadprofile->route_prio_weight);
3192 //int ret2 = ( ret * 100 * (roadprofile->route_prio_weight * 10.0 ) / 10000);
3193 //dbg(0, "ret2 new=%d\n", ret2);
3194
3195 ret = (int)( (float)ret * ((float)roadprofile->route_prio_weight / 10.0f ));
3196 //dbg(0, "ret new=%d\n", ret);
3197 }
3198 }
3199 // add new "route_prio_weight" attr here ----------------------------------------------------------
3200
3201
3202
3203 if (ret == INT_MAX)
3204 {
3205 return ret;
3206 }
3207
3208 if (!route_through_traffic_allowed(profile, over) && from && route_through_traffic_allowed(profile, from->seg_rev))
3209 {
3210 ret += profile->through_traffic_penalty;
3211 }
3212
3213 // calc delay from traffic lights
3214 if ((from) && (global_traffic_light_delay > 0))
3215 {
3216 if (from->flags & RP_TRAFFIC_LIGHT)
3217 {
3218 // dbg(0, "traffic light delay:%d w/o:%d\n", (ret+global_traffic_light_delay), ret);
3219 // in 1/10 of a second !!
3220 ret += global_traffic_light_delay;
3221 }
3222 }
3223
3224 return ret;
3225 }
3226 // !!was for dijkstra reverse!!
3227 # endif
3228
3229
3230 /**
3231 * @brief Adds a traffic light item to the route graph
3232 *
3233 * @param this The route graph to add to
3234 * @param item The item to add
3235 */
3236 static void route_process_traffic_light(struct route_graph *this, struct item *item)
3237 {
3238
3239 struct route_graph_point *s_pnt, *e_pnt;
3240 struct coord l;
3241 struct route_graph_segment_data data;
3242
3243 data.item = item;
3244 data.len = 0;
3245 data.flags = 0;
3246 data.offset = 1;
3247 data.maxspeed = INT_MAX;
3248
3249 if (item_coord_get(item, &l, 1))
3250 {
3251 s_pnt = route_graph_add_point(this, &l);
3252 s_pnt->flags |= RP_TRAFFIC_LIGHT;
3253 }
3254
3255 }
3256
3257
3258
3259
3260
3261 /**
3262 * @brief Adds a route distortion item to the route graph
3263 *
3264 * @param this The route graph to add to
3265 * @param item The item to add
3266 */
3267 static void route_process_traffic_distortion(struct route_graph *this, struct item *item)
3268 {
3269 __F_START__
3270
3271 struct route_graph_point *s_pnt, *e_pnt;
3272 struct coord c, l;
3273 struct attr delay_attr, maxspeed_attr;
3274 struct route_graph_segment_data data;
3275
3276 data.item = item;
3277 data.len = 0;
3278 data.flags = 0;
3279 data.offset = 1;
3280 data.maxspeed = INT_MAX;
3281
3282 if (item_coord_get(item, &l, 1))
3283 {
3284 s_pnt = route_graph_add_point(this, &l);
3285 while (item_coord_get(item, &c, 1))
3286 {
3287 l = c;
3288 }
3289
3290 e_pnt = route_graph_add_point(this, &l);
3291 s_pnt->flags |= RP_TRAFFIC_DISTORTION;
3292 e_pnt->flags |= RP_TRAFFIC_DISTORTION;
3293
3294 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr))
3295 {
3296 data.flags |= NAVIT_AF_SPEED_LIMIT;
3297 data.maxspeed = maxspeed_attr.u.num;
3298 }
3299
3300 if (item_attr_get(item, attr_delay, &delay_attr))
3301 {
3302 data.len = delay_attr.u.num;
3303 }
3304 //dbg(0,"add traffic distortion segment, speed=%d\n", data.maxspeed);
3305 route_graph_add_segment(this, s_pnt, e_pnt, &data);
3306 }
3307
3308 __F_END__
3309 }
3310
3311
3312 /**
3313 * @brief Adds a route distortion item to the route graph
3314 *
3315 * @param this The route graph to add to
3316 * @param item The item to add
3317 */
3318 static void route_process_turn_restriction(struct route_graph *this, struct item *item)
3319 {
3320
3321 struct route_graph_point *pnt[4];
3322 struct coord c[5];
3323 int i, count;
3324 struct route_graph_segment_data data;
3325
3326 count = item_coord_get(item, c, 5);
3327
3328 if (count != 3 && count != 4)
3329 {
3330 //dbg(0, "wrong count %d\n", count);
3331 return;
3332 }
3333
3334 if (count == 4)
3335 {
3336 return;
3337 }
3338
3339 for (i = 0; i < count; i++)
3340 {
3341 pnt[i] = route_graph_add_point(this, &c[i]);
3342 }
3343
3344 //dbg(1, "%s: (0x%x,0x%x)-(0x%x,0x%x)-(0x%x,0x%x) %p-%p-%p\n",
3345 // item_to_name(item->type), c[0].x, c[0].y, c[1].x, c[1].y, c[2].x,
3346 // c[2].y, pnt[0], pnt[1], pnt[2]);
3347 data.item = item;
3348 data.flags = 0;
3349 data.len = 0;
3350 route_graph_add_segment(this, pnt[0], pnt[1], &data);
3351 route_graph_add_segment(this, pnt[1], pnt[2], &data);
3352
3353 #if 1
3354 if (count == 4)
3355 {
3356 pnt[1]->flags |= RP_TURN_RESTRICTION;
3357 pnt[2]->flags |= RP_TURN_RESTRICTION;
3358 route_graph_add_segment(this, pnt[2], pnt[3], &data);
3359 }
3360 else
3361 {
3362 pnt[1]->flags |= RP_TURN_RESTRICTION;
3363 }
3364 #endif
3365
3366 }
3367
3368 /**
3369 * @brief Adds an item to the route graph
3370 *
3371 * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
3372 * segmented item.
3373 *
3374 * @param this The route graph to add to
3375 * @param item The item to add
3376 * @param profile The vehicle profile currently in use
3377 */
3378 static void route_process_street_graph(struct route_graph *this, struct item *item, struct vehicleprofile *profile)
3379 {
3380
3381 #ifdef AVOID_FLOAT
3382 int len=0;
3383 #else
3384 double len = 0;
3385 #endif
3386 int segmented = 0;
3387 struct roadprofile *roadp;
3388 struct route_graph_point *s_pnt, *e_pnt;
3389 struct coord c2, c99, c98;
3390 struct coord c, l;
3391 struct attr attr;
3392 struct route_graph_segment_data data;
3393 data.flags = 0;
3394 data.offset = 1;
3395 data.maxspeed = -1;
3396 data.item = item;
3397
3398 roadp = vehicleprofile_get_roadprofile(profile, item->type);
3399
3400 if (!roadp)
3401 {
3402 // Don't include any roads that don't have a road profile in our vehicle profile
3403 return;
3404 }
3405
3406 if (item_coord_get(item, &l, 1))
3407 {
3408 int *default_flags = item_get_default_flags(item->type);
3409 if (!default_flags)
3410 {
3411 return;
3412 }
3413
3414 if (item_attr_get(item, attr_flags, &attr))
3415 {
3416 data.flags = attr.u.num;
3417 if (data.flags & NAVIT_AF_SEGMENTED)
3418 {
3419 segmented = 1;
3420 }
3421 }
3422 else
3423 {
3424 data.flags = *default_flags;
3425 }
3426
3427 if (data.flags & NAVIT_AF_SPEED_LIMIT)
3428 {
3429 if (item_attr_get(item, attr_maxspeed, &attr))
3430 {
3431 data.maxspeed = attr.u.num;
3432 }
3433 }
3434
3435 if (data.flags & NAVIT_AF_DANGEROUS_GOODS)
3436 {
3437 if (item_attr_get(item, attr_vehicle_dangerous_goods, &attr))
3438 {
3439 data.dangerous_goods = attr.u.num;
3440 }
3441 else
3442 {
3443 data.flags &= ~NAVIT_AF_DANGEROUS_GOODS;
3444 }
3445 }
3446
3447 if (data.flags & NAVIT_AF_SIZE_OR_WEIGHT_LIMIT)
3448 {
3449 if (item_attr_get(item, attr_vehicle_width, &attr))
3450 data.size_weight.width = attr.u.num;
3451 else
3452 data.size_weight.width = -1;
3453
3454
3455 if (item_attr_get(item, attr_vehicle_height, &attr))
3456 data.size_weight.height = attr.u.num;
3457 else
3458 data.size_weight.height = -1;
3459
3460
3461 if (item_attr_get(item, attr_vehicle_length, &attr))
3462 data.size_weight.length = attr.u.num;
3463 else
3464 data.size_weight.length = -1;
3465
3466
3467 if (item_attr_get(item, attr_vehicle_weight, &attr))
3468 data.size_weight.weight = attr.u.num;
3469 else
3470 data.size_weight.weight = -1;
3471
3472
3473 if (item_attr_get(item, attr_vehicle_axle_weight, &attr))
3474 data.size_weight.axle_weight = attr.u.num;
3475 else
3476 data.size_weight.axle_weight = -1;
3477
3478 }
3479
3480 // add start point
3481 s_pnt = route_graph_add_point(this, &l);
3482
3483 if (!segmented)
3484 {
3485 int count_coords = 0;
3486
3487 c2.x = l.x;
3488 c2.y = l.y;
3489 c99.x = l.x;
3490 c99.y = l.y;
3491 c98.x = l.x;
3492 c98.y = l.y;
3493
3494 while (item_coord_get(item, &c, 1))
3495 {
3496 len += transform_distance(map_projection(item->map), &l, &c);
3497 l = c;
3498
3499 if (count_coords == 0)
3500 {
3501 // save second coord
3502 c2.x = c.x;
3503 c2.y = c.y;
3504 // fill in some values for the second to last coord (in case we only have 2 coords total!)
3505 }
3506
3507 c98.x = c99.x;
3508 c98.y = c99.y;
3509 c99.x = c.x;
3510 c99.y = c.y;
3511
3512 count_coords++;
3513 }
3514 // add end point
3515 e_pnt = route_graph_add_point(this, &l);
3516 dbg_assert(len >= 0);
3517 data.len = len;
3518
3519 if (!route_graph_segment_is_duplicate(s_pnt, &data))
3520 {
3521 route_graph_add_segment_with_coords(this, s_pnt, e_pnt, &data, &c2, &c98);
3522 }
3523 }
3524 else
3525 {
3526 int isseg, rc;
3527 int sc = 0;
3528 do
3529 {
3530 isseg = item_coord_is_node(item);
3531 rc = item_coord_get(item, &c, 1);
3532 if (rc)
3533 {
3534 len += transform_distance(map_projection(item->map), &l, &c);
3535 l = c;
3536 if (isseg)
3537 {
3538 e_pnt = route_graph_add_point(this, &l);
3539 data.len = len;
3540
3541 if (!route_graph_segment_is_duplicate(s_pnt, &data))
3542 {
3543 route_graph_add_segment(this, s_pnt, e_pnt, &data);
3544 }
3545
3546 data.offset++;
3547 s_pnt = route_graph_add_point(this, &l);
3548 len = 0;
3549 }
3550 }
3551 }
3552 while (rc);
3553
3554
3555
3556 e_pnt = route_graph_add_point(this, &l);
3557 dbg_assert(len >= 0);
3558 sc++;
3559 data.len = len;
3560
3561 if (!route_graph_segment_is_duplicate(s_pnt, &data))
3562 {
3563 route_graph_add_segment(this, s_pnt, e_pnt, &data);
3564 }
3565 }
3566 }
3567
3568 }
3569
3570 struct route_graph_segment *route_graph_get_segment(struct route_graph *graph, struct street_data *sd, struct route_graph_segment *last)
3571 {
3572 struct route_graph_point *start = NULL;
3573 struct route_graph_segment *s;
3574 int seen = 0;
3575
3576 while ((start = route_graph_get_point_next(graph, &sd->c[0], start)))
3577 {
3578 s = start->start;
3579 while (s)
3580 {
3581 if (item_is_equal(sd->item, s->data.item))
3582 {
3583 if (!last || seen)
3584 {
3585 return s;
3586 }
3587
3588 if (last == s)
3589 {
3590 seen = 1;
3591 }
3592 }
3593 s = s->start_next;
3594 }
3595 }
3596
3597 return NULL;
3598 }
3599
3600
3601 static int route_angle_diff(int a1, int a2, int full)
3602 {
3603 int ret = (a1 - a2) % full;
3604
3605 if (ret > full / 2)
3606 {
3607 ret -= full;
3608 }
3609
3610 if (ret < -full / 2)
3611 {
3612 ret += full;
3613 }
3614
3615 return ret;
3616 }
3617
3618 static int route_angle_abs_diff(int a1, int a2, int full)
3619 {
3620 int ret = route_angle_diff(a1, a2, full);
3621
3622 if (ret < 0)
3623 {
3624 ret = -ret;
3625 }
3626
3627 return ret;
3628
3629 }
3630
3631 // unused, and maybe broken!
3632 int route_road_to_road_angle____XXXXXXXX(struct route_graph_segment *s1, struct route_graph_segment *s2, int dir1)
3633 {
3634
3635 int dir2 = 1;
3636
3637 if (dir1 == -1)
3638 {
3639 if ((s1->start->c.x == s2->start->c.x) && (s1->start->c.y == s2->start->c.y))
3640 {
3641 dir2 = 1;
3642 }
3643 else
3644 {
3645 dir2 = -1;
3646 }
3647 }
3648 else
3649 {
3650 if ((s1->end->c.x == s2->start->c.x) && (s1->end->c.y == s2->start->c.y))
3651 {
3652 dir2 = 1;
3653 }
3654 else
3655 {
3656 dir2 = -1;
3657 }
3658 }
3659
3660 // COST: 204
3661 dbg(0, "COST:204\n");
3662
3663 struct coord *c1 = &(s1->start->c);
3664 struct coord *c2 = &(s1->end->c);
3665 int angle1 = transform_get_angle_delta(c1, c2, -dir1);
3666
3667 c1 = &(s2->start->c);
3668 c2 = &(s2->end->c);
3669 int angle2 = transform_get_angle_delta(c1, c2, dir2);
3670
3671 int ret = route_angle_abs_diff(angle1, angle2, 360);
3672
3673 return ret;
3674
3675 }
3676
3677 static int route_real_item_2nd_node(struct route_graph_segment *s, struct coord *c)
3678 {
3679 struct item *i;
3680 struct item *i2;
3681
3682 if ((s->c_start_plus_1.x != 0) && (s->c_start_plus_1.y != 0))
3683 {
3684 // COST: 201a
3685 // dbg(0, "COST:201a\n");
3686
3687 c->x = s->c_start_plus_1.x;
3688 c->y = s->c_start_plus_1.y;
3689 return 1;
3690 }
3691
3692 // COST: 201
3693 // dbg(0, "COST:201\n");
3694
3695 i = &(s->data.item);
3696
3697 if (i)
3698 {
3699 struct map_rect *mr33 = NULL;
3700 mr33 = map_rect_new(i->map, NULL);
3701
3702 if (mr33)
3703 {
3704 i2 = map_rect_get_item_byid(mr33, i->id_hi, i->id_lo);
3705 if (i2)
3706 {
3707 if (item_coord_get(i2, c, 1))
3708 {
3709 if (item_coord_get(i2, c, 1))
3710 {
3711 map_rect_destroy(mr33);
3712
3713 // save into struct -------------
3714 s->c_start_plus_1.x = c->x;
3715 s->c_start_plus_1.y = c->y;
3716 // save into struct -------------
3717
3718 return 1;
3719 }
3720 }
3721 }
3722 map_rect_destroy(mr33);
3723 }
3724 }
3725
3726 c->x = 0;
3727 c->y = 0;
3728
3729 return 0;
3730 }
3731
3732 static int route_real_item_2nd_last_node(struct route_graph_segment *s, struct coord *c)
3733 {
3734 struct item *i;
3735 struct item *i2;
3736 struct coord c_temp1;
3737 struct coord c_temp2;
3738 int count = 0;
3739
3740 if ((s->c_end_minus_1.x != 0) && (s->c_end_minus_1.y != 0))
3741 {
3742 // COST: 202a
3743 // dbg(0, "COST:202a\n");
3744
3745 c->x = s->c_end_minus_1.x;
3746 c->y = s->c_end_minus_1.y;
3747 return 1;
3748 }
3749
3750 // COST: 202
3751 // dbg(0, "COST:202\n");
3752
3753 i = &(s->data.item);
3754
3755 if (i)
3756 {
3757 struct map_rect *mr33 = NULL;
3758 mr33 = map_rect_new(i->map, NULL);
3759
3760 if (mr33)
3761 {
3762 i2 = map_rect_get_item_byid(mr33, i->id_hi, i->id_lo);
3763 if (i2)
3764 {
3765 // get all coords, and remeber the 2nd last
3766 while (item_coord_get(i2, c, 1))
3767 {
3768 count++;
3769
3770 c_temp2.x = c_temp1.x;
3771 c_temp2.y = c_temp1.y;
3772 c_temp1.x = c->x;
3773 c_temp1.y = c->y;
3774 }
3775
3776 if (count > 1)
3777 {
3778 c->x = c_temp2.x;
3779 c->y = c_temp2.y;
3780
3781 map_rect_destroy(mr33);
3782
3783 // save into struct -------------
3784 s->c_end_minus_1.x = c->x;
3785 s->c_end_minus_1.y = c->y;
3786 // save into struct -------------
3787
3788 return 1;
3789 }
3790 }
3791 map_rect_destroy(mr33);
3792 }
3793 }
3794
3795 c->x = 0;
3796 c->y = 0;
3797
3798 return 0;
3799 }
3800
3801 //
3802 // return: 1 == seg start is at point, 0 == seg end is at point
3803 //
3804 int route_find_seg_dir_at_point(struct route_graph_point *p, struct route_graph_segment *s1)
3805 {
3806 if ((p->c.x == s1->start->c.x) && (p->c.y == s1->start->c.y))
3807 {
3808 return 1;
3809 }
3810 else
3811 {
3812 return -1;
3813 }
3814 }
3815
3816 int route_road_to_road_angle_get_segs(struct route_graph_segment *s1, struct route_graph_segment *s2, int dir1, int *dir2, struct coord *cc, struct coord *cs, struct coord *ce, int abs)
3817 {
3818
3819 struct coord ci;
3820 struct coord z1;
3821 struct coord z2;
3822 struct coord z1e;
3823 struct coord z2e;
3824
3825 // dir1 == 1 (center point is s1->end)
3826 // dir1 == -1 (center point is s1->start)
3827
3828
3829 // dir == 1 --> goes forward on item
3830 // dir == -1 --> does backwards on item
3831
3832
3833
3834 *dir2 = 1;
3835
3836 if (dir1 == -1)
3837 {
3838 if ((s1->start->c.x == s2->start->c.x) && (s1->start->c.y == s2->start->c.y))
3839 {
3840 *dir2 = 1;
3841 cc->x = s1->start->c.x; // s2->start
3842 cc->y = s1->start->c.y;
3843
3844 //cs->x = s1->end->c.x;
3845 //cs->y = s1->end->c.y;
3846 if (route_real_item_2nd_node(s1, &ci) == 0)
3847 {
3848 return 180;
3849 }
3850 else
3851 {
3852 cs->x = ci.x;
3853 cs->y = ci.y;
3854 }
3855
3856 // ce->x = s2->end->c.x;
3857 // ce->y = s2->end->c.y;
3858 if (route_real_item_2nd_node(s2, &ci) == 0)
3859 {
3860 return 180;
3861 }
3862 else
3863 {
3864 ce->x = ci.x;
3865 ce->y = ci.y;
3866 }
3867
3868
3869 z1.x = s1->start->c.x;
3870 z1.y = s1->start->c.y;
3871 z2.x = cs->x;
3872 z2.y = cs->y;
3873
3874 z1e.x = s2->start->c.x;
3875 z1e.y = s2->start->c.y;
3876 z2e.x = ce->x;
3877 z2e.y = ce->y;
3878
3879 }
3880 else
3881 {
3882 *dir2 = -1;
3883 cc->x = s1->start->c.x; // s2->end
3884 cc->y = s1->start->c.y;
3885
3886 // cs->x = s1->end->c.x;
3887 // cs->y = s1->end->c.y;
3888 if (route_real_item_2nd_node(s1, &ci) == 0)
3889 {
3890 return 180;
3891 }
3892 else
3893 {
3894 cs->x = ci.x;
3895 cs->y = ci.y;
3896 }
3897
3898 // ce->x = s2->start->c.x;
3899 // ce->y = s2->start->c.y;
3900 if (route_real_item_2nd_last_node(s2, &ci) == 0)
3901 {
3902 return 180;
3903 }
3904 else
3905 {
3906 ce->x = ci.x;
3907 ce->y = ci.y;
3908 }
3909
3910 z1.x = s1->start->c.x;
3911 z1.y = s1->start->c.y;
3912 z2.x = cs->x;
3913 z2.y = cs->y;
3914
3915 z1e.x = ce->x;
3916 z1e.y = ce->y;
3917 z2e.x = s2->end->c.x;
3918 z2e.y = s2->end->c.y;
3919
3920 }
3921 }
3922 else
3923 {
3924 if ((s1->end->c.x == s2->start->c.x) && (s1->end->c.y == s2->start->c.y))
3925 {
3926 *dir2 = 1;
3927 cc->x = s1->end->c.x; // s2->start
3928 cc->y = s1->end->c.y;
3929
3930 // cs->x = s1->start->c.x;
3931 // cs->y = s1->start->c.y;
3932 if (route_real_item_2nd_last_node(s1, &ci) == 0)
3933 {
3934 return 180;
3935 }
3936 else
3937 {
3938 cs->x = ci.x;
3939 cs->y = ci.y;
3940 }
3941
3942
3943 // ce->x = s2->end->c.x;
3944 // ce->y = s2->end->c.y;
3945 if (route_real_item_2nd_node(s2, &ci) == 0)
3946 {
3947 return 180;
3948 }
3949 else
3950 {
3951 ce->x = ci.x;
3952 ce->y = ci.y;
3953 }
3954
3955 z1.x = cs->x;
3956 z1.y = cs->y;
3957 z2.x = s1->end->c.x;
3958 z2.y = s1->end->c.y;
3959
3960 z1e.x = s2->start->c.x;
3961 z1e.y = s2->start->c.y;
3962 z2e.x = ce->x;
3963 z2e.y = ce->y;
3964
3965 }
3966 else
3967 {
3968 *dir2 = -1;
3969 cc->x = s1->end->c.x; // s2->end
3970 cc->y = s1->end->c.y;
3971
3972 // cs->x = s1->start->c.x;
3973 // cs->y = s1->start->c.y;
3974 if (route_real_item_2nd_last_node(s1, &ci) == 0)
3975 {
3976 return 180;
3977 }
3978 else
3979 {
3980 cs->x = ci.x;
3981 cs->y = ci.y;
3982 }
3983
3984
3985 // ce->x = s2->start->c.x;
3986 // ce->y = s2->start->c.y;
3987 if (route_real_item_2nd_last_node(s2, &ci) == 0)
3988 {
3989 return 180;
3990 }
3991 else
3992 {
3993 ce->x = ci.x;
3994 ce->y = ci.y;
3995 }
3996
3997 z1.x = cs->x;
3998 z1.y = cs->y;
3999 z2.x = s1->end->c.x;
4000 z2.y = s1->end->c.y;
4001
4002 z1e.x = ce->x;
4003 z1e.y = ce->y;
4004 z2e.x = s2->end->c.x;
4005 z2e.y = s2->end->c.y;
4006
4007 }
4008 }
4009
4010 /*
4011 z1.x = s1->start->c.x;
4012 z1.y = s1->start->c.y;
4013 z2.x = s1->end->c.x;
4014 z2.y = s1->end->c.y;
4015 */
4016 // COST: 203
4017 // dbg(0, "COST:203\n");
4018
4019 int angle1 = transform_get_angle_delta(&z1, &z2, -dir1);
4020
4021 // dbg(0, "RR:55:a1=%d\n", angle1);
4022
4023 /*
4024 z1e.x = s2->start->c.x;
4025 z1e.y = s2->start->c.y;
4026 z2e.x = s2->end->c.x;
4027 z2e.y = s2->end->c.y;
4028 */
4029 int angle2 = transform_get_angle_delta(&z1e, &z2e, *dir2);
4030
4031 // dbg(0, "RR:55:a2=%d\n", angle2);
4032
4033 int ret;
4034
4035 if (abs == 1)
4036 {
4037 ret = route_angle_abs_diff(angle1, angle2, 360);
4038 }
4039 else
4040 {
4041 ret = route_angle_diff(angle1, angle2, 360);
4042 if (ret > 0)
4043 {
4044 ret = ret - 180;
4045 }
4046 else // ret <= 0
4047 {
4048 ret = ret + 180;
4049 }
4050 }
4051
4052 // dbg(0, "RR:55:res=%d\n", ret);
4053 return ret;
4054 }
4055
4056
4057 void route_clear_sharp_turn_list()
4058 {
4059 if (global_sharp_turn_list)
4060 {
4061 g_free(global_sharp_turn_list);
4062 }
4063
4064 global_sharp_turn_list_count = 0;
4065 global_sharp_turn_list = g_new0(struct global_sharp_turn, MAX_SHARP_TURN_LIST_ENTRIES + 2 );
4066
4067 }
4068
4069 void route_add_to_sharp_turn_list(struct coord *c, struct coord *cs, struct coord *ce, int turn_angle, int dir)
4070 {
4071 global_sharp_turn_list[global_sharp_turn_list_count].dir = dir;
4072 global_sharp_turn_list[global_sharp_turn_list_count].angle = turn_angle;
4073
4074 // dbg(0, "st.angle=%d\n", turn_angle);
4075
4076 global_sharp_turn_list[global_sharp_turn_list_count].c1.x = c->x;
4077 global_sharp_turn_list[global_sharp_turn_list_count].c1.y = c->y;
4078
4079 global_sharp_turn_list[global_sharp_turn_list_count].cs.x = cs->x;
4080 global_sharp_turn_list[global_sharp_turn_list_count].cs.y = cs->y;
4081
4082 global_sharp_turn_list[global_sharp_turn_list_count].ce.x = ce->x;
4083 global_sharp_turn_list[global_sharp_turn_list_count].ce.y = ce->y;
4084
4085 global_sharp_turn_list_count++;
4086 if (global_sharp_turn_list_count > MAX_SHARP_TURN_LIST_ENTRIES)
4087 {
4088 global_sharp_turn_list_count--;
4089 }
4090 }
4091
4092
4093
4094 void route_clear_freetext_list()
4095 {
4096 if (global_freetext_list)
4097 {
4098 g_free(global_freetext_list);
4099 }
4100
4101 global_freetext_list_count = 0;
4102 global_freetext_list = g_new0(struct global_freetext, MAX_FREETEXT_LIST_ENTRIES + 2 );
4103
4104 }
4105
4106 void route_add_to_freetext_list(struct coord *c, const char* txt)
4107 {
4108 global_freetext_list[global_freetext_list_count].c1.x = c->x;
4109 global_freetext_list[global_freetext_list_count].c1.y = c->y;
4110
4111 snprintf(global_freetext_list[global_freetext_list_count].text, (MAX_FREETEXT_ENTRY_LEN - 2), "%s", txt);
4112 global_freetext_list[global_freetext_list_count].text[(MAX_FREETEXT_ENTRY_LEN - 1)] = '\0';
4113
4114 global_freetext_list_count++;
4115 if (global_freetext_list_count > MAX_FREETEXT_LIST_ENTRIES)
4116 {
4117 global_freetext_list_count--;
4118 }
4119 }
4120
4121
4122
4123
4124 /**
4125 * @brief Calculates the routing costs for each point
4126 *
4127 * This function is the heart of routing. It assigns each point in the route graph a
4128 * cost at which one can reach the destination from this point on.
4129 *
4130 * elements are: seg, value
4131 *
4132 * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
4133 * at this algorithm.
4134 *
4135 * call "cb" at the end
4136 *
4137 */
4138 static void route_graph_flood(struct route_graph *this, struct route_info *dst, struct route_info *pos, struct vehicleprofile *profile, struct callback *cb)
4139 {
4140 __F_START__
4141
4142 dbg(0, "RR_TIM:g:001\n");
4143
4144 struct route_graph_point *p_min = NULL;
4145 struct route_graph_segment *s = NULL;
4146 int min, new, old, val;
4147 int turn_angle;
4148 struct fibheap *heap; /* This heap will hold segments with "temporarily" calculated costs */
4149
4150 heap = fh_makekeyheap();
4151
4152 // start from "wanted destination" and loop until "start position" is reached
4153
4154 clock_t s_ = debug_measure_start();
4155
4156 struct route_graph_segment *pos_segment = NULL;
4157 struct route_graph_segment *s_min = NULL;
4158 int edges_count = 0;
4159 int max_cost = INT_MAX;
4160
4161 pos_segment = route_graph_get_segment(this, pos->street, pos_segment);
4162
4163
4164
4165 // calc segments lengths and values ------------
4166 // loop over all segments that connect to the destination street ONLY !!
4167 // calc segments lengths and values ------------
4168 // -------
4169 // dbg(0, "RR_SEG_DEBUG:001\n");
4170 while ((s = route_graph_get_segment(this, dst->street, s)))
4171 {
4172 // dbg(0, "RR_SEG_DEBUG:002:1:s=%p\n", s);
4173 val = route_value_seg(profile, NULL, s, -1);
4174 // dbg(0, "RR_SEG_DEBUG:002:2:val=%d\n", val);
4175 if (val != INT_MAX)
4176 {
4177 val = val * (100 - dst->percent) / 100;
4178 // dbg(0, "RR_SEG_DEBUG:002:P=%p dst->percent=%d val=%d end value=%d\n", s->end, dst->percent, val, s->end->value);
4179 s->seg_end_out_cost = val;
4180 s->el_end = fh_insertkey(heap, val, s);
4181 }
4182
4183 // dbg(0,"check destination segment end , val =%i, est_time = %i\n",val, 0);
4184 val = route_value_seg(profile, NULL, s, 1);
4185 // dbg(0, "RR_SEG_DEBUG:003:3:val=%d\n", val);
4186 if (val != INT_MAX)
4187 {
4188 val = val * dst->percent / 100;
4189 // dbg(0, "RR_SEG_DEBUG:003:P=%p dst->percent=%d val=%d start value=%d\n", s->start, dst->percent, val, s->start->value);
4190 s->seg_start_out_cost = val;
4191 s->el_start=fh_insertkey(heap, val, s);
4192 }
4193 //dbg(0, "RR_SEG_DEBUG:009:9:val=%d\n", val);
4194 }
4195 // dbg(0, "RR_SEG_DEBUG:090\n");
4196 // -------
4197 // calc segments lengths and values ------------
4198 // calc segments lengths and values ------------
4199
4200
4201 debug_mrp("RR_TIM:g:002", debug_measure_end(s_));
4202 // dbg(0, "RR_TIM:g:002 %s\n");
4203
4204
4205
4206 s_ = debug_measure_start();
4207
4208 // start Dijkstra here ------------
4209 // start Dijkstra here ------------
4210 for (;;)
4211 {
4212 s_min = fh_extractmin(heap);
4213
4214 if (!s_min)
4215 {
4216 break;
4217 }
4218
4219 if (s_min->el_end)
4220 {
4221 min = s_min->seg_end_out_cost;
4222 if (s_min->el_start && (s_min->seg_start_out_cost < min))
4223 {
4224 min = s_min->seg_start_out_cost;
4225 p_min = s_min->start;
4226 s_min->el_start = NULL;
4227 }
4228 else
4229 {
4230 p_min = s_min->end;
4231 s_min->el_end = NULL;
4232 }
4233 }
4234 else
4235 {
4236 min = s_min->seg_start_out_cost;
4237 p_min = s_min->start;
4238 s_min->el_start = NULL;
4239 }
4240
4241
4242 s = p_min->start;
4243
4244 while (s)
4245 { /* Iterating all the segments leading away from our point to update the points at their ends */
4246 edges_count++;
4247 val = route_value_seg(profile, s_min, s, -1);
4248 if (val != INT_MAX && item_is_equal(s->data.item,s_min->data.item))
4249 {
4250 // if (profile->turn_around_penalty2)
4251 // {
4252 // val+=profile->turn_around_penalty2;
4253 // }
4254 // else
4255 {
4256 val=INT_MAX;
4257
4258 }
4259 }
4260
4261 if (val != INT_MAX)
4262 {
4263 new=min+val;
4264 if (new < s->seg_end_out_cost)
4265 {
4266 s->seg_end_out_cost = new;
4267 s->start_from_seg = s_min;
4268
4269 if (!s->el_end)
4270 {
4271 s->el_end = fh_insertkey(heap, new, s);
4272 }
4273 else
4274 {
4275 fh_replacekey(heap, s->el_end, new);
4276 }
4277 }
4278
4279 if (item_is_equal(pos_segment->data.item,s->data.item))
4280 {
4281 max_cost = new;
4282 // dbg(0,"new shortest path cost via end_out= %i\n",new);
4283 // dbg(0,"number of edges visited =%i\n",edges_count);
4284 }
4285 }
4286 s = s->start_next;
4287 }
4288
4289 s = p_min->end;
4290
4291 while (s && max_cost == INT_MAX)
4292 { /* Doing the same as above with the segments leading towards our point */
4293 edges_count++;
4294 val = route_value_seg(profile, s_min, s, 1);
4295 if (val != INT_MAX && item_is_equal(s->data.item,s_min->data.item))
4296 {
4297 // if (profile->turn_around_penalty2)
4298 // {
4299 // val += profile->turn_around_penalty2;
4300 // }
4301 // else
4302 {
4303 val=INT_MAX;
4304 }
4305 }
4306
4307 if (val != INT_MAX)
4308 {
4309
4310
4311
4312
4313 new = min + val;
4314
4315 if (new < s->seg_start_out_cost)
4316 {
4317 // old = ...
4318 s->seg_start_out_cost = new;
4319 s->end_from_seg = s_min;
4320
4321 if (!s->el_start)
4322 {
4323 s->el_start = fh_insertkey(heap, new, s);
4324 }
4325 else
4326 {
4327 //if (debug_route)
4328 //{
4329 // printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
4330 //}
4331 fh_replacekey(heap, s->el_start, new);
4332 }
4333 }
4334
4335 if (item_is_equal(pos_segment->data.item, s->data.item))
4336 {
4337 max_cost = new;
4338 // dbg(0,"new shortest path cost via start_out= %i\n",new);
4339 // dbg(0,"number of edges visited =%i\n",edges_count);
4340 }
4341 }
4342 s = s->end_next;
4343 }
4344 }
4345 // dbg(0,"number of edges visited =%i\n",edges_count);
4346 debug_mrp("RR_TIM:g:003", debug_measure_end(s_));
4347
4348 fh_deleteheap(heap);
4349
4350 // CB: calls -> "route_path_update_done" !!
4351 callback_call_0(cb);
4352
4353 dbg(0, "RR_TIM:g:099\n");
4354
4355
4356 __F_END__
4357 }
4358
4359
4360
4361 #if 0
4362 void route_find_next_lowest_segment_and_pin_it(struct route_graph_point *p, struct route_graph_segment *s, int min_value, int penalty)
4363 {
4364 struct route_graph_segment *tmp = NULL;
4365 int cur_min = min_value;
4366
4367 // -------------------------------------------------------------
4368 // p->start ==> a list of all streets that start from this point
4369 // -------------------------------------------------------------
4370 tmp = p->start;
4371 while (tmp)
4372 {
4373 if (tmp != s)
4374 {
4375 if (tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only)
4376 {
4377 if (tmp->end->value <= min_value)
4378 {
4379 min_value = tmp->end->value;
4380 p->value = min_value;
4381 p->seg = tmp;
4382 }
4383 }
4384 }
4385 tmp = tmp->start_next;
4386 }
4387
4388 // -------------------------------------------------------------
4389 // p->end ==> a list of all streets that end at this point
4390 // -------------------------------------------------------------
4391 tmp = p->end;
4392 while (tmp)
4393 {
4394 if (tmp != s)
4395 {
4396 if (tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only)
4397 {
4398 if (tmp->start->value <= min_value)
4399 {
4400 min_value = tmp->start->value;
4401 p->value = min_value;
4402 p->seg = tmp;
4403 }
4404 }
4405 }
4406 tmp = tmp->end_next;
4407 }
4408 }
4409 # endif
4410
4411
4412 /**
4413 * @brief Starts an "offroad" path
4414 *
4415 * This starts a path that is not located on a street. It creates a new route path
4416 * adding only one segment, that leads from pos to dest, and which is not associated with an item.
4417 *
4418 * @param this Not used
4419 * @param pos The starting position for the new path
4420 * @param dst The destination of the new path
4421 * @param dir Not used
4422 * @return The new path
4423 */
4424 static struct route_path *
4425 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst)
4426 {
4427 __F_START__
4428
4429 struct route_path *ret;
4430
4431 ret=g_new0(struct route_path, 1);
4432 ret->in_use = 1;
4433 ret->path_hash = item_hash_new();
4434 route_path_add_line(ret, &pos->c, &dst->c, pos->lenextra + dst->lenextra);
4435 ret->updated = 1;
4436
4437 return2 ret;
4438
4439 __F_END__
4440 }
4441
4442 /**
4443 * @brief Returns a coordinate at a given distance
4444 *
4445 * This function returns the coordinate, where the user will be if he
4446 * follows the current route for a certain distance.
4447 *
4448 * @param this_ The route we're driving upon
4449 * @param dist The distance in meters
4450 * @return The coordinate where the user will be in that distance
4451 */
4452 struct coord route_get_coord_dist(struct route *this_, int dist)
4453 {
4454 __F_START__
4455
4456 int d, l, i, len;
4457 int dx, dy;
4458 double frac;
4459 struct route_path_segment *cur;
4460 struct coord ret;
4461 enum projection pro = route_projection(this_);
4462 struct route_info *dst = route_get_dst(this_);
4463
4464 d = dist;
4465
4466 if (!this_->path2 || pro == projection_none)
4467 {
4468 return2 this_->pos->c;
4469 }
4470
4471 ret = this_->pos->c;
4472 cur = this_->path2->path;
4473 while (cur)
4474 {
4475 if (cur->data->len < d)
4476 {
4477 d -= cur->data->len;
4478 }
4479 else
4480 {
4481 for (i = 0; i < (cur->ncoords - 1); i++)
4482 {
4483 l = d;
4484 len = (int) transform_polyline_length(pro, (cur->c + i), 2);
4485 d -= len;
4486 if (d <= 0)
4487 {
4488 // We interpolate a bit here...
4489 frac = (double) l / len;
4490
4491 dx = (cur->c + i + 1)->x - (cur->c + i)->x;
4492 dy = (cur->c + i + 1)->y - (cur->c + i)->y;
4493
4494 ret.x = (cur->c + i)->x + (frac * dx);
4495 ret.y = (cur->c + i)->y + (frac * dy);
4496 return2 ret;
4497 }
4498 }
4499 return2 cur->c[(cur->ncoords - 1)];
4500 }
4501 cur = cur->next;
4502 }
4503
4504 return2 dst->c;
4505
4506 __F_END__
4507 }
4508
4509 /**
4510 * @brief Creates a new route path
4511 *
4512 * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
4513 * make sure to run route_graph_flood() after changing the destination before using this function.
4514 *
4515 * @param this The route graph to create the route from
4516 * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
4517 * @param pos The starting position of the route
4518 * @param dst The destination of the route
4519 * @param preferences The routing preferences
4520 * @return The new route path
4521 */
4522 static struct route_path *
4523 route_path_new(struct route *rr, struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct vehicleprofile *profile)
4524 {
4525 __F_START__
4526
4527 struct route_graph_segment *s = NULL, *s1 = NULL, *s2 = NULL;
4528 struct route_graph_point *start;
4529 struct route_info *posinfo, *dstinfo;
4530 int segs = 0;
4531 int dir;
4532 int val1 = INT_MAX, val2 = INT_MAX;
4533 int val, val1_new, val2_new;
4534 struct route_path *ret;
4535
4536
4537 dbg(0, "RPNEW:ENTER\n");
4538
4539 dbg(0, "RR_TIM:001\n");
4540
4541 if (! pos->street || !dst->street)
4542 {
4543 // dbg(0, "pos or dest not set\n");
4544 dbg(0, "RR_TIM:002:return\n");
4545
4546 dbg(0, "RPNEW:RET001\n");
4547 return2 NULL;
4548 }
4549
4550 // street direction from tracking
4551 // dbg(0,"street_direction = %i\n",pos->street_direction);
4552
4553
4554 if (profile->mode == 2 || (profile->mode == 0 && pos->lenextra + dst->lenextra > transform_distance(map_projection(pos->street->item.map), &pos->c, &dst->c)))
4555 {
4556 dbg(0, "RPNEW:RET002\n");
4557 return2 route_path_new_offroad(this, pos, dst);
4558 }
4559
4560
4561 // the integer 4000 below is a kind of turn around penalty with a hardcoded value for now
4562
4563 while ((s = route_graph_get_segment(this, pos->street, s)))
4564 {
4565 val = route_value_seg(profile, NULL, s, 2);
4566 if (val != INT_MAX && s->seg_start_out_cost != INT_MAX)
4567 {
4568 val = val * (pos->percent) / 100; // cost om naar het andere uiteinde te rijden !!
4569 val1_new = s->seg_start_out_cost - val;
4570
4571 if (pos->street_direction == -1)
4572 {
4573 val1_new = val1_new + 4000;
4574 }
4575
4576 if (val1_new < val1)
4577 {
4578 val1 = val1_new;
4579 s1 = s;
4580 }
4581 }
4582 val = route_value_seg(profile, NULL, s, -2);
4583 if (val != INT_MAX && s->seg_end_out_cost != INT_MAX)
4584 {
4585 val = val * (100 - pos->percent) / 100;
4586 val2_new = s->seg_end_out_cost - val;
4587
4588 if (pos->street_direction == 1)
4589 {
4590 val2_new = val2_new + 4000;
4591 }
4592
4593 if (val2_new < val2)
4594 {
4595 val2 = val2_new;
4596 s2 = s;
4597 }
4598 }
4599 }
4600 // ------ just calculate the smallest cost to reach destination ----------
4601 // ------ just calculate the smallest cost to reach destination ----------
4602
4603
4604 // val1 en s1 = goedkoopst voorwaarts
4605 // val2 en s2 = goedkoppst achterwaards
4606
4607 if (val1 == INT_MAX && val2 == INT_MAX)
4608 {
4609 //dbg(0, "no route found, pos blocked\n");
4610 dbg(0, "RR_TIM:003:return\n");
4611 dbg(0, "RPNEW:RET003\n");
4612
4613 return2 NULL;
4614 }
4615
4616 if (val1 == val2)
4617 {
4618 val1 = s1->seg_end_out_cost;
4619 val2 = s2->seg_start_out_cost;
4620 }
4621 if (val1 < val2)
4622 {
4623 start = s1->start;
4624 s = s1;
4625 dir = 1;
4626 }
4627 else
4628 {
4629 start = s2->end;
4630 s = s2;
4631 dir = -1;
4632 }
4633
4634 // if (pos->street_direction && dir != pos->street_direction && profile->turn_around_penalty)
4635 // {
4636 // if (!route_graph_segment_match(this->avoid_seg,s))
4637 // {
4638 // dbg(0,"avoid current segment\n");
4639 // if (this->avoid_seg)
4640 // route_graph_set_traffic_distortion(this, this->avoid_seg, 0);
4641 // this->avoid_seg=s;
4642 // route_graph_set_traffic_distortion(this, this->avoid_seg, profile->turn_around_penalty);
4643 // route_graph_reset(this);
4644 // route_graph_flood_frugal(this, dst, pos, profile, NULL);
4645 // return route_path_new(NULL, this, oldpath, pos, dst, profile);
4646 // }
4647 // }
4648 ret=g_new0(struct route_path, 1);
4649 ret->in_use = 1;
4650 ret->updated = 1;
4651 if (pos->lenextra)
4652 {
4653 route_path_add_line(ret, &pos->c, &pos->lp, pos->lenextra);
4654 }
4655
4656 ret->path_hash = item_hash_new();
4657 dstinfo = NULL;
4658 posinfo = pos;
4659 dbg(0, "RR_TIM:004\n");
4660
4661 clock_t s_;
4662 s_ = debug_measure_start();
4663
4664
4665 // ------- build the real route here ------------------------
4666 // ------- build the real route here ------------------------
4667 while (s && !dstinfo)
4668 { /* following start->seg, which indicates the least costly way to reach our destination */
4669 segs++;
4670 if (s->start == start)
4671 {
4672 if (item_is_equal(s->data.item, dst->street->item) && (s->end_from_seg == s || !posinfo))
4673 {
4674 dstinfo = dst;
4675 }
4676 if (!route_path_add_item_from_graph(ret, oldpath, s, 1, posinfo, dstinfo))
4677 {
4678 ret->updated = 0;
4679 }
4680
4681 start = s->end; // new start point
4682 s = s->end_from_seg;
4683 }
4684 else
4685 {
4686 if (item_is_equal(s->data.item, dst->street->item) && (s->start_from_seg == s || !posinfo))
4687 {
4688 dstinfo = dst;
4689 }
4690 if (!route_path_add_item_from_graph(ret, oldpath, s, -1, posinfo, dstinfo))
4691 {
4692 ret->updated = 0;
4693 }
4694 start = s->start; // new start point
4695 s = s->start_from_seg;
4696 }
4697
4698 posinfo = NULL;
4699 }
4700 // ------- build the real route here ------------------------
4701 // ------- build the real route here ------------------------
4702
4703 debug_mrp("RR_TIM:005", debug_measure_end(s_));
4704
4705 #if 0
4706 if (dst->lenextra)
4707 {
4708 //
4709 route_path_add_line(ret, &dst->lp, &dst->c, dst->lenextra);
4710 }
4711 #endif
4712
4713 if (dst->lenextra)
4714 {
4715 struct route_info *rr_last = g_list_last(rr->destinations)->data;
4716
4717 //dbg(0,"l extra1=%d\n", pos->lenextra);
4718 if (rr_last != dst)
4719 {
4720 dbg(0, "RPNEW:PP:not dst\n");
4721 route_path_add_line_as_waypoint(ret, &dst->lp, &dst->c, dst->lenextra);
4722 }
4723 else
4724 {
4725 dbg(0, "RPNEW:PP:IS dst\n");
4726 route_path_add_line(ret, &dst->lp, &dst->c, dst->lenextra);
4727 }
4728 }
4729
4730
4731 //dbg(1, "%d segments\n", segs);
4732
4733 // dbg(0, "RR_TIM:099:segs=%d\n", segs);
4734
4735 dbg(0, "RPNEW:LEAVE\n");
4736
4737 return2 ret;
4738
4739 __F_END__
4740 }
4741
4742 static int route_graph_build_next_map(struct route_graph *rg)
4743 {
4744 __F_START__
4745
4746 do
4747 {
4748 rg->m = mapset_next(rg->h, 2);
4749 if (!rg->m)
4750 {
4751 return2 0;
4752 }
4753
4754 #if 0
4755 struct attr map_name_attr;
4756 if (map_get_attr(rg->m, attr_name, &map_name_attr, NULL))
4757 {
4758 if (strncmp("_ms_sdcard_map:-special-:worldmap", map_name_attr.u.str, 34) == 0)
4759 {
4760 continue;
4761 }
4762 }
4763 #endif
4764
4765 map_rect_destroy(rg->mr);
4766 rg->mr = map_rect_new(rg->m, rg->sel);
4767 }
4768 while (!rg->mr);
4769
4770 return2 1;
4771
4772 __F_END__
4773 }
4774
4775 int is_turn_allowed(struct route_graph_point *p, struct route_graph_segment *from, struct route_graph_segment *to)
4776 {
4777 struct route_graph_point *prev, *next;
4778 struct route_graph_segment *tmp1, *tmp2;
4779
4780 if (item_is_equal(from->data.item, to->data.item))
4781 {
4782 return 0;
4783 }
4784
4785 if (from->start == p)
4786 prev = from->end;
4787 else
4788 prev = from->start;
4789
4790 if (to->start == p)
4791 next = to->end;
4792 else
4793 next = to->start;
4794
4795 tmp1 = p->end;
4796
4797 while (tmp1)
4798 {
4799 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))
4800 {
4801 tmp2 = p->start;
4802 //dbg(1, "found %s (0x%x,0x%x) (0x%x,0x%x)-(0x%x,0x%x) %p-%p\n",
4803 // item_to_name(tmp1->data.item.type), tmp1->data.item.id_hi,
4804 // tmp1->data.item.id_lo, tmp1->start->c.x, tmp1->start->c.y,
4805 // tmp1->end->c.x, tmp1->end->c.y, tmp1->start, tmp1->end);
4806 while (tmp2)
4807 {
4808 //dbg(
4809 // 1,
4810 // "compare %s (0x%x,0x%x) (0x%x,0x%x)-(0x%x,0x%x) %p-%p\n",
4811 // item_to_name(tmp2->data.item.type),
4812 // tmp2->data.item.id_hi, tmp2->data.item.id_lo,
4813 // tmp2->start->c.x, tmp2->start->c.y, tmp2->end->c.x,
4814 // tmp2->end->c.y, tmp2->start, tmp2->end);
4815 if (item_is_equal(tmp1->data.item, tmp2->data.item))
4816 {
4817 break;
4818 }
4819 tmp2 = tmp2->start_next;
4820 }
4821 //dbg(1, "tmp2=%p\n", tmp2);
4822 if (tmp2)
4823 {
4824 //dbg(1, "%s tmp2->end=%p next=%p\n",
4825 // item_to_name(tmp1->data.item.type), tmp2->end, next);
4826 }
4827 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)
4828 {
4829 //dbg(
4830 // 1,
4831 // "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x not allowed (no)\n",
4832 // prev->c.x, prev->c.y, p->c.x, p->c.y, next->c.x,
4833 // next->c.y);
4834 return 0;
4835 }
4836 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))
4837 {
4838 //dbg(
4839 // 1,
4840 // "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x not allowed (only)\n",
4841 // prev->c.x, prev->c.y, p->c.x, p->c.y, next->c.x,
4842 // next->c.y);
4843 return 0;
4844 }
4845 }
4846 tmp1 = tmp1->end_next;
4847 }
4848 //dbg(1, "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x allowed\n", prev->c.x,
4849 // prev->c.y, p->c.x, p->c.y, next->c.x, next->c.y);
4850 return 1;
4851
4852 }
4853
4854 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)
4855 {
4856 struct route_graph_segment_data data;
4857 data.flags = s->data.flags | flags;
4858 data.offset = 1;
4859 data.maxspeed = -1;
4860 data.item = &s->data.item;
4861 data.len = s->data.len + 1;
4862
4863 if (s->data.flags & NAVIT_AF_SPEED_LIMIT)
4864 data.maxspeed = RSD_MAXSPEED(&s->data);
4865
4866 if (s->data.flags & NAVIT_AF_SEGMENTED)
4867 data.offset = RSD_OFFSET(&s->data);
4868
4869 //dbg(1, "cloning segment from %p (0x%x,0x%x) to %p (0x%x,0x%x)\n", start,
4870 // start->c.x, start->c.y, end, end->c.x, end->c.y);
4871 route_graph_add_segment(this, start, end, &data);
4872
4873 }
4874
4875 static void route_graph_process_restriction_segment(struct route_graph *this, struct route_graph_point *p, struct route_graph_segment *s, int dir)
4876 {
4877 struct route_graph_segment *tmp;
4878 struct route_graph_point *pn;
4879 struct coord c = p->c;
4880 int dx = 0;
4881 int dy = 0;
4882 c.x += dx;
4883 c.y += dy;
4884
4885 //dbg(1, "From %s %d,%d\n", item_to_name(s->data.item.type), dx, dy);
4886 pn = route_graph_point_new(this, &c);
4887 if (dir > 0)
4888 { /* going away */
4889 //dbg(1, "other 0x%x,0x%x\n", s->end->c.x, s->end->c.y);
4890 //dbg(0, "fl 001 = %x\n", s->data.flags);
4891 if (route_get_real_oneway_flag(s->data.flags, NAVIT_AF_ONEWAY))
4892 {
4893 //dbg(1, "Not possible\n");
4894 return;
4895 }
4896 // route_graph_clone_segment(this, s, pn, s->end, NAVIT_AF_ONEWAYREV|(s->data.flags & NAVIT_AF_ONEWAY_BICYCLE_NO));
4897 route_graph_clone_segment(this, s, pn, s->end, NAVIT_AF_ONEWAYREV);
4898 }
4899 else
4900 { /* coming in */
4901 //dbg(1, "other 0x%x,0x%x\n", s->start->c.x, s->start->c.y);
4902 //dbg(0, "fl 002 = %x\n", s->data.flags);
4903 if (route_get_real_oneway_flag(s->data.flags, NAVIT_AF_ONEWAYREV))
4904 {
4905 //dbg(1, "Not possible\n");
4906 return;
4907 }
4908 // route_graph_clone_segment(this, s, s->start, pn, NAVIT_AF_ONEWAY|(s->data.flags & NAVIT_AF_ONEWAY_BICYCLE_NO));
4909 route_graph_clone_segment(this, s, s->start, pn, NAVIT_AF_ONEWAY);
4910 }
4911
4912 tmp = p->start;
4913 while (tmp)
4914 {
4915 if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only && !(route_get_real_oneway_flag(tmp->data.flags, NAVIT_AF_ONEWAYREV)) && is_turn_allowed(p, s, tmp))
4916 {
4917 //dbg(0, "fl 003 = %x\n", tmp->data.flags);
4918 // route_graph_clone_segment(this, tmp, pn, tmp->end, NAVIT_AF_ONEWAY|(tmp->data.flags & NAVIT_AF_ONEWAY_BICYCLE_NO));
4919 route_graph_clone_segment(this, tmp, pn, tmp->end, NAVIT_AF_ONEWAY);
4920 //dbg(1, "To start %s\n", item_to_name(tmp->data.item.type));
4921 }
4922 tmp = tmp->start_next;
4923 }
4924
4925 tmp = p->end;
4926 while (tmp)
4927 {
4928 if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only && !(route_get_real_oneway_flag(tmp->data.flags, NAVIT_AF_ONEWAY)) && is_turn_allowed(p, s, tmp))
4929 {
4930 //dbg(0, "fl 004 = %x\n", tmp->data.flags);
4931 // route_graph_clone_segment(this, tmp, tmp->start, pn, NAVIT_AF_ONEWAYREV|(tmp->data.flags & NAVIT_AF_ONEWAY_BICYCLE_NO));
4932 route_graph_clone_segment(this, tmp, tmp->start, pn, NAVIT_AF_ONEWAYREV);
4933 //dbg(1, "To end %s\n", item_to_name(tmp->data.item.type));
4934 }
4935 tmp = tmp->end_next;
4936 }
4937
4938 }
4939
4940 // -- UNUSED --
4941 // -- UNUSED --
4942 static void route_graph_process_traffic_light_segment(struct route_graph *this, struct route_graph_point *p, struct route_graph_segment *s, int dir)
4943 {
4944 __F_START__
4945
4946 //struct route_graph_segment *tmp;
4947 //s->data.len = s->data.len + global_traffic_light_delay;
4948
4949 __F_END__
4950 }
4951
4952
4953 static void route_graph_process_restriction_point(struct route_graph *this, struct route_graph_point *p)
4954 {
4955
4956 struct route_graph_segment *tmp;
4957
4958 // -------------------------------------------------------------
4959 // p->start ==> a list of all streets that start from this point
4960 // -------------------------------------------------------------
4961 tmp = p->start;
4962 //dbg(1, "node 0x%x,0x%x\n", p->c.x, p->c.y);
4963 while (tmp)
4964 {
4965 if (tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only)
4966 {
4967 route_graph_process_restriction_segment(this, p, tmp, 1);
4968 }
4969 tmp = tmp->start_next;
4970 }
4971
4972 // -------------------------------------------------------------
4973 // p->end ==> a list of all streets that end at this point
4974 // -------------------------------------------------------------
4975 tmp = p->end;
4976 while (tmp)
4977 {
4978 if (tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only)
4979 {
4980 route_graph_process_restriction_segment(this, p, tmp, -1);
4981 }
4982 tmp = tmp->end_next;
4983 }
4984
4985 p->flags |= RP_TURN_RESTRICTION_RESOLVED;
4986
4987 }
4988
4989 // -- UNUSED --
4990 // -- UNUSED --
4991 static void route_graph_process_traffic_light_point(struct route_graph *this, struct route_graph_point *p)
4992 {
4993 __F_START__
4994
4995 struct route_graph_segment *tmp;
4996
4997 // -------------------------------------------------------------
4998 // p->start ==> a list of all streets that start from this point
4999 // -------------------------------------------------------------
5000 tmp = p->start;
5001 while (tmp)
5002 {
5003 route_graph_process_traffic_light_segment(this, p, tmp, 1);
5004 tmp = tmp->start_next;
5005 }
5006
5007 // -------------------------------------------------------------
5008 // p->end ==> a list of all streets that end at this point
5009 // -------------------------------------------------------------
5010 tmp = p->end;
5011 while (tmp)
5012 {
5013 route_graph_process_traffic_light_segment(this, p, tmp, -1);
5014 tmp = tmp->end_next;
5015 }
5016
5017 // p->flags |= RP_TRAFFIC_LIGHT_RESOLVED;
5018
5019 __F_END__
5020 }
5021
5022
5023 static void route_graph_process_restrictions(struct route_graph *this)
5024 {
5025 __F_START__
5026
5027 struct route_graph_point *curr;
5028 int i;
5029 //dbg(1, "enter\n");
5030 for (i = 0; i < HASH_SIZE; i++)
5031 {
5032 curr = this->hash[i];
5033 while (curr)
5034 {
5035 if (curr->flags & RP_TURN_RESTRICTION)
5036 {
5037 route_graph_process_restriction_point(this, curr);
5038 }
5039 curr = curr->hash_next;
5040 }
5041 }
5042
5043 __F_END__
5044 }
5045
5046 // -- UNUSED --
5047 // -- UNUSED --
5048 static void route_graph_process_traffic_lights(struct route_graph *this)
5049 {
5050 __F_START__
5051
5052 // check if we should calc delay for traffic lights?
5053 if (global_traffic_light_delay > 0)
5054 {
5055 struct route_graph_point *curr;
5056 int i;
5057 //dbg(1, "enter\n");
5058 for (i = 0; i < HASH_SIZE; i++)
5059 {
5060 curr = this->hash[i];
5061 while (curr)
5062 {
5063 if (curr->flags & RP_TRAFFIC_LIGHT)
5064 {
5065 route_graph_process_traffic_light_point(this, curr);
5066 }
5067 curr = curr->hash_next;
5068 }
5069 }
5070 }
5071
5072 __F_END__
5073 }
5074
5075
5076 static void route_graph_build_done(struct route_graph *rg, int cancel)
5077 {
5078 __F_START__
5079
5080 //dbg(1, "cancel=%d\n", cancel);
5081 if (rg->idle_ev)
5082 {
5083 event_remove_idle(rg->idle_ev);
5084 rg->idle_ev = NULL;
5085 }
5086
5087 if (rg->idle_cb)
5088 {
5089 callback_destroy(rg->idle_cb);
5090 rg->idle_cb = NULL;
5091 }
5092
5093 map_rect_destroy(rg->mr);
5094 mapset_close(rg->h);
5095 route_free_selection(rg->sel);
5096 rg->mr = NULL;
5097 rg->h = NULL;
5098 rg->sel = NULL;
5099
5100 if (!cancel)
5101 {
5102 route_graph_process_restrictions(rg);
5103 // --unused-- route_graph_process_traffic_lights(rg);
5104 //dbg(0, "callback\n");
5105 callback_call_0(rg->done_cb);
5106 }
5107
5108 rg->busy = 0;
5109
5110 __F_END__
5111 }
5112
5113 // this function gets called in a loop until route is ready ----------
5114 // this function gets called in a loop until route is ready ----------
5115 // this function gets called in a loop until route is ready ----------
5116 static void route_graph_build_idle(struct route_graph *rg, struct vehicleprofile *profile)
5117 {
5118 __F_START__
5119
5120 #ifdef DEBUG_GLIB_MEM_FUNCTIONS
5121 g_mem_profile();
5122 #endif
5123
5124 // int count = 1000; // *ORIG* value
5125 // int count = 1200; // process 5000 items in one step
5126 int count = 4000; // process 15000 items in one step
5127 struct item *item;
5128
5129 while (count > 0)
5130 {
5131 // loop until an item is found ---------
5132 for (;;)
5133 {
5134 item = map_rect_get_item(rg->mr);
5135 if (item)
5136 {
5137 break;
5138 }
5139
5140 if (!route_graph_build_next_map(rg))
5141 {
5142 route_graph_build_done(rg, 0);
5143 return2;
5144 }
5145 }
5146 // loop until an item is found ---------
5147
5148
5149 if (item->type == type_traffic_distortion)
5150 {
5151 route_process_traffic_distortion(rg, item);
5152 }
5153 /*
5154 else if (
5155 (item->type == type_street_2_city) ||
5156 (item->type == type_street_3_city) ||
5157 (item->type == type_street_4_city) ||
5158 (item->type == type_highway_city) ||
5159 (item->type == type_street_1_land) ||
5160 (item->type == type_street_2_land) ||
5161 (item->type == type_street_3_land) ||
5162 (item->type == type_street_4_land) ||
5163 (item->type == type_street_n_lanes) ||
5164 (item->type == type_highway_land) ||
5165 (item->type == type_ramp) ||
5166 )
5167 {
5168 */
5169 /*
5170 ITEM(street_0)
5171 ITEM(street_1_city)
5172 ITEM(street_2_city)
5173 ITEM(street_3_city)
5174 ITEM(street_4_city)
5175 ITEM(highway_city)
5176 ITEM(street_1_land)
5177 ITEM(street_2_land)
5178 ITEM(street_3_land)
5179 ITEM(street_4_land)
5180 ITEM(street_n_lanes)
5181 ITEM(highway_land)
5182 ITEM(ramp)
5183 */
5184 // route_process_sharp_turn(rg, item);
5185 // }
5186 else if (item->type == type_traffic_signals)
5187 {
5188 route_process_traffic_light(rg, item);
5189 }
5190 else if (item->type == type_street_turn_restriction_no || item->type == type_street_turn_restriction_only)
5191 {
5192 route_process_turn_restriction(rg, item);
5193 }
5194 else
5195 {
5196 //dbg(0,"*[xx]type=%s\n", item_to_name(item->type));
5197 route_process_street_graph(rg, item, profile);
5198 }
5199
5200 count--;
5201 }
5202
5203 __F_END__
5204 }
5205
5206 /**
5207 * @brief Builds a new route graph from a mapset
5208 *
5209 * This function builds a new route graph from a map. Please note that this function does not
5210 * add any routing information to the route graph - this has to be done via the route_graph_flood()
5211 * function.
5212 *
5213 * The function does not create a graph covering the whole map, but only covering the rectangle
5214 * between c1 and c2.
5215 *
5216 * @param ms The mapset to build the route graph from
5217 * @param c1 Corner 1 of the rectangle to use from the map
5218 * @param c2 Corner 2 of the rectangle to use from the map
5219 * @param done_cb The callback which will be called when graph is complete
5220 * @return The new route graph.
5221 */
5222 static struct route_graph *
5223 route_graph_build(struct mapset *ms, struct coord *c, int count, struct callback *done_cb, int async, struct vehicleprofile *profile, int try_harder)
5224 {
5225 __F_START__
5226
5227 dbg(0, "RR_TIM:rgb:001\n");
5228
5229 struct route_graph *ret=g_new0(struct route_graph, 1);
5230
5231 ret->sel = route_calc_selection(c, count, try_harder);
5232
5233 ret->h = mapset_open(ms);
5234 ret->done_cb = done_cb;
5235 ret->busy = 1;
5236
5237 if (route_graph_build_next_map(ret))
5238 {
5239 // ------ xxxxxx ----
5240 // dbg(0,"async=%d\n", async);
5241 if (async)
5242 {
5243 //dbg(0,"route_graph_build_idle sync callback\n");
5244 ret->idle_cb = callback_new_2(callback_cast(route_graph_build_idle), ret, profile);
5245 callback_add_names(ret->idle_cb, "route_graph_build", "route_graph_build_idle");
5246 ret->idle_ev = event_add_idle(10, ret->idle_cb);
5247 }
5248 else
5249 {
5250 // ?? do we need this ?? // route_graph_build_idle(ret, profile);
5251 }
5252 }
5253 else
5254 {
5255 route_graph_build_done(ret, 0);
5256 }
5257
5258 dbg(0, "RR_TIM:rgb:099\n");
5259
5260 return2 ret;
5261
5262 __F_END__
5263 }
5264
5265 static void route_graph_update_done(struct route *this, struct callback *cb)
5266 {
5267 __F_START__
5268
5269 dbg(0, "RR_TIM:gud:001\n");
5270
5271 route_graph_flood(this->graph, this->current_dst, this->pos, this->vehicleprofile, cb);
5272
5273 dbg(0, "RR_TIM:gud:099\n");
5274
5275 __F_END__
5276 }
5277
5278 /**
5279 * @brief Updates the route graph
5280 *
5281 * This updates the route graph after settings in the route have changed. It also
5282 * adds routing information afterwards by calling route_graph_flood().
5283 *
5284 * @param this The route to update the graph for
5285 */
5286 static void route_graph_update(struct route *this, struct callback *cb, int async)
5287 {
5288 __F_START__
5289
5290 dbg(0, "RR_TIM:gu:001\n");
5291
5292 struct attr route_status;
5293 struct coord *c = g_alloca(sizeof(struct coord) * (1 + g_list_length(this->destinations)));
5294 int i = 0;
5295 GList *tmp;
5296
5297 route_status.type = attr_route_status;
5298 route_graph_destroy(this->graph);
5299 this->graph = NULL;
5300 callback_destroy(this->route_graph_done_cb);
5301
5302 this->route_graph_done_cb = callback_new_2(callback_cast(route_graph_update_done), this, cb);
5303 callback_add_names(this->route_graph_done_cb, "route_graph_update", "route_graph_update_done");
5304
5305 route_status.u.num = route_status_building_graph;
5306 route_set_attr(this, &route_status);
5307
5308 c[i++] = this->pos->c;
5309 tmp = this->destinations;
5310 while (tmp)
5311 {
5312 struct route_info *dst = tmp->data;
5313 c[i++] = dst->c;
5314 tmp = g_list_next(tmp);
5315 }
5316
5317 this->graph = route_graph_build(this->ms, c, i, this->route_graph_done_cb, async, this->vehicleprofile, this->try_harder);
5318
5319 if (!async)
5320 {
5321 while (this->graph->busy)
5322 {
5323 route_graph_build_idle(this->graph, this->vehicleprofile);
5324 }
5325 }
5326
5327 dbg(0, "RR_TIM:gu:099\n");
5328
5329 __F_END__
5330 }
5331
5332 /**
5333 * @brief Gets street data for an item
5334 *
5335 * @param item The item to get the data for
5336 * @return Street data for the item
5337 */
5338 struct street_data *
5339 street_get_data(struct item *item)
5340 {
5341 //// dbg(0, "enter\n");
5342
5343 int count = 0, *flags;
5344 struct street_data *ret = NULL, *ret1;
5345 struct attr flags_attr, maxspeed_attr;
5346 const int step = 128;
5347 int c;
5348
5349 do
5350 {
5351 ret1 = g_realloc(ret, sizeof(struct street_data) + (count + step) * sizeof(struct coord));
5352 if (!ret1)
5353 {
5354 if (ret)
5355 g_free(ret);
5356 return NULL;
5357 }
5358 ret = ret1;
5359 c = item_coord_get(item, &ret->c[count], step);
5360 count += c;
5361 }
5362 while (c && c == step);
5363
5364 ret1 = g_realloc(ret, sizeof(struct street_data) + count * sizeof(struct coord));
5365
5366 if (ret1)
5367 ret = ret1;
5368
5369 ret->item = *item;
5370 ret->count = count;
5371
5372 if (item_attr_get(item, attr_flags, &flags_attr))
5373 {
5374 ret->flags = flags_attr.u.num;
5375 }
5376 else
5377 {
5378 flags = item_get_default_flags(item->type);
5379
5380 if (flags)
5381 ret->flags = *flags;
5382 else
5383 ret->flags = 0;
5384 }
5385
5386 ret->maxspeed = -1;
5387 if (ret->flags & NAVIT_AF_SPEED_LIMIT)
5388 {
5389 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr))
5390 {
5391 ret->maxspeed = maxspeed_attr.u.num;
5392 }
5393 }
5394
5395 return ret;
5396 }
5397
5398 /**
5399 * @brief Copies street data
5400 *
5401 * @param orig The street data to copy
5402 * @return The copied street data
5403 */
5404 struct street_data *
5405 street_data_dup(struct street_data *orig)
5406 {
5407 //// dbg(0, "enter\n");
5408
5409 struct street_data *ret;
5410 int size = sizeof(struct street_data) + orig->count * sizeof(struct coord);
5411
5412 ret = g_malloc(size);
5413 // xxx global_route_memory_size = global_route_memory_size + seg_size + seg_dat_size;
5414 // xxx dbg(0,"route mem=%lu\n", global_route_memory_size);
5415 memcpy(ret, orig, size);
5416
5417 return ret;
5418 }
5419
5420 /**
5421 * @brief Frees street data
5422 *
5423 * @param sd Street data to be freed
5424 */
5425 void street_data_free(struct street_data *sd)
5426 {
5427 //// dbg(0, "enter\n");
5428
5429 g_free(sd);
5430 }
5431
5432 /**
5433 * @brief Finds the nearest street to a given coordinate (result should be a road that is in vehicle profile for routing!)
5434 *
5435 * @param ms The mapset to search in for the street
5436 * @param pc The coordinate to find a street nearby
5437 * @return The nearest street
5438 */
5439 static struct route_info *
5440 route_find_nearest_street(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc)
5441 {
5442 __F_START__
5443
5444 struct route_info *ret = NULL;
5445 int max_dist = 1000; // was 1000 originally!!
5446 struct map_selection *sel;
5447 int dist, mindist = 0, pos;
5448 struct mapset_handle *h;
5449 struct map *m;
5450 struct map_rect *mr;
5451 struct item *item;
5452 struct coord lp;
5453 struct street_data *sd;
5454 struct coord c;
5455 struct coord_geo g;
5456 struct roadprofile *roadp;
5457
5458 ret=g_new0(struct route_info, 1);
5459 mindist = INT_MAX;
5460
5461 h = mapset_open(ms);
5462 while ((m = mapset_next(h, 2)))
5463 {
5464 c.x = pc->x;
5465 c.y = pc->y;
5466
5467 if (map_projection(m) != pc->pro)
5468 {
5469 transform_to_geo(pc->pro, &c, &g);
5470 transform_from_geo(map_projection(m), &g, &c);
5471 }
5472
5473 sel = route_rect(18, &c, &c, 0, max_dist);
5474
5475 if (!sel)
5476 {
5477 continue;
5478 }
5479
5480 mr = map_rect_new(m, sel);
5481 //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);
5482
5483 if (!mr)
5484 {
5485 map_selection_destroy(sel);
5486 continue;
5487 }
5488
5489 while ((item = map_rect_get_item(mr)))
5490 {
5491 roadp = vehicleprofile_get_roadprofile(vehicleprofile, item->type);
5492 if (roadp)
5493 {
5494 if (item_get_default_flags(item->type))
5495 {
5496 sd = street_get_data(item);
5497 if (!sd)
5498 {
5499 continue;
5500 }
5501
5502 //dbg(0,"*type=%s\n", item_to_name(item->type));
5503
5504 dist = transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
5505
5506 if (dist < mindist && ((sd->flags & route_get_real_oneway_mask(sd->flags, vehicleprofile->flags_forward_mask)) == vehicleprofile->flags || (sd->flags & route_get_real_oneway_mask(sd->flags, vehicleprofile->flags_reverse_mask)) == vehicleprofile->flags))
5507 {
5508 mindist = dist;
5509 if (ret->street)
5510 {
5511 street_data_free(ret->street);
5512 }
5513 ret->c = c;
5514 ret->lp = lp;
5515 ret->pos = pos;
5516 ret->street = sd;
5517
5518 //dbg(0,"*(N)type=%s\n", item_to_name(item->type));
5519 /*
5520 struct attr street_name_attr;
5521 if (item_attr_get(item, attr_label, &street_name_attr))
5522 {
5523 dbg(0, "*name=%s\n", street_name_attr.u.str);
5524 }
5525 else if (item_attr_get(item, attr_street_name, &street_name_attr))
5526 {
5527 dbg(0, "*name=%s\n", street_name_attr.u.str);
5528 }
5529 */
5530 //dbg(0, "dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
5531 }
5532 else
5533 {
5534 street_data_free(sd);
5535 }
5536 }
5537 }
5538 }
5539 map_selection_destroy(sel);
5540 map_rect_destroy(mr);
5541 }
5542 mapset_close(h);
5543
5544 if (!ret->street || mindist > max_dist * max_dist)
5545 {
5546 if (ret->street)
5547 {
5548 street_data_free(ret->street);
5549 //dbg(0, "Much too far %d > %d\n", mindist, max_dist);
5550 }
5551
5552 //dbg(0,"return NULL\n");
5553
5554 g_free(ret);
5555 ret = NULL;
5556 }
5557
5558 return2 ret;
5559
5560 __F_END__
5561 }
5562
5563
5564
5565 static struct route_info *
5566 route_find_nearest_street_harder(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc, int max_dist_wanted)
5567 {
5568 __F_START__
5569
5570 struct route_info *ret = NULL;
5571 int max_dist = max_dist_wanted; // was 1000 originally!!
5572 struct map_selection *sel;
5573 int dist, mindist = 0, pos;
5574 struct mapset_handle *h;
5575 struct map *m;
5576 struct map_rect *mr;
5577 struct item *item;
5578 struct coord lp;
5579 struct street_data *sd;
5580 struct coord c;
5581 struct coord_geo g;
5582 struct roadprofile *roadp;
5583
5584 ret=g_new0(struct route_info, 1);
5585 mindist = INT_MAX;
5586
5587 h = mapset_open(ms);
5588 while ((m = mapset_next(h, 2)))
5589 {
5590 c.x = pc->x;
5591 c.y = pc->y;
5592
5593 if (map_projection(m) != pc->pro)
5594 {
5595 transform_to_geo(pc->pro, &c, &g);
5596 transform_from_geo(map_projection(m), &g, &c);
5597 }
5598
5599 sel = route_rect(18, &c, &c, 0, max_dist);
5600
5601 if (!sel)
5602 {
5603 continue;
5604 }
5605
5606 //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);
5607
5608 mr = map_rect_new(m, sel);
5609
5610 if (!mr)
5611 {
5612 map_selection_destroy(sel);
5613 continue;
5614 }
5615
5616 while ((item = map_rect_get_item(mr)))
5617 {
5618 roadp = vehicleprofile_get_roadprofile(vehicleprofile, item->type);
5619 if (roadp)
5620 {
5621 if (item_get_default_flags(item->type))
5622 {
5623 sd = street_get_data(item);
5624 if (!sd)
5625 {
5626 continue;
5627 }
5628
5629 //dbg(0,"*type=%s\n", item_to_name(item->type));
5630
5631 dist = transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
5632
5633 if (dist < mindist && ((sd->flags & route_get_real_oneway_mask(sd->flags, vehicleprofile->flags_forward_mask)) == vehicleprofile->flags || (sd->flags & route_get_real_oneway_mask(sd->flags, vehicleprofile->flags_reverse_mask)) == vehicleprofile->flags))
5634 {
5635 mindist = dist;
5636 if (ret->street)
5637 {
5638 street_data_free(ret->street);
5639 }
5640 ret->c = c;
5641 ret->lp = lp;
5642 ret->pos = pos;
5643 ret->street = sd;
5644
5645 /*
5646 dbg(0,"*(h)type=%s\n", item_to_name(item->type));
5647 struct attr street_name_attr;
5648 if (item_attr_get(item, attr_label, &street_name_attr))
5649 {
5650 dbg(0, "*name=%s\n", street_name_attr.u.str);
5651 }
5652 else if (item_attr_get(item, attr_street_name, &street_name_attr))
5653 {
5654 dbg(0, "*name=%s\n", street_name_attr.u.str);
5655 }
5656 */
5657 //dbg(0, "dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
5658 }
5659 else
5660 {
5661 street_data_free(sd);
5662 }
5663 }
5664 }
5665 }
5666 map_selection_destroy(sel);
5667 map_rect_destroy(mr);
5668 }
5669 mapset_close(h);
5670
5671 if (!ret->street || mindist > (max_dist * max_dist))
5672 {
5673
5674 //dbg(0,"no street found!\n");
5675
5676 if (ret->street)
5677 {
5678 street_data_free(ret->street);
5679 //dbg(0, "Much too far %d > %d\n", mindist, max_dist);
5680 }
5681 g_free(ret);
5682 ret = NULL;
5683 }
5684
5685 return2 ret;
5686
5687 __F_END__
5688 }
5689
5690
5691 /**
5692 * @brief Destroys a route_info
5693 *
5694 * @param info The route info to be destroyed
5695 */
5696 void route_info_free(struct route_info *inf)
5697 {
5698 __F_START__
5699
5700 if (!inf)
5701 {
5702 return2;
5703 }
5704
5705 if (inf->street)
5706 street_data_free(inf->street);
5707
5708 g_free(inf);
5709
5710 __F_END__
5711 }
5712
5713 #include "point.h"
5714
5715 /**
5716 * @brief Returns street data for a route info
5717 *
5718 * @param rinf The route info to return the street data for
5719 * @return Street data for the route info
5720 */
5721 struct street_data *
5722 route_info_street(struct route_info *rinf)
5723 {
5724 __F_START__
5725
5726 return2 rinf->street;
5727
5728 __F_END__
5729 }
5730
5731 #if 0
5732 struct route_crossings *
5733 route_crossings_get(struct route *this, struct coord *c)
5734 {
5735 struct route_point *pnt;
5736 struct route_segment *seg;
5737 int crossings=0;
5738 struct route_crossings *ret;
5739
5740 pnt=route_graph_get_point(this, c);
5741 seg=pnt->start;
5742 while (seg)
5743 {
5744 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
5745 crossings++;
5746 seg=seg->start_next;
5747 }
5748 seg=pnt->end;
5749 while (seg)
5750 {
5751 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
5752 crossings++;
5753 seg=seg->end_next;
5754 }
5755 ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
5756 ret->count=crossings;
5757 return ret;
5758 }
5759 #endif
5760
5761 struct map_rect_priv
5762 {
5763 struct route_info_handle *ri;
5764 enum attr_type attr_next;
5765 int pos;
5766 struct map_priv *mpriv;
5767 struct item item;
5768 unsigned int last_coord;
5769 struct route_path *path;
5770 struct route_path_segment *seg, *seg_next;
5771 struct route_graph_point *point;
5772 struct route_graph_segment *rseg;
5773 char *str;
5774 int hash_bucket;
5775 struct coord *coord_sel; /**< Set this to a coordinate if you want to filter for just a single route graph point */
5776 struct route_graph_point_iterator it;
5777 };
5778
5779 static void rm_coord_rewind(void *priv_data)
5780 {
5781 //// dbg(0, "enter\n");
5782
5783 struct map_rect_priv *mr = priv_data;
5784 mr->last_coord = 0;
5785 }
5786
5787 static void rm_attr_rewind(void *priv_data)
5788 {
5789 //// dbg(0, "enter\n");
5790
5791 struct map_rect_priv *mr = priv_data;
5792 mr->attr_next = attr_street_item;
5793 }
5794
5795 static int rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
5796 {
5797 //// dbg(0, "enter\n");
5798
5799 struct map_rect_priv *mr = priv_data;
5800 struct route_path_segment *seg = mr->seg;
5801 struct route *route = mr->mpriv->route;
5802
5803 if ((mr->item.type != type_street_route) && (mr->item.type != type_street_route_waypoint))
5804 {
5805 return 0;
5806 }
5807
5808 attr->type = attr_type;
5809 switch (attr_type)
5810 {
5811 case attr_any:
5812 while (mr->attr_next != attr_none)
5813 {
5814 if (rm_attr_get(priv_data, mr->attr_next, attr))
5815 return 1;
5816 }
5817 return 0;
5818 case attr_maxspeed:
5819 mr->attr_next = attr_street_item;
5820 if (seg && seg->data->flags & NAVIT_AF_SPEED_LIMIT)
5821 {
5822 attr->u.num = RSD_MAXSPEED(seg->data);
5823 }
5824 else
5825 {
5826 return 0;
5827 }
5828 return 1;
5829 case attr_details: // use this dummy attr "details" to get street flags
5830 mr->attr_next = attr_street_item;
5831 attr->u.num = seg->data->flags;
5832 return 1;
5833 case attr_street_item:
5834 mr->attr_next = attr_direction;
5835 if (seg && seg->data->item.map)
5836 attr->u.item = &seg->data->item;
5837 else
5838 return 0;
5839 return 1;
5840 case attr_direction:
5841 mr->attr_next = attr_route;
5842 if (seg)
5843 attr->u.num = seg->direction;
5844 else
5845 return 0;
5846 return 1;
5847 case attr_route:
5848 mr->attr_next = attr_length;
5849 attr->u.route = mr->mpriv->route;
5850 return 1;
5851 case attr_length:
5852 mr->attr_next = attr_time;
5853 if (seg)
5854 attr->u.num = seg->data->len;
5855 else
5856 return 0;
5857 return 1;
5858 case attr_time:
5859 mr->attr_next = attr_speed;
5860 if (seg)
5861 attr->u.num = route_time_seg(route->vehicleprofile, seg->data, NULL);
5862 else
5863 return 0;
5864 return 1;
5865 case attr_speed:
5866 mr->attr_next = attr_none;
5867 if (seg)
5868 attr->u.num = route_seg_speed_real(route->vehicleprofile, seg->data, NULL);
5869 else
5870 return 0;
5871 return 1;
5872 case attr_label:
5873 mr->attr_next = attr_none;
5874 return 0;
5875 default:
5876 mr->attr_next = attr_none;
5877 attr->type = attr_none;
5878 return 0;
5879 }
5880 return 0;
5881 }
5882
5883 static int rm_coord_get(void *priv_data, struct coord *c, int count)
5884 {
5885 //// dbg(0, "enter\n");
5886
5887 struct map_rect_priv *mr = priv_data;
5888 struct route_path_segment *seg = mr->seg;
5889 int i, rc = 0;
5890 struct route *r = mr->mpriv->route;
5891 enum projection pro = route_projection(r);
5892
5893 if (pro == projection_none)
5894 return 0;
5895
5896 if (mr->item.type == type_route_start || mr->item.type == type_route_start_reverse || mr->item.type == type_route_end)
5897 {
5898 if (!count || mr->last_coord)
5899 return 0;
5900
5901 mr->last_coord = 1;
5902
5903 if (mr->item.type == type_route_start || mr->item.type == type_route_start_reverse)
5904 {
5905 c[0] = r->pos->c;
5906 }
5907 else
5908 {
5909 c[0] = route_get_dst(r)->c;
5910 }
5911 return 1;
5912 }
5913
5914 if (!seg)
5915 return 0;
5916
5917 for (i = 0; i < count; i++)
5918 {
5919 if (mr->last_coord >= seg->ncoords)
5920 break;
5921
5922 if (i >= seg->ncoords)
5923 break;
5924
5925 if (pro != projection_mg)
5926 {
5927 transform_from_to(&seg->c[mr->last_coord++], pro, &c[i], projection_mg);
5928 }
5929 else
5930 {
5931 c[i] = seg->c[mr->last_coord++];
5932 }
5933
5934 rc++;
5935 }
5936 //dbg(1, "return %d\n", rc);
5937 return rc;
5938 }
5939
5940 static struct item_methods methods_route_item = { rm_coord_rewind, rm_coord_get, rm_attr_rewind, rm_attr_get, };
5941
5942 static void rp_attr_rewind(void *priv_data)
5943 {
5944 //// dbg(0, "enter\n");
5945
5946 struct map_rect_priv *mr = priv_data;
5947 mr->attr_next = attr_label;
5948 }
5949
5950 static int rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
5951 {
5952 //// dbg(0, "enter\n");
5953
5954 struct map_rect_priv *mr = priv_data;
5955 struct route_graph_point *p = mr->point;
5956 struct route_graph_segment *seg = mr->rseg;
5957 struct route *route = mr->mpriv->route;
5958
5959 attr->type = attr_type;
5960 switch (attr_type)
5961 {
5962 case attr_any: // works only with rg_points for now
5963 while (mr->attr_next != attr_none)
5964 {
5965 //dbg(0, "querying %s\n", attr_to_name(mr->attr_next));
5966 if (rp_attr_get(priv_data, mr->attr_next, attr))
5967 return 1;
5968 }
5969 return 0;
5970
5971 case attr_maxspeed:
5972 mr->attr_next = attr_label;
5973 if (mr->item.type != type_rg_segment)
5974 {
5975 return 0;
5976 }
5977
5978 if (seg && (seg->data.flags & NAVIT_AF_SPEED_LIMIT))
5979 {
5980 attr->type = attr_maxspeed;
5981 attr->u.num = RSD_MAXSPEED(&seg->data);
5982 return 1;
5983 }
5984 else
5985 {
5986 return 0;
5987 }
5988
5989 case attr_label:
5990 mr->attr_next = attr_street_item;
5991 if ((mr->item.type != type_rg_point) && (mr->item.type != type_rg_segment))
5992 {
5993 return 0;
5994 }
5995
5996 if (mr->item.type == type_rg_point)
5997 {
5998 attr->type = attr_label; // ZZZx
5999 if (mr->str)
6000 {
6001 g_free(mr->str);
6002 } // ZZZx
6003
6004 int lowest_cost = INT_MAX;
6005 if (p->start && p->start->seg_start_out_cost < lowest_cost)
6006 {
6007 lowest_cost = p->start->seg_start_out_cost;
6008 }
6009
6010 if (p->end && p->end->seg_end_out_cost < lowest_cost)
6011 {
6012 lowest_cost = p->end->seg_end_out_cost;
6013 }
6014
6015 if (lowest_cost < INT_MAX)
6016 {
6017 mr->str = g_strdup_printf("%d", lowest_cost);
6018 }
6019 else
6020 {
6021 mr->str = g_strdup("-");
6022 }
6023 attr->u.str = mr->str; // ZZZx
6024 }
6025 else if (mr->item.type == type_rg_segment)
6026 {
6027 attr->type = attr_label;
6028 if (mr->str)
6029 {
6030 g_free(mr->str);
6031 }
6032
6033 #if 0
6034 // z5z5
6035 if (seg)
6036 {
6037
6038 // FIXME
6039 // mr->str = g_strdup_printf("%dl, %dt, %ds sv=%d ev=%d", seg->data.len, route_time_seg(route->vehicleprofile, &seg->data, NULL), route_seg_speed(route->vehicleprofile, &seg->data, NULL), seg->start->value, seg->end->value);
6040 mr->str = g_strdup_printf("%dl, %dt, %ds", seg->data.len, route_time_seg(route->vehicleprofile, &seg->data, NULL), route_seg_speed(route->vehicleprofile, &seg->data, NULL));
6041 }
6042 else
6043 {
6044 mr->str = g_strdup("??");
6045 }
6046 #endif
6047
6048 mr->str = g_strdup("fix me - fix me");
6049
6050 attr->u.str = mr->str;
6051 }
6052
6053 return 1;
6054
6055 case attr_street_item:
6056 mr->attr_next = attr_flags;
6057 if (mr->item.type != type_rg_segment)
6058 return 0;
6059 if (seg && seg->data.item.map)
6060 attr->u.item = &seg->data.item;
6061 else
6062 return 0;
6063 return 1;
6064
6065 case attr_flags:
6066 mr->attr_next = attr_direction;
6067 if (mr->item.type != type_rg_segment)
6068 return 0;
6069 if (seg)
6070 {
6071 attr->u.num = seg->data.flags;
6072 }
6073 else
6074 {
6075 return 0;
6076 }
6077 return 1;
6078
6079 case attr_direction:
6080 mr->attr_next = attr_debug;
6081 // This only works if the map has been opened at a single point, and in that case indicates if the
6082 // segment returned last is connected to this point via its start (1) or its end (-1)
6083 if (!mr->coord_sel || (mr->item.type != type_rg_segment))
6084 return 0;
6085
6086 if (seg->start == mr->point)
6087 {
6088 attr->u.num = 1;
6089 }
6090 else if (seg->end == mr->point)
6091 {
6092 attr->u.num = -1;
6093 }
6094 else
6095 {
6096 return 0;
6097 }
6098
6099 return 1;
6100
6101 case attr_debug:
6102 mr->attr_next = attr_none;
6103
6104 if (mr->str)
6105 g_free(mr->str);
6106
6107 switch (mr->item.type)
6108 {
6109 case type_rg_point:
6110 {
6111 struct route_graph_segment *tmp;
6112 int start = 0;
6113 int end = 0;
6114 tmp = p->start;
6115 while (tmp)
6116 {
6117 start++;
6118 tmp = tmp->start_next;
6119 }
6120 tmp = p->end;
6121 while (tmp)
6122 {
6123 end++;
6124 tmp = tmp->end_next;
6125 }
6126 mr->str = g_strdup_printf("%d %d %p (0x%x,0x%x)", start, end, p, p->c.x, p->c.y);
6127 attr->u.str = mr->str;
6128 }
6129 return 1;
6130 case type_rg_segment:
6131 if (!seg)
6132 return 0;
6133 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);
6134 attr->u.str = mr->str;
6135 return 1;
6136 default:
6137 return 0;
6138 }
6139 default:
6140 mr->attr_next = attr_none;
6141 attr->type = attr_none;
6142 return 0;
6143 }
6144 }
6145
6146 /**
6147 * @brief Returns the coordinates of a route graph item
6148 *
6149 * @param priv_data The route graph item's private data
6150 * @param c Pointer where to store the coordinates
6151 * @param count How many coordinates to get at a max?
6152 * @return The number of coordinates retrieved
6153 */
6154 static int rp_coord_get(void *priv_data, struct coord *c, int count)
6155 {
6156 //// dbg(0, "enter\n");
6157
6158 struct map_rect_priv *mr = priv_data;
6159 struct route_graph_point *p = mr->point;
6160 struct route_graph_segment *seg = mr->rseg;
6161 int rc = 0, i, dir;
6162 struct route *r = mr->mpriv->route;
6163 enum projection pro = route_projection(r);
6164
6165 if (pro == projection_none)
6166 {
6167 return 0;
6168 }
6169
6170 for (i = 0; i < count; i++)
6171 {
6172 if (mr->item.type == type_rg_point)
6173 {
6174 if (mr->last_coord >= 1)
6175 break;
6176
6177 if (pro != projection_mg)
6178 transform_from_to(&p->c, pro, &c[i], projection_mg);
6179 else
6180 c[i] = p->c;
6181 }
6182 else
6183 {
6184 if (mr->last_coord >= 2)
6185 break;
6186
6187 dir = 0;
6188
6189 // FIXME !!
6190
6191 // if (seg->end->seg == seg)
6192 // dir = 1;
6193
6194 if (mr->last_coord)
6195 dir = 1 - dir;
6196
6197 // if (dir)
6198 // {
6199 // if (pro != projection_mg)
6200 // transform_from_to(&seg->end->c, pro, &c[i], projection_mg);
6201 // else
6202 // c[i] = seg->end->c;
6203 // }
6204 // else
6205 {
6206 if (pro != projection_mg)
6207 transform_from_to(&seg->start->c, pro, &c[i], projection_mg);
6208 else
6209 c[i] = seg->start->c;
6210 }
6211 }
6212 mr->last_coord++;
6213 rc++;
6214 }
6215 return rc;
6216 }
6217
6218 static struct item_methods methods_point_item = { rm_coord_rewind, rp_coord_get, rp_attr_rewind, rp_attr_get, };
6219
6220 static void rp_destroy(struct map_priv *priv)
6221 {
6222 __F_START__
6223
6224 g_free(priv);
6225
6226 __F_END__
6227 }
6228
6229 static void rm_destroy(struct map_priv *priv)
6230 {
6231 __F_START__
6232
6233 g_free(priv);
6234
6235 __F_END__
6236 }
6237
6238 static struct map_rect_priv *
6239 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
6240 {
6241 struct map_rect_priv * mr;
6242 //dbg(1, "enter\n");
6243
6244 #if 0
6245 if (! route_get_pos(priv->route))
6246 return NULL;
6247 if (! route_get_dst(priv->route))
6248 return NULL;
6249 #endif
6250
6251 #if 0
6252 if (! priv->route->path2)
6253 return NULL;
6254 #endif
6255
6256 mr=g_new0(struct map_rect_priv, 1);
6257 mr->mpriv = priv;
6258 mr->item.priv_data = mr;
6259 mr->item.type = type_none;
6260 mr->item.meth = &methods_route_item;
6261 if (priv->route->path2)
6262 {
6263 mr->path = priv->route->path2;
6264 mr->seg_next = mr->path->path;
6265 mr->path->in_use++;
6266 }
6267 else
6268 {
6269 mr->seg_next = NULL;
6270 }
6271
6272 return mr;
6273 }
6274
6275 /**
6276 * @brief Opens a new map rectangle on the route graph's map
6277 *
6278 * This function opens a new map rectangle on the route graph's map.
6279 * The "sel" parameter enables you to only search for a single route graph
6280 * point on this map (or exactly: open a map rectangle that only contains
6281 * this one point). To do this, pass here a single map selection, whose
6282 * c_rect has both coordinates set to the same point. Otherwise this parameter
6283 * has no effect.
6284 *
6285 * @param priv The route graph map's private data
6286 * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
6287 * @return A new map rect's private data
6288 */
6289 static struct map_rect_priv *
6290 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
6291 {
6292 struct map_rect_priv * mr;
6293
6294 if (!priv->route->graph)
6295 {
6296 return NULL;
6297 }
6298
6299 mr=g_new0(struct map_rect_priv, 1);
6300 mr->mpriv = priv;
6301 mr->item.priv_data = mr;
6302 mr->item.type = type_rg_point;
6303 mr->item.meth = &methods_point_item;
6304
6305 if (sel)
6306 {
6307 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))
6308 {
6309 mr->coord_sel = g_malloc(sizeof(struct coord));
6310 // xxx
6311 *(mr->coord_sel) = sel->u.c_rect.lu;
6312 }
6313 }
6314
6315 return mr;
6316
6317 }
6318
6319 static void rm_rect_destroy(struct map_rect_priv *mr)
6320 {
6321
6322 if (mr->str)
6323 g_free(mr->str);
6324
6325 if (mr->coord_sel)
6326 {
6327 g_free(mr->coord_sel);
6328 }
6329
6330 if (mr->path)
6331 {
6332 mr->path->in_use--;
6333
6334 if (mr->path->update_required && (mr->path->in_use == 1))
6335 route_path_update_done(mr->mpriv->route, mr->path->update_required - 1);
6336
6337 else if (!mr->path->in_use)
6338 g_free(mr->path);
6339 }
6340
6341 g_free(mr);
6342
6343 }
6344
6345 static struct item *
6346 rp_get_item(struct map_rect_priv *mr)
6347 {
6348 //// dbg(0, "enter\n");
6349
6350 struct route *r = mr->mpriv->route;
6351 struct route_graph_point *p = mr->point;
6352 struct route_graph_segment *seg = mr->rseg;
6353
6354 if (mr->item.type == type_rg_point)
6355 {
6356 if (mr->coord_sel)
6357 {
6358 // We are supposed to return only the point at one specified coordinate...
6359 if (!p)
6360 {
6361 p = route_graph_get_point_last(r->graph, mr->coord_sel);
6362 if (!p)
6363 {
6364 mr->point = NULL; // This indicates that no point has been found
6365 }
6366 else
6367 {
6368 mr->it = rp_iterator_new(p);
6369 }
6370 }
6371 else
6372 {
6373 p = NULL;
6374 }
6375 }
6376 else
6377 {
6378 if (!p)
6379 {
6380 mr->hash_bucket = 0;
6381 p = r->graph->hash[0];
6382 }
6383 else
6384 {
6385 p = p->hash_next;
6386 }
6387
6388 while (!p)
6389 {
6390 mr->hash_bucket++;
6391 if (mr->hash_bucket >= HASH_SIZE)
6392 {
6393 break;
6394 }
6395 p = r->graph->hash[mr->hash_bucket];
6396 }
6397 }
6398
6399 if (p)
6400 {
6401 mr->point = p;
6402 mr->item.id_lo++;
6403 rm_coord_rewind(mr);
6404 rp_attr_rewind(mr);
6405
6406 return &mr->item;
6407 }
6408 else
6409 {
6410 mr->item.type = type_rg_segment;
6411 }
6412 }
6413
6414 if (mr->coord_sel)
6415 {
6416 if (!mr->point)
6417 { // This means that no point has been found
6418 return NULL;
6419 }
6420 seg = rp_iterator_next(&(mr->it));
6421 }
6422 else
6423 {
6424 if (!seg)
6425 {
6426 seg = r->graph->route_segments;
6427 }
6428 else
6429 {
6430 seg = seg->next;
6431 }
6432 }
6433
6434 if (seg)
6435 {
6436 mr->rseg = seg;
6437 mr->item.id_lo++;
6438 rm_coord_rewind(mr);
6439 rp_attr_rewind(mr);
6440
6441 return &mr->item;
6442 }
6443 return NULL;
6444
6445 __F_END__
6446 }
6447
6448 static struct item *
6449 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
6450 {
6451 struct item *ret = NULL;
6452
6453 while (id_lo-- > 0)
6454 ret = rp_get_item(mr);
6455
6456 return ret;
6457 }
6458
6459 static struct item *
6460 rm_get_item(struct map_rect_priv *mr)
6461 {
6462 struct route *route = mr->mpriv->route;
6463
6464 int is_waypoint = 0;
6465
6466 #if 1
6467 dbg(0, "NAVR:ROUTE:001.r0:%s ===================================\n", item_to_name(mr->item.type));
6468 if (mr->seg_next)
6469 {
6470 dbg(0, "NAVR:ROUTE:001.r1:%s ===================================\n", item_to_name(mr->seg_next->data->item.type));
6471 }
6472 if ((mr->seg)&&(mr->seg->next))
6473 {
6474 dbg(0, "NAVR:ROUTE:001.r2:%s ===================================\n", item_to_name(mr->seg->next->data->item.type));
6475 }
6476 if (mr->seg)
6477 // mr->seg->next
6478 // if (mr->seg_next)
6479 {
6480 if (mr->seg->data)
6481 // if (mr->seg_next->data)
6482 {
6483 dbg(0, "NAVR:ROUTE:001:%s ===================================\n", item_to_name(mr->seg->data->item.type));
6484 // dbg(0, "NAVR:ROUTE:001:%s ===================================\n", item_to_name(mr->seg_next->data->item.type));
6485 if (mr->seg->data->item.type == type_street_route_waypoint)
6486 // if (mr->seg_next->data->item.type == type_street_route_waypoint)
6487 {
6488 item_dump_coords(&mr->item, route_get_map(route));
6489 is_waypoint = 1;
6490 }
6491 }
6492 }
6493 // item_dump_coords(&mr->item, route_get_map(route));
6494
6495 #endif
6496
6497 switch (mr->item.type)
6498 {
6499 case type_none:
6500
6501 if (route->pos)
6502 {
6503 dbg(0, "NAVR:ROUTE:001ppp:route->pos->street_direction=%d route->pos->dir=%d\n", route->pos->street_direction, route->pos->dir);
6504 }
6505
6506 if (route->pos && route->pos->street_direction && route->pos->street_direction != route->pos->dir)
6507 {
6508 mr->item.type = type_route_start_reverse;
6509 }
6510 else
6511 {
6512 mr->item.type = type_route_start;
6513 }
6514
6515 if (route->pos)
6516 {
6517 break;
6518 }
6519
6520 default:
6521 mr->item.type = type_street_route;
6522 mr->seg = mr->seg_next;
6523
6524 #if 0
6525 if (mr->seg)
6526 {
6527 if (mr->seg->data)
6528 {
6529 dbg(0, "NAVR:ROUTE:001:%s ===================================\n", item_to_name(mr->seg->data->item.type));
6530 if (mr->seg->data->item.type == type_street_route_waypoint)
6531 {
6532 is_waypoint = 1;
6533 }
6534 }
6535 }
6536 #endif
6537
6538 if (!mr->seg && mr->path && mr->path->next)
6539 {
6540 // dbg(0, "NAVR:ROUTE:002:WAYPOINT/DESTINATION---------------------------------------------------------");
6541
6542 struct route_path *p = NULL;
6543 mr->path->in_use--;
6544
6545 if (!mr->path->in_use)
6546 {
6547 p = mr->path;
6548 // dbg(0, "NAVR:ROUTE:003:+++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
6549 }
6550
6551 mr->path = mr->path->next;
6552 mr->path->in_use++;
6553 mr->seg = mr->path->path;
6554
6555 if (p)
6556 {
6557 g_free(p);
6558 }
6559
6560 // set waypoint type
6561 // ?? seems to not be the correct spot for waypoint ?? // mr->item.type = type_street_route_waypoint;
6562 }
6563
6564 if (mr->seg)
6565 {
6566 mr->seg_next = mr->seg->next;
6567 break;
6568 }
6569
6570 mr->item.type = type_route_end;
6571 // dbg(0,"* set route_end *\n");
6572
6573 if (mr->mpriv->route->destinations)
6574 {
6575 break;
6576 }
6577
6578 case type_route_end:
6579 return NULL;
6580 }
6581
6582 mr->last_coord = 0;
6583 mr->item.id_lo++;
6584 rm_attr_rewind(mr);
6585
6586
6587 if (is_waypoint == 1)
6588 {
6589 mr->item.type = type_street_route_waypoint;
6590 }
6591
6592 return &mr->item;
6593 }
6594
6595 static struct item *
6596 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
6597 {
6598 //// dbg(0, "enter\n");
6599
6600 struct item *ret = NULL;
6601
6602 while (id_lo-- > 0)
6603 {
6604 ret = rm_get_item(mr);
6605 }
6606
6607 return ret;
6608 }
6609
6610 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, };
6611
6612 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, };
6613
6614 static struct map_priv *
6615 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
6616 {
6617 __F_START__
6618
6619 struct map_priv *ret;
6620 struct attr *route_attr;
6621
6622 route_attr = attr_search(attrs, NULL, attr_route);
6623
6624 if (!route_attr)
6625 {
6626 return2 NULL;
6627 }
6628
6629 ret=g_new0(struct map_priv, 1);
6630
6631 if (graph)
6632 *meth = route_graph_meth;
6633 else
6634 *meth = route_meth;
6635
6636 ret->route = route_attr->u.route;
6637
6638 return2 ret;
6639
6640 __F_END__
6641 }
6642
6643 struct map_priv *
6644 route_map_new(struct map_methods *meth, struct attr **attrs, struct callback_list *cbl)
6645 {
6646 __F_START__
6647
6648 return2 route_map_new_helper(meth, attrs, 0);
6649
6650 __F_END__
6651 }
6652
6653 struct map_priv *
6654 route_graph_map_new(struct map_methods *meth, struct attr **attrs, struct callback_list *cbl)
6655 {
6656 __F_START__
6657
6658 return2 route_map_new_helper(meth, attrs, 1);
6659
6660 __F_END__
6661 }
6662
6663 static struct map *
6664 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
6665 {
6666 struct attr *attrs[5];
6667 struct attr a_type, navigation, data, a_description;
6668 a_type.type = attr_type;
6669 a_type.u.str = type;
6670 navigation.type = attr_route;
6671 navigation.u.route = this_;
6672 data.type = attr_data;
6673 data.u.str = "";
6674 a_description.type = attr_description;
6675 a_description.u.str = description;
6676
6677 attrs[0] = &a_type;
6678 attrs[1] = &navigation;
6679 attrs[2] = &data;
6680 attrs[3] = &a_description;
6681 attrs[4] = NULL;
6682
6683 if (!*map)
6684 {
6685 *map = map_new(NULL, attrs);
6686 map_ref(*map);
6687 }
6688
6689 return *map;
6690 }
6691
6692 /**
6693 * @brief Returns a new map containing the route path
6694 *
6695 * This function returns a new map containing the route path.
6696 *
6697 * @important Do not map_destroy() this!
6698 *
6699 * @param this_ The route to get the map of
6700 * @return A new map containing the route path
6701 */
6702 struct map *
6703 route_get_map(struct route *this_)
6704 {
6705 return route_get_map_helper(this_, &this_->map, "route", "Route");
6706 }
6707
6708 /**
6709 * @brief Returns a new map containing the route graph
6710 *
6711 * This function returns a new map containing the route graph.
6712 *
6713 * @important Do not map_destroy() this!
6714 *
6715 * @param this_ The route to get the map of
6716 * @return A new map containing the route graph
6717 */
6718 struct map *
6719 route_get_graph_map(struct route *this_)
6720 {
6721 return route_get_map_helper(this_, &this_->graph_map, "route_graph", "Route Graph");
6722 }
6723
6724 void route_set_projection(struct route *this_, enum projection pro)
6725 {
6726 }
6727
6728 int route_set_attr(struct route *this_, struct attr *attr)
6729 {
6730 __F_START__
6731
6732 int attr_updated = 0;
6733 switch (attr->type)
6734 {
6735 case attr_route_status:
6736 // update global route_status notifier
6737
6738 #ifdef NAVIT_ROUTING_DEBUG_PRINT
6739 dbg(0, "RS:002P:route_status=%s\n", route_status_to_name(route_status_previous));
6740 dbg(0, "RS:002C:route_status=%s\n", route_status_to_name(this_->route_status));
6741 dbg(0, "RS:002N:route_status=%s\n", route_status_to_name(attr->u.num));
6742 #endif
6743 //dbg(0,"previous=%d\n", route_status_previous);
6744 //dbg(0,"this_->route_status=%d attr->u.num=%d\n", this_->route_status, attr->u.num);
6745
6746 if (this_->route_status != attr->u.num)
6747 {
6748 if (attr->u.num == 5)
6749 {
6750 }
6751 else
6752 {
6753 if (route_status_previous != attr->u.num)
6754 {
6755 //dbg(0,"update\n");
6756 this_->route_status_was_updated = 1;
6757 }
6758 route_status_previous = attr->u.num;
6759 }
6760 }
6761
6762 attr_updated = (this_->route_status != attr->u.num);
6763 this_->route_status = attr->u.num;
6764 break;
6765
6766 case attr_destination:
6767 route_set_destination(this_, attr->u.pcoord, 1);
6768 return2 1;
6769
6770 case attr_vehicle:
6771 attr_updated = (this_->v != attr->u.vehicle);
6772 this_->v = attr->u.vehicle;
6773 if (attr_updated)
6774 {
6775 struct attr g;
6776 struct pcoord pc;
6777 struct coord c;
6778 if (vehicle_get_attr(this_->v, attr_position_coord_geo, &g, NULL))
6779 {
6780 pc.pro = projection_mg;
6781 transform_from_geo(projection_mg, g.u.coord_geo, &c);
6782 pc.x = c.x;
6783 pc.y = c.y;
6784 #ifdef NAVIT_ROUTING_DEBUG_PRINT
6785 dbg(0, "ROUTExxPOSxx:route_set_attr:YYYYYYYY: %d %d\n", c.x, c.y);
6786 #endif
6787 route_set_position(this_, &pc);
6788 }
6789 }
6790 break;
6791
6792 default:
6793 // dbg(0, "unsupported attribute: %s\n", attr_to_name(attr->type));
6794 return2 0;
6795 }
6796
6797 if (attr_updated)
6798 {
6799 #ifdef NAVIT_ROUTING_DEBUG_PRINT
6800 dbg(0, "ROUTExxPOSxx:route_set_attr:attr->type=%s\n", attr_to_name(attr->type));
6801 #endif
6802 if (attr->type == attr_route_status)
6803 {
6804 #ifdef NAVIT_ROUTING_DEBUG_PRINT
6805 dbg(0, "RS:004:route_status=%s\n", route_status_to_name(attr->u.num));
6806 #endif
6807
6808 dbg(0, "NAVR:ROUTE:007r:route_status=%s\n", route_status_to_name(attr->u.num));
6809
6810 // calls: "navit_redraw_route" and "navigation_update"
6811 callback_list_call_attr_2(this_->cbl2, attr->type, this_, attr);
6812 }
6813 }
6814
6815 return2 1;
6816
6817 __F_END__
6818 }
6819
6820 int route_add_attr(struct route *this_, struct attr *attr)
6821 {
6822 __F_START__
6823
6824 switch (attr->type)
6825 {
6826 case attr_callback:
6827 callback_list_add(this_->cbl2, attr->u.callback);
6828 return2 1;
6829 default:
6830 return2 0;
6831 }
6832
6833 __F_END__
6834 }
6835
6836 int route_remove_attr(struct route *this_, struct attr *attr)
6837 {
6838 __F_START__
6839
6840 switch (attr->type)
6841 {
6842 case attr_callback:
6843 callback_list_remove(this_->cbl2, attr->u.callback);
6844 return2 1;
6845 case attr_vehicle:
6846 this_->v = NULL;
6847 return2 1;
6848 default:
6849 return2 0;
6850 }
6851
6852 __F_END__
6853 }
6854
6855 int route_get_attr(struct route *this_, enum attr_type type, struct attr *attr, struct attr_iter *iter)
6856 {
6857 __F_START__
6858
6859 int ret = 1;
6860 switch (type)
6861 {
6862 case attr_map:
6863 attr->u.map = route_get_map(this_);
6864 ret = (attr->u.map != NULL);
6865 break;
6866 case attr_destination:
6867 if (this_->destinations)
6868 {
6869 struct route_info *dst;
6870 if (iter)
6871 {
6872 if (iter->u.list)
6873 {
6874 iter->u.list = g_list_next(iter->u.list);
6875 }
6876 else
6877 {
6878 iter->u.list = this_->destinations;
6879 }
6880 if (!iter->u.list)
6881 {
6882 return2 0;
6883 }
6884 dst = (struct route_info*) iter->u.list->data;
6885 }
6886 else
6887 { //No iter handling
6888 dst = route_get_dst(this_);
6889 }
6890 attr->u.pcoord = &this_->pc;
6891 this_->pc.pro = projection_mg; /* fixme */
6892 this_->pc.x = dst->c.x;
6893 this_->pc.y = dst->c.y;
6894 }
6895 else
6896 ret = 0;
6897 break;
6898 case attr_vehicle:
6899 attr->u.vehicle = this_->v;
6900 ret = (this_->v != NULL);
6901 //dbg(0,"get vehicle %p\n",this_->v);
6902 break;
6903 case attr_vehicleprofile:
6904 attr->u.vehicleprofile = this_->vehicleprofile;
6905 ret = (this_->vehicleprofile != NULL);
6906 break;
6907 case attr_route_status:
6908 attr->u.num = this_->route_status;
6909 break;
6910 case attr_destination_time:
6911 if (this_->path2 && (this_->route_status == route_status_path_done_new || this_->route_status == route_status_path_done_incremental))
6912 {
6913
6914 attr->u.num = this_->path2->path_time;
6915 //dbg(1, "path_time %d\n", attr->u.num);
6916 }
6917 else
6918 ret = 0;
6919
6920 break;
6921 case attr_destination_length:
6922 if (this_->path2 && (this_->route_status == route_status_path_done_new || this_->route_status == route_status_path_done_incremental))
6923 attr->u.num = this_->path2->path_len;
6924 else
6925 ret = 0;
6926
6927 break;
6928 default:
6929 return2 0;
6930 }
6931 attr->type = type;
6932
6933 return2 ret;
6934
6935 __F_END__
6936 }
6937
6938 struct attr_iter *
6939 route_attr_iter_new(void)
6940 {
6941 //// dbg(0, "enter\n");
6942
6943 return g_new0(struct attr_iter, 1);
6944 }
6945
6946 void route_attr_iter_destroy(struct attr_iter *iter)
6947 {
6948 //// dbg(0, "enter\n");
6949
6950 g_free(iter);
6951 }
6952
6953 void route_init(void)
6954 {
6955 __F_START__
6956
6957 #ifdef PLUGSSS
6958 plugin_register_map_type("route", route_map_new);
6959 plugin_register_map_type("route_graph", route_graph_map_new);
6960 #endif
6961
6962 __F_END__
6963 }
6964
6965 void route_destroy(struct route *this_)
6966 {
6967 __F_START__
6968
6969 route_path_destroy(this_->path2, 1);
6970 route_graph_destroy(this_->graph);
6971 route_clear_destinations(this_);
6972 route_info_free(this_->pos);
6973 map_destroy(this_->map);
6974 map_destroy(this_->graph_map);
6975 g_free(this_);
6976
6977 __F_END__
6978 }
6979

   
Visit the ZANavi Wiki