From 7a252833ae2add78fae06f52d90219adbf59057a Mon Sep 17 00:00:00 2001 From: tinloaf Date: Wed, 17 Dec 2008 14:59:26 +0000 Subject: [PATCH] Add:Core:Adding first roundabout detection git-svn-id: https://navit.svn.sourceforge.net/svnroot/navit/trunk@1820 ffa7fe5e-494d-0410-b361-a75ebd5db220 --- navit/navit/attr.h | 2 +- navit/navit/navigation.c | 78 ++++++++++++++++++++++++++++++++++++++-- navit/navit/route.c | 92 ++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 168 insertions(+), 4 deletions(-) diff --git a/navit/navit/attr.h b/navit/navit/attr.h index a29972f..d65cd4c 100644 --- a/navit/navit/attr.h +++ b/navit/navit/attr.h @@ -43,7 +43,7 @@ enum attr_type { #define AF_NOPASS (AF_ONEWAY|AF_ONEWAYREV) #define AF_ONEWAYMASK (AF_ONEWAY|AF_ONEWAYREV) #define AF_SEGMENTED (1<<2) - +#define AF_ROUNDABOUT (1<<3) struct attr { enum attr_type type; diff --git a/navit/navit/navigation.c b/navit/navit/navigation.c index ae577ea..3ce5bf2 100644 --- a/navit/navit/navigation.c +++ b/navit/navit/navigation.c @@ -168,6 +168,7 @@ struct navigation_itm { int dest_length; int told; int dest_count; + int flags; struct navigation_itm *next; struct navigation_itm *prev; struct navigation_way *ways; /**< Pointer to all ways one could drive from here */ @@ -480,6 +481,61 @@ navigation_itm_update(struct navigation_itm *itm, struct item *ritem) itm->time=time.u.num; } +/** + * @brief This check if an item is part of a roundabout + * + * @param itm The item to be checked + * @return True if the item is part of a roundabout + */ +static int +check_roundabout(struct navigation_itm *itm, struct map *graph_map) +{ + struct map_selection coord_sel; + struct map_rect *g_rect; // Contains a map rectangle from the route graph's map + struct item *i,*sitem; + struct attr sitem_attr,flags_attr; + + // These values cause the code in route.c to get us only the route graph point and connected segments + coord_sel.next = NULL; + coord_sel.u.c_rect.lu = itm->start; + coord_sel.u.c_rect.rl = itm->start; + // the selection's order is ignored + + g_rect = map_rect_new(graph_map, &coord_sel); + + i = map_rect_get_item(g_rect); + if (!i || i->type != type_rg_point) { // probably offroad? + return 0; + } + + while (1) { + i = map_rect_get_item(g_rect); + + if (!i) { + break; + } + + if (i->type != type_rg_segment) { + continue; + } + + if (!item_attr_get(i,attr_street_item,&sitem_attr)) { + continue; + } + + sitem = sitem_attr.u.item; + if (item_is_equal(itm->item,*sitem)) { + if (item_attr_get(i,attr_flags,&flags_attr) && (flags_attr.u.num & AF_ROUNDABOUT)) { + map_rect_destroy(g_rect); + return 1; + } + } + } + + map_rect_destroy(g_rect); + return 0; +} + static struct navigation_itm * navigation_itm_new(struct navigation *this_, struct item *ritem) { @@ -503,9 +559,6 @@ navigation_itm_new(struct navigation *this_, struct item *ritem) else ret->direction=0; - item_attr_get(ritem, attr_route, &route_attr); - graph_map = route_get_graph_map(route_attr.u.route); - sitem=street_item.u.item; ret->item=*sitem; item_hash_insert(this_->hash, sitem, ret); @@ -535,6 +588,13 @@ navigation_itm_new(struct navigation *this_, struct item *ritem) ret->start=c[0]; ret->end=c[i]; + + item_attr_get(ritem, attr_route, &route_attr); + graph_map = route_get_graph_map(route_attr.u.route); + if (check_roundabout(ret, graph_map)) { + ret->flags |= AF_ROUNDABOUT; + } + dbg(1,"i=%d start %d end %d '%s' '%s'\n", i, ret->angle_start, ret->angle_end, ret->name1, ret->name2); map_rect_destroy(mr); } else { @@ -718,6 +778,7 @@ check_multiple_streets(struct navigation_itm *new) } } + /** * @brief Check if the new item is entered "straight" * @@ -767,6 +828,17 @@ maneuver_required2(struct navigation_itm *old, struct navigation_itm *new, int * dbg(1,"enter %p %p %p\n",old, new, delta); *delta=angle_delta(old->angle_end, new->angle_start); + if ((old->flags & AF_ROUNDABOUT) && ! (new->flags & AF_ROUNDABOUT)) { + dbg(1, "maneuver_required: leaving roundabout: yes\n"); + return 1; + } else if (!(old->flags & AF_ROUNDABOUT) && (new->flags & AF_ROUNDABOUT)) { + dbg(1, "maneuver_required: entering roundabout: no\n"); + return 0; + } else if ((old->flags & AF_ROUNDABOUT) && (new->flags & AF_ROUNDABOUT)) { + dbg(1, "maneuver_required: staying in roundabout: no\n"); + return 0; + } + if (new->item.type == old->item.type || (new->item.type != type_ramp && old->item.type != type_ramp)) { if (is_same_street2(old, new)) { if (! entering_straight(new, abs(*delta))) { diff --git a/navit/navit/route.c b/navit/navit/route.c index fa6b9d5..64e92ba 100644 --- a/navit/navit/route.c +++ b/navit/navit/route.c @@ -293,6 +293,21 @@ static struct route_graph_segment } /** + * @brief Checks if the last segment returned from a route_graph_point_iterator comes from the end + * + * @param it The route graph point iterator to be checked + * @return 1 if the last segment returned comes from the end of the route graph point, 0 otherwise + */ +static int +rp_iterator_end(struct route_graph_point_iterator *it) { + if (it->end && (it->next != it->p->end)) { + return 1; + } else { + return 0; + } +} + +/** * @brief Destroys a route_path * * @param this The route_path to be destroyed @@ -343,6 +358,66 @@ route_new(struct attr *parent, struct attr **attrs) } /** + * @brief Checks if a segment is part of a roundabout + * + * This function checks if a segment is part of a roundabout. + * + * @param seg The segment to be checked + * @param level How deep to scan the route graph + * @param direction Set this to 1 if we're entering the segment through its end, to 0 otherwise + * @param origin Used internally, set to NULL + * @return 1 If a roundabout was detected, 0 otherwise + */ +static int +route_check_roundabout(struct route_graph_segment *seg, int level, int direction, struct route_graph_segment *origin) +{ + struct route_graph_point_iterator it; + struct route_graph_segment *cur; + + if (!level) { + return 0; + } + if (!direction && !(seg->flags & AF_ONEWAY)) { + return 0; + } + if (direction && !(seg->flags & AF_ONEWAYREV)) { + return 0; + } + + if (!origin) { + origin = seg; + } + + if (!direction) { + it = rp_iterator_new(seg->end); + } else { + it = rp_iterator_new(seg->start); + } + + cur = rp_iterator_next(&it); + while (cur) { + if (cur == seg) { + cur = rp_iterator_next(&it); + continue; + } + + if (cur == origin) { + seg->flags |= AF_ROUNDABOUT; + return 1; + } + + if (route_check_roundabout(cur, (level-1), rp_iterator_end(&it), origin)) { + seg->flags |= AF_ROUNDABOUT; + return 1; + } + + cur = rp_iterator_next(&it); + } + + return 0; +} + +/** * @brief Sets the mapset of the route passwd * * @param this The route to set the mapset for @@ -1065,6 +1140,13 @@ route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpa segment->c[i]=ca[ccnt-i-1]; } segment->ncoords = ccnt; + + /* We check if the route graph segment is part of a roundabout here, because this + * only matters for route graph segments which form parts of the route path */ + if (!(rgs->flags & AF_ROUNDABOUT)) { // We identified this roundabout earlier + route_check_roundabout(rgs, 5, (dir < 1), NULL); + } + segment->item=rgs->item; segment->offset = offset; linkold: @@ -1956,6 +2038,16 @@ rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr) else return 0; return 1; + case attr_flags: + if (mr->item.type != type_rg_segment) + return 0; + mr->attr_next = attr_none; + if (seg) { + attr->u.num = seg->flags; + } else { + return 0; + } + return 1; case attr_direction: // This only works if the map has been opened at a single point, and in that case indicates if the // segment returned last is connected to this point via its start (1) or its end (-1) -- 2.7.4