Fix/refactor polygon reassembly.

We're getting close. Finally processed map of Oberbayern, Germany
without any issues. Renders nicely on Qt5. Nedds still some hacks in
maptool as I did not understan everything properly. Parts of maptool are
rather hacky, aren't they?

2 files changed, 129 insertions, 123 deletions

diff --git a/navit/graphics.c b/navit/graphics.c
index 5b4a63616..b787d28d0 100644
--- a/navit/graphics.c
+++ b/navit/graphics.c
@@ -1426,7 +1426,7 @@ static void display_add(struct hash_entry *entry, struct item *item, int count,
     holes_length = sizeof(struct displayitem_poly_holes) + hole_count * sizeof(int) + hole_count * sizeof(
                        struct coord *) + hole_total_coords * sizeof(struct coord);
     if(hole_count > 0)
-        dbg(lvl_error,"got %d holes with %d coords total", hole_count, hole_total_coords);
+        dbg(lvl_debug,"got %d holes with %d coords total", hole_count, hole_total_coords);
     len += holes_length;
 
     p=g_malloc(len);
diff --git a/navit/maptool/osm.c b/navit/maptool/osm.c
index fc8f79851..6eab6a903 100644
--- a/navit/maptool/osm.c
+++ b/navit/maptool/osm.c
@@ -2662,7 +2662,6 @@ void process_house_number_interpolations(FILE *in, struct files_relation_process
     g_list_free(fp.allocations);
 }
 
-#define MEMBER_MAX 20
 struct multipolygon {
     osmid relid;
     struct item_bin * rel;
@@ -2676,7 +2675,8 @@ struct multipolygon {
 /**
  * @brief find the nect matching polygon segment
  * This can be used to find the next matching "line" to form a polygon.
- * @param coord find lines starting (or ending) at this coordinate
+ * @param part current line part
+ * @param part_used how this part was used
  * @param in_count number of lines passed in parts
  * @parts array of item_bin pointers giving the single parts
  * @parts used int array, one for each part, indicating wheather the part was already used. This
@@ -2684,8 +2684,16 @@ struct multipolygon {
  *        1: used forward 2: used reverse
  * @returns: index of matching part, -1 if none matches or all are consumed already.
  */
-static int  process_multipolygons_find_match(struct coord* coord, int in_count, struct item_bin **parts, int*used) {
+static int  process_multipolygons_find_match(struct item_bin* part,int part_used, int in_count, struct item_bin **parts,
+        int*used) {
     int i;
+    struct coord * coord;
+    /*get the actual ending coordinate of the sequence*/
+    coord=(struct coord *)(part +1);
+    if(part_used == 1) {
+        /* was a standard match. Need last coordinate */
+        coord+=(part->clen / 2) - 1;
+    }
     for(i=0; i < in_count; i ++) {
         if(!used[i]) {
             int have_match = 0;
@@ -2700,8 +2708,9 @@ static int  process_multipolygons_find_match(struct coord* coord, int in_count,
             try_first=(struct coord *)(parts[i] +1);
             try_last=(struct coord *)(parts[i] +1);
             try_last+=(parts[i]->clen / 2) - 1;
-            //fprintf(stderr, "try_first[%d] 0x%x,0x%x, try_last[%d] 0x%x,0x%x\n",i,try_first->x, try_first->y, i, try_last->x,
-            //        try_last->y);
+            fprintf(stderr, "0x%x,0x%x try_first[%d] 0x%x,0x%x try_last[%d] 0x%x,0x%x\n",coord->x, coord->y,i,try_first->x,
+                    try_first->y, i, try_last->x,
+                    try_last->y);
 
             if((coord->x == try_first->x) && (coord->y == try_first->y)) {
                 /* forward match */
@@ -2724,7 +2733,68 @@ static int  process_multipolygons_find_match(struct coord* coord, int in_count,
     return -1;
 }
 
-static int process_multipolygons_find_loop(int in_count, struct item_bin ** parts, int **scount, int *** sequences,
+static int is_loop (struct item_bin * start_part, int start_used, struct item_bin * end_part, int end_used) {
+    struct coord *first, *last;
+    /*get the actual starting coordinate of the sequence*/
+    first=(struct coord *)(start_part +1);
+    if(start_used != 1) {
+        /* was a reverse match. Need first coordinate */
+        first+=(start_part->clen / 2) - 1;
+    }
+
+    /*get the actual ending coordinate of the sequence*/
+    last=(struct coord *)(end_part +1);
+    if(end_used == 1) {
+        /* was a standard match. Need last coordinate */
+        last+=(end_part->clen / 2) - 1;
+    }
+    if((first->x == last->x) && (first->y == last->y))
+        return 1;
+    return 0;
+}
+
+static int process_multipolygons_find_loop(int in_count, struct item_bin ** parts, int* sequence, int * used) {
+    int a;
+    int sequence_count=0;
+    /* assume we already have the sequence array*/
+
+    /* to start find a unused part */
+    for(a=0; a < in_count; a ++) {
+        if(!used[a])
+            break;
+    }
+    if(!(a < in_count)) {
+        /* got no unused part. indicate no more loops possible */
+        return -1;
+    }
+    /* consume this part */
+    used[a] = 1;
+    sequence[sequence_count]=a;
+    sequence_count ++;
+
+    /* check all parts until no more matches, or a loop is found */
+    while(!is_loop (parts[sequence[0]], used[sequence[0]], parts[sequence[sequence_count-1]],
+                    used[sequence[sequence_count-1]])) {
+        int match;
+        /* get new mathching part */
+        match=process_multipolygons_find_match(parts[sequence[sequence_count-1]],used[sequence[sequence_count-1]], in_count,
+                                               parts, used);
+        if(match >= 0) {
+            sequence[sequence_count]=match;
+            sequence_count ++;
+        } else {
+            break;
+        }
+    }
+
+    /* check if this is a loop already */
+    if(is_loop (parts[sequence[0]], used[sequence[0]], parts[sequence[sequence_count-1]], used[sequence[sequence_count-1]]))
+        return sequence_count;
+    else
+        return 0;
+}
+
+static int process_multipolygons_find_loops(int in_count, struct item_bin ** parts, int **scount, int *** sequences,
         int **direction) {
     int done=0;
     int loop_count=0;
@@ -2738,111 +2808,26 @@ static int process_multipolygons_find_loop(int in_count, struct item_bin ** part
     *direction = NULL;
     /* allocate the usage and direction array.*/
     used=g_malloc0(in_count * sizeof(int));
-#if 0
-    while (! done) {
-        int a;
-        /* search for a new loop */
-        /* find first unused part to begin */
-        for(a=0; a < in_count; a ++) {
-            if(!used[a])
-                break;
-        }
-        if(!(a < in_count)) {
-            /* got no unused part */
-            done=1;
-        } else {
-            char * sequence;
-            int part_count = 0;
-            int done_loop = 0;
-            /* start a new sequence */
-            sequence=g_malloc0(in_count * sizeof(int));
-            /* consume the first item */
-            used[a] = 1;
-            /* add to sequence */
-            sequence[part_count]=a;
-            part_count ++;
-            while ((part_count < in_count) || (done_loop)) {
-            }
-        }
-    }
-#else
-    while(!done) {
-        int a;
-        int done_loop=0;
-        int have_loop=0;
-        int part_count=0;
-        int *sequence;
-        /* find first unused part to begin */
-        for(a=0; a < in_count; a ++) {
-            if(!used[a])
-                break;
-        }
-        /* chech if actually one was found */
-        if(!(a < in_count)) {
+    do {
+        int sequence_count;
+        int * sequence = g_malloc0(in_count * sizeof(int));
+        sequence_count = process_multipolygons_find_loop(in_count, parts, sequence,  used);
+        if(sequence_count < 0) {
             done = 1;
-        }
-        if(! done) {
-            sequence=g_malloc0(in_count * sizeof(int));
-            /* consume this, and start sequence */
-            used[a] = 1; /** always start keeping order */
-            sequence[part_count] = a;
-            /* will increase part_count later */
-        }
-
-        while((!have_loop) && (!done_loop) && (!done)) {
-            struct coord *first, *last;
-            /*get the actual starting coordinate of the sequence*/
-            first=(struct coord *)(parts[sequence[0]] +1);
-            /*get the actual ending coordinate of the sequence*/
-            last=(struct coord *)(parts[sequence[part_count]] +1);
-            if(used[sequence[part_count]] == 1) {
-                /* was a standard match. Need last coordinate */
-                last+=((parts[sequence[part_count]]->clen) / 2) - 1;
-            }
-            //fprintf(stderr, "first 0x%x,0x%x, last[%d] 0x%x,0x%x\n",first->x, first->y, sequence[part_count], last->x, last->y);
-
-            /* check if this is a loop already */
-            if((first->x == last->x) && (first->y == last->y))
-                have_loop=1;
-            if((!have_loop) && (part_count + 1  < in_count)) {
-                /* No loop yet, try to find the next matching part */
-                sequence[part_count +1] = process_multipolygons_find_match(last, in_count, parts, used);
-                /*process_multipolygon_find_match coped for "used" already*/
-                if(sequence[part_count +1] >= 0) {
-                    /*  matching part found */
-                    part_count ++;
-                    /*next iteration will check for loop*/
-                } else {
-                    done_loop=1;
-                }
-            } else
-                done=1;
-
-        }
-        if(have_loop) {
-            /* add the first entry to count */
-            part_count ++;
-            /* copy over the found loop sequence*/
-            /* increase memory for count array */
+        } else if(sequence_count == 0) {
+            fprintf(stderr,"skipping nonclosed sequence\n");
+            /* skip empty sequence */
+            g_free(sequence);
+        } else {
+            /* increase space for sequences */
             (*scount)=(int*) g_realloc((*scount), (loop_count +1) * sizeof(int));
-            /* increase memory for sequences array */
             (*sequences)=(int**) g_realloc((*sequences), (loop_count +1) * sizeof(int*));
-            /* link the sequence */
-            (*scount)[loop_count]=part_count;
-            (*sequences)[loop_count]=sequence;
-            /* count loop */
+            /* hook it in */
+            (*scount)[loop_count] = sequence_count;
+            (*sequences)[loop_count] = sequence;
             loop_count ++;
-            /* do not delete sequence, as we added it to *sequences */
-        } else if(!done) {
-            int i;
-            fprintf(stderr,"Throw away sequence which is no loop :");
-            for(i=0; i < part_count; i ++)
-                fprintf(stderr, "%d ", sequence[i]);
-            fprintf(stderr, "\n");
-            g_free(sequence);
         }
-    }
-#endif
+    } while (!done);
     fprintf(stderr,"found %d loops\n", loop_count);
     *direction = used;
     return loop_count;
@@ -2861,10 +2846,10 @@ static int process_multipolygons_loop_dump(struct item_bin** bin, int scount, in
         struct coord * c;
         c= (struct coord *) (bin[sequence[a]] + 1);
         pcount= bin[sequence[a]]->clen / 2;
-        /* cut the duplicate on all than the first one */
+
+        /* remove the duplicate point if not the first one */
         if(a!=0)
             pcount --;
-
         if((buffer != NULL) && (direction !=NULL)) {
             if(direction[a] == 1) {
                 memcpy(&(buffer[points]), c, pcount * sizeof(struct coord));
@@ -2872,7 +2857,7 @@ static int process_multipolygons_loop_dump(struct item_bin** bin, int scount, in
                 int b;
                 struct coord * target = &(buffer[points]);
                 for (b=0; b < pcount; b ++) {
-                    target[b] = c[(bin[sequence[a]]->clen / 2) - pcount -1];
+                    target[b] = c[(bin[sequence[a]]->clen / 2) - b -1];
                 }
             }
         }
@@ -2911,7 +2896,6 @@ static void process_multipolygons_finish(GList *tr, FILE *out) {
         int a;
         int b;
         struct multipolygon *multipolygon=l->data;
-        struct rect bbox;
         int inner_loop_count=0;
         int *inner_scount=NULL;
         int *inner_direction=NULL;
@@ -2921,19 +2905,19 @@ static void process_multipolygons_finish(GList *tr, FILE *out) {
         int *outer_direction=NULL;
         int **outer_sequences=NULL;
         /* combine outer to full loops */
-        outer_loop_count = process_multipolygons_find_loop(multipolygon->outer_count,multipolygon->outer, &outer_scount,
+        outer_loop_count = process_multipolygons_find_loops(multipolygon->outer_count,multipolygon->outer, &outer_scount,
                            &outer_sequences, &outer_direction);
 
         /* combine inner to full loops */
-        inner_loop_count = process_multipolygons_find_loop(multipolygon->inner_count,multipolygon->inner, &inner_scount,
+        inner_loop_count = process_multipolygons_find_loops(multipolygon->inner_count,multipolygon->inner, &inner_scount,
                            &inner_sequences, &inner_direction);
 
         dump_sequence("outer",outer_loop_count, outer_scount, outer_sequences);
         dump_sequence("inner",inner_loop_count, inner_scount, inner_sequences);
 
-        /* calculate bounding box */
 
         for(b=0; b<outer_loop_count; b++) {
+            struct rect outer_bbox;
             /* write out */
             int order;
             char tilebuf[20]="";
@@ -2946,6 +2930,8 @@ static void process_multipolygons_finish(GList *tr, FILE *out) {
                 l = g_list_next(l);
                 continue;
             }
+            long long relid=item_bin_get_relationid(multipolygon->rel);
+            fprintf(stderr,"process %lld\n", relid);
             outer_length = process_multipolygons_loop_count(multipolygon->outer, outer_scount[b],
                            outer_sequences[b]) * sizeof(struct coord);
             outer_buffer = (struct coord *) g_malloc0(outer_length);
@@ -2956,27 +2942,37 @@ static void process_multipolygons_finish(GList *tr, FILE *out) {
             g_free(outer_buffer);
             item_bin_copy_attr(ib,multipolygon->rel,attr_osm_relationid);
             item_bin_copy_attr(ib,multipolygon->rel,attr_label);
+            /*calculate bbox*/
+            bbox((struct coord*)(ib +1), (ib->clen/2), &outer_bbox);
 
             for(a = 0; a < inner_loop_count; a ++) {
+                int d;
                 int hole_len;
                 char * buffer;
                 int used =0;
                 int inner_len =0;
+                int inside = 0;
+                struct coord *hole_coord;
                 hole_len = process_multipolygons_loop_count(multipolygon->inner, inner_scount[a], inner_sequences[a]);
                 inner_len = (hole_len * sizeof(struct coord));
                 inner_len+=4;
                 buffer=g_malloc0(inner_len);
                 memcpy(&(buffer[used]), &(hole_len), sizeof(int));
                 used += sizeof(int);
-                fprintf(stderr,"hole_len %d, used %d\n", hole_len, used);
+                hole_coord = (struct coord*) &(buffer[used]);
                 used += process_multipolygons_loop_dump(multipolygon->inner, inner_scount[a], inner_sequences[a], inner_direction,
                                                         (struct coord *)&(buffer[used])) * sizeof(struct coord);
-                fprintf(stderr,"hole_len %d, used %d\n", hole_len, used);
-                item_bin_add_attr_data(ib, attr_poly_hole, buffer, inner_len);
+                /* check if at least one point is inside the outer */
+                for(d=0; d < hole_len; d++)
+                    if(bbox_contains_coord(&outer_bbox,hole_coord))
+                        inside=1;
+
+                if(inside)
+                    item_bin_add_attr_data(ib, attr_poly_hole, buffer, inner_len);
                 g_free(buffer);
             }
 
-            order=tile(&bbox,"",tilebuf,sizeof(tilebuf)-1,overlap,NULL);
+            order=tile(&outer_bbox,"",tilebuf,sizeof(tilebuf)-1,overlap,NULL);
             if(order > multipolygon->order)
                 order=multipolygon->order;
 
@@ -3046,28 +3042,35 @@ static GList *process_multipolygons_setup(FILE *in, struct relations *relations)
     fseek(in, 0, SEEK_SET);
     relations_func=relations_func_new(process_multipolygons_member, NULL);
     while ((ib=read_item(in))) {
-        struct relation_member outer[MEMBER_MAX];
+        struct relation_member *outer=NULL;
         int outer_count=0;
-        struct relation_member inner[MEMBER_MAX];
+        struct relation_member *inner=NULL;;
         int inner_count=0;
         long long relid;
         int a;
         struct multipolygon *p_multipolygon;
         relid=item_bin_get_relationid(ib);
         min_count=0;
-        while((outer_count < MEMBER_MAX) && (search_relation_member(ib, "outer",&(outer[outer_count]),&min_count))) {
+        /* allocate a slot for inner and outer */
+        outer = g_malloc0(sizeof(struct relation_member));
+        inner = g_malloc0(sizeof(struct relation_member));
+        while(search_relation_member(ib, "outer",&(outer[outer_count]),&min_count)) {
             if(outer[outer_count].type != rel_member_way)
                 osm_warning("relation",relid,0,"multipolygon: wrong type for outer member ");
             outer_count ++;
+            /*realloc outer to make space for next */
+            outer = g_realloc(outer, sizeof(struct relation_member) * (outer_count +1));
         }
         min_count=0;
-        while((inner_count < MEMBER_MAX) && (search_relation_member(ib, "inner",&(inner[inner_count]),&min_count))) {
+        while(search_relation_member(ib, "inner",&(inner[inner_count]),&min_count)) {
             if(inner[inner_count].type != rel_member_way)
                 osm_warning("relation",relid,0,"multipolygon: wrong type for inner member ");
             inner_count ++;
+            /*realloc inner to make space for next */
+            inner = g_realloc(inner, sizeof(struct relation_member) * (inner_count +1));
         }
         fprintf(stderr,"Relid %lld: Got %d outer and %d inner\n", relid, outer_count, inner_count);
-        if(outer == 0) {
+        if(outer_count == 0) {
             osm_warning("relation",relid,0,"multipolygon: missing outer member ");
             continue;
         }
@@ -3082,6 +3085,9 @@ static GList *process_multipolygons_setup(FILE *in, struct relations *relations)
             relations_add_relation_member_entry(relations, relations_func, p_multipolygon, (gpointer) 1, inner[a].type,
                                                 inner[a].id);
         multipolygons=g_list_append(multipolygons, p_multipolygon);
+        /* clean up*/
+        g_free(inner);
+        g_free(outer);
     }
     return multipolygons;
 }