navit/navit/maptool/boundaries.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include "maptool.h"
   4
   5 struct boundary {
   6         struct item_bin *ib;
   7         GList *segments,*sorted_segments;
   8         GList *children;
   9         struct rect r;
  10 };
  11
  12 struct boundary_member {
  13         long long wayid;
  14         enum geom_poly_segment_type role;
  15         struct boundary *boundary;
  16 };
  17
  18 static guint
  19 boundary_member_hash(gconstpointer key)
  20 {
  21         const struct boundary_member *memb=key;
  22         return (memb->wayid >> 32)^(memb->wayid & 0xffffffff);
  23 }
  24
  25 static gboolean
  26 boundary_member_equal(gconstpointer a, gconstpointer b)
  27 {
  28         const struct boundary_member *memba=a;
  29         const struct boundary_member *membb=b;
  30         return (memba->wayid == membb->wayid);
  31 }
  32
  33 GHashTable *member_hash;
  34
  35 static char *
  36 osm_tag_name(struct item_bin *ib)
  37 {
  38         char *tag=NULL;
  39         while ((tag=item_bin_get_attr(ib, attr_osm_tag, tag))) {
  40                 if (!strncmp(tag,"name=",5))
  41                         return tag+5;
  42         }
  43         return NULL;
  44 }
  45
  46 static GList *
  47 build_boundaries(FILE *boundaries)
  48 {
  49         struct item_bin *ib;
  50         GList *boundaries_list=NULL;
  51
  52         while ((ib=read_item(boundaries))) {
  53                 char *member=NULL;
  54                 struct boundary *boundary=g_new0(struct boundary, 1);
  55                 while ((member=item_bin_get_attr(ib, attr_osm_member, member))) {
  56                         long long wayid;
  57                         int read=0;
  58                         if (sscanf(member,"2:%Ld:%n",&wayid,&read) >= 1) {
  59                                 struct boundary_member *memb=g_new(struct boundary_member, 1);
  60                                 char *role=member+read;
  61                                 memb->wayid=wayid;
  62                                 memb->boundary=boundary;
  63                                 if (!strcmp(role,"outer"))
  64                                         memb->role=geom_poly_segment_type_way_outer;
  65                                 else if (!strcmp(role,"inner"))
  66                                         memb->role=geom_poly_segment_type_way_inner;
  67                                 else if (!strcmp(role,""))
  68                                         memb->role=geom_poly_segment_type_way_unknown;
  69                                 else {
  70                                         printf("Unknown role %s\n",role);
  71                                         memb->role=geom_poly_segment_type_none;
  72                                 }
  73                                 g_hash_table_insert(member_hash, memb, g_list_append(g_hash_table_lookup(member_hash, memb), memb));
  74
  75                         }
  76                 }
  77                 boundary->ib=item_bin_dup(ib);
  78                 boundaries_list=g_list_append(boundaries_list, boundary);
  79         }
  80         return boundaries_list;
  81 }
  82
  83 static void
  84 find_matches(GList *l, struct coord *c)
  85 {
  86         while (l) {
  87                 struct boundary *boundary=l->data;
  88                 if (bbox_contains_coord(&boundary->r, c)) {
  89                         struct item_bin *ib=boundary->ib;
  90                         if (geom_poly_segments_point_inside(boundary->sorted_segments,c))
  91                                 printf("%s,",osm_tag_name(ib));
  92                         find_matches(boundary->children, c);
  93                 }
  94                 l=g_list_next(l);
  95         }
  96 }
  97
  98 static void
  99 test(GList *boundaries_list)
 100 {
 101         struct item_bin *ib;
 102         FILE *f=fopen("country_276.bin.unsorted","r");
 103         printf("start\n");
 104         while (ib=read_item(f)) {
 105                 struct coord *c=(struct coord *)(ib+1);
 106                 char *name=item_bin_get_attr(ib, attr_town_name, NULL);
 107                 printf("%s:",name);
 108                 find_matches(boundaries_list, c);
 109                 printf("\n");
 110         }
 111         fclose(f);
 112         printf("end\n");
 113 }
 114
 115 static void
 116 dump_hierarchy(GList *l, char *prefix)
 117 {
 118         char *newprefix=g_alloca(sizeof(char)*(strlen(prefix)+2));
 119         strcpy(newprefix, prefix);
 120         strcat(newprefix," ");
 121         while (l) {
 122                 struct boundary *boundary=l->data;
 123                 printf("%s:%s\n",prefix,osm_tag_name(boundary->ib));
 124                 dump_hierarchy(boundary->children, newprefix);
 125                 l=g_list_next(l);
 126         }
 127 }
 128
 129 static gint
 130 boundary_bbox_compare(gconstpointer a, gconstpointer b)
 131 {
 132         const struct boundary *boundarya=a;
 133         const struct boundary *boundaryb=b;
 134         long long areaa=bbox_area(&boundarya->r);
 135         long long areab=bbox_area(&boundaryb->r);
 136         if (areaa > areab)
 137                 return 1;
 138         if (areaa < areab)
 139                 return -1;
 140         return 0;
 141 }
 142
 143 int
 144 process_boundaries(FILE *boundaries, FILE *ways)
 145 {
 146         struct item_bin *ib;
 147         GList *boundaries_list,*l,*sl,*l2,*ln;
 148
 149         member_hash=g_hash_table_new_full(boundary_member_hash, boundary_member_equal, NULL, NULL);
 150         boundaries_list=build_boundaries(boundaries);
 151         while (ib=read_item(ways)) {
 152                 long long *wayid=item_bin_get_attr(ib, attr_osm_wayid, NULL);
 153                 if (wayid) {
 154                         GList *l=g_hash_table_lookup(member_hash, wayid);
 155                         while (l) {
 156                                 struct boundary_member *memb=l->data;
 157                                 memb->boundary->segments=g_list_prepend(memb->boundary->segments,item_bin_to_poly_segment(ib, memb->role));
 158
 159                                 l=g_list_next(l);
 160                         }
 161                 }
 162         }
 163         l=boundaries_list;
 164         while (l) {
 165                 struct boundary *boundary=l->data;
 166                 int first=1;
 167                 boundary->sorted_segments=geom_poly_segments_sort(boundary->segments, geom_poly_segment_type_way_right_side);
 168                 sl=boundary->sorted_segments;
 169                 while (sl) {
 170                         struct geom_poly_segment *gs=sl->data;
 171                         struct coord *c=gs->first;
 172                         while (c <= gs->last) {
 173                                 if (first) {
 174                                         boundary->r.l=*c;
 175                                         boundary->r.h=*c;
 176                                         first=0;
 177                                 } else
 178                                         bbox_extend(c, &boundary->r);
 179                                 c++;
 180                         }
 181                         sl=g_list_next(sl);
 182                 }
 183                 l=g_list_next(l);
 184
 185         }
 186         printf("hierarchy\n");
 187         boundaries_list=g_list_sort(boundaries_list, boundary_bbox_compare);
 188         l=boundaries_list;
 189         while (l) {
 190                 struct boundary *boundary=l->data;
 191                 ln=l2=g_list_next(l);
 192                 while (l2) {
 193                         struct boundary *boundary2=l2->data;
 194                         if (bbox_contains_bbox(&boundary2->r, &boundary->r)) {
 195                                 boundaries_list=g_list_remove(boundaries_list, boundary);
 196                                 boundary2->children=g_list_append(boundary2->children, boundary);
 197                                 printf("found\n");
 198                                 break;
 199                         }
 200                         l2=g_list_next(l2);
 201                 }
 202                 l=ln;
 203         }
 204         printf("hierarchy done\n");
 205         dump_hierarchy(boundaries_list,"");
 206         printf("test\n");
 207         test(boundaries_list);
 208         return 1;
 209 }