fix:core:add clipping to polygons with holes (#870) fixes (#869)

* fix:core:refactor polygon clipping

This commit extracts the polygon clipping into its own function to be
re used for polygon with holes clipping.

* fix:core:Clip polygons with holes prior drawing.

While this helps drawing for limited graphics like SDL or WindowsCE,
it will slightly slow down on graphics that do clipping themselves like
qt5. As this is done for polygons already, we do this for polygons with
holes as well.

1 files changed, 186 insertions, 43 deletions

diff --git a/navit/graphics.c b/navit/graphics.c
index 172315488..784ca5540 100644
--- a/navit/graphics.c
+++ b/navit/graphics.c
@@ -2137,66 +2137,209 @@ static void poly_intersection(struct point *p1, struct point *p2, struct point_r
 }
 
 /**
- * @brief Draw a plain polygon on the display
+ * @brief clip a polygon inside a rectangle
  *
- * @param gra The graphics instance on which to draw
- * @param gc The graphics context
- * @param[in] pin An array of points forming the polygon
- * @param count_in The number of elements inside @p pin
+ * This function clippes a given polygon inside a rectangle. It writes the result into provided buffer.
+ *
+ * @param[in] r rectangle to clip into
+ * @param[in] pin point array of input polygon
+ * @param[in] count_in number of points in pin
+ * @param[out] out preallocated buffer of at least count_in *8 +1 points size
+ * @param[out] count_out size of out number of points, number of points used in out at return
  */
-void graphics_draw_polygon_clipped(struct graphics *gra, struct graphics_gc *gc, struct point *pin, int count_in) {
-    struct point_rect r=gra->r;
-    struct point *pout,*p,*s,pi,*p1,*p2;
-    int limit=10000;
-    struct point *pa1=g_alloca(sizeof(struct point) * (count_in < limit ? count_in*8+1:0));
-    struct point *pa2=g_alloca(sizeof(struct point) * (count_in < limit ? count_in*8+1:0));
-    int count_out,edge=3;
-    int i;
-    if (count_in < limit) {
-        p1=pa1;
-        p2=pa2;
-    } else {
-        p1=g_new(struct point, count_in*8+1);
-        p2=g_new(struct point, count_in*8+1);
+static void graphics_clip_polygon(struct point_rect * r, struct point * in, int count_in, struct point *out,
+                                  int* count_out) {
+    /* set our self a limit for the in stack buffer. To not overflow stack */
+    const int limit=10000;
+    /* get a temp buffer to store points after one direction clipping.
+     * since we are clipping 4 directions, result is always in out at the end*/
+    struct point *temp=g_alloca(sizeof(struct point) * (count_in < limit ? count_in*8+1:0));
+    struct point *pout;
+    struct point *pin;
+    int edge;
+    int count;
+
+    /* sanity check */
+    if((r == NULL) || (in == NULL) || (out == NULL) || (count_out == NULL) || (*count_out < count_in*8+1)) {
+        return;
+    }
+
+    /* prepare buffers. We have two buffers that we flip over.
+     * 1. the output buffer
+     * 2. temp
+     */
+    if (count_in >= limit) {
+        /* too big. Allocate a buffer (slower) */
+        temp=g_new(struct point, count_in*8+1);
     }
+    /* use temp as first buffer. So we get the final result in out*/
+    pout = temp;
+    /* start with input polygon */
+    pin=in;
+    /* start with number of points of source polygon*/
+    count=count_in;
 
-    pout=p1;
+    /* clip all four directions of a rectangle */
     for (edge = 0 ; edge < 4 ; edge++) {
-        p=pin;
-        s=pin+count_in-1;
-        count_out=0;
-        for (i = 0 ; i < count_in ; i++) {
-            if (is_inside(p, &r, edge)) {
-                if (! is_inside(s, &r, edge)) {
-                    poly_intersection(s,p,&r,edge,&pi);
-                    pout[count_out++]=pi;
+        int i;
+        /* p is first element in current buffer */
+        struct point *p=pin;
+        /* s is lasst element in current buffer */
+        struct point *s=pin+count-1;
+        /* nothing written yet */
+        *count_out=0;
+
+        /* iterate all points in current buffer */
+        for (i = 0 ; i < count ; i++) {
+            if (is_inside(p, r, edge)) {
+                if (! is_inside(s, r, edge)) {
+                    struct point pi;
+                    /* current segment crosses border from outside to inside. Add crossing point with border first */
+                    poly_intersection(s,p,r,edge,&pi);
+                    pout[(*count_out)++]=pi;
                 }
-                pout[count_out++]=*p;
+                /* add point if inside */
+                pout[(*count_out)++]=*p;
             } else {
-                if (is_inside(s, &r, edge)) {
-                    poly_intersection(p,s,&r,edge,&pi);
-                    pout[count_out++]=pi;
+                if (is_inside(s, r, edge)) {
+                    struct point pi;
+                    /*current segment crosses border from inside to outside. Add crossing point with border */
+                    poly_intersection(p,s,r,edge,&pi);
+                    pout[(*count_out)++]=pi;
                 }
+                /* skip point if outside */
             }
+            /* move one coordinate forward */
             s=p;
             p++;
         }
-        count_in=count_out;
-        if (pin == p1) {
-            pin=p2;
-            pout=p1;
+        /* use result of last clipping for next */
+        count=*count_out;
+
+        /* switch buffer */
+        if(pout == temp) {
+            pout=out;
+            pin=temp;
         } else {
-            pin=p1;
-            pout=p2;
+            pin=out;
+            pout=temp;
         }
     }
-    graphics_draw_polygon(gra, gc, pin, count_in);
+
+    /* have clipped poly in out. And number of points now in *count_out */
+
+    /* if we had to allocate the buffer, we need to free it */
+    if (count_in >= limit) {
+        g_free(temp);
+    }
+    return;
+}
+
+/**
+ * @brief Draw a plain polygon on the display
+ *
+ * @param gra The graphics instance on which to draw
+ * @param gc The graphics context
+ * @param[in] pin An array of points forming the polygon
+ * @param count_in The number of elements inside @p pin
+ */
+void graphics_draw_polygon_clipped(struct graphics *gra, struct graphics_gc *gc, struct point *pin, int count_in) {
+    struct point_rect r=gra->r;
+    int limit=10000;
+    struct point *pa1=g_alloca(sizeof(struct point) * (count_in < limit ? count_in*8+1:0));
+    struct point *clipped;
+    int count_out = count_in*8+1;
+
+    /* prepare buffer */
+    if (count_in < limit) {
+        /* use on stack buffer */
+        clipped=pa1;
+    } else {
+        /* too big. allocate buffer (slower) */
+        clipped=g_new(struct point, count_in*8+1);
+    }
+
+    graphics_clip_polygon(&r, pin, count_in, clipped, &count_out);
+    graphics_draw_polygon(gra, gc, clipped, count_out);
+
+    /* if we had to allocate buffer, free it */
     if (count_in >= limit) {
-        g_free(p1);
-        g_free(p2);
+        g_free(clipped);
     }
 }
 
+/**
+ * @brief Draw a plain polygon with holes on the display
+ *
+ * @param gra The graphics instance on which to draw
+ * @param gc The graphics context
+ * @param[in] pin An array of points forming the polygon
+ * @param count_in The number of elements inside @p pin
+ * @param hole_count The number of hole polygons to cut out
+ * @param pcount array of [hole_count] integers giving the number of
+ *        points per hole
+ * @param holes array of point arrays for the hole polygons
+ */
+static void graphics_draw_polygon_with_holes_clipped(struct graphics *gra, struct graphics_gc *gc, struct point *pin,
+        int count_in, int hole_count, int* ccount, struct point **holes) {
+    int i;
+    struct point_rect r=gra->r;
+    int limit=10000;
+    struct point *pa1;
+    struct point *clipped;
+    int total_count_in;
+    int count_out;
+    int count_used;
+    int found_hole_count;
+    int *found_ccount;
+    struct point ** found_holes;
+    /* get total node count for polygon plus all holes */
+    total_count_in = count_in;
+    for(i = 0; i < hole_count; i ++) {
+        total_count_in += ccount[i];
+    }
+    count_out = total_count_in*8+1+hole_count;
+
+    /* prepare buffer */
+    pa1=g_alloca(sizeof(struct point) * (total_count_in < limit ? total_count_in*8+1:0));
+    if (count_in < limit) {
+        /* use on stack buffer */
+        clipped=pa1;
+    } else {
+        /* too big. allocate buffer (slower) */
+        clipped=g_new(struct point, count_in*8+1);
+    }
+    count_used=0;
+
+    /* prepare arrays for new holes */
+    found_ccount=g_alloca(sizeof(int)*hole_count);
+    found_holes=g_alloca(sizeof(struct point*)*hole_count);
+    found_hole_count=0;
+
+    /* clip outer polygon */
+    graphics_clip_polygon(&r, pin, count_in, clipped, &count_out);
+    count_used += count_out;
+    /* clip the holes */
+    for (i=0; i < hole_count; i ++) {
+        struct point* buffer = clipped + count_used;
+        int count = total_count_in*8+1+hole_count - count_used;
+        graphics_clip_polygon(&r, holes[i], ccount[i], buffer, &count);
+        count_used +=count;
+        if(count > 0) {
+            /* only if there are points left after clipping */
+            found_ccount[found_hole_count]=count;
+            found_holes[found_hole_count]=buffer;
+            found_hole_count ++;
+        }
+    }
+    /* call drawing function */
+    graphics_draw_polygon_with_holes(gra, gc, clipped, count_out, found_hole_count, found_ccount, found_holes);
+
+    /* if we had to allocate buffer, free it */
+    if (total_count_in >= limit) {
+        g_free(clipped);
+    }
+}
 
 static void display_context_free(struct display_context *dc) {
     if (dc->gc)
@@ -2387,9 +2530,9 @@ static void displayitem_free_holes(struct displayitem_poly_holes * holes) {
 
 static inline void displayitem_draw_polygon (struct display_context * dc, struct graphics * gra, struct point * pa,
         int count, struct displayitem_poly_holes * holes) {
-    /*TODO: implement a "clipped" version of graphics_draw_polygon_with_holes*/
     if((holes != NULL) && (holes->count > 0))
-        graphics_draw_polygon_with_holes(gra, dc->gc, pa, count, holes->count, holes->ccount, (struct point **)holes->coords);
+        graphics_draw_polygon_with_holes_clipped(gra, dc->gc, pa, count, holes->count, holes->ccount,
+                (struct point **)holes->coords);
     else
         graphics_draw_polygon_clipped(gra, dc->gc, pa, count);
 }