Add:graphics/windows: polygons with holes for windows CE #862

Add:graphics/windows: polygons with holes for windows CE

This uses the same "hand and foot" raycasting algorithm than the SDL version does since WindowsCE lacks the fancy drawing routines of better Windows.

1 files changed, 170 insertions, 5 deletions

diff --git a/navit/graphics/win32/graphics_win32.c b/navit/graphics/win32/graphics_win32.c
index 6bcad3be6..6346e59f7 100644
--- a/navit/graphics/win32/graphics_win32.c
+++ b/navit/graphics/win32/graphics_win32.c
@@ -829,8 +829,177 @@ static void draw_polygon(struct graphics_priv *gr, struct graphics_gc_priv *gc,
 
 #if HAVE_API_WIN32_CE
 /*
- * Windows CE doesn't support PaintPath used for other versions. No polygon with holes support for CE yet.
+ * Windows CE doesn't feature GraphicsPath, so in order to draw filled polygons
+ * with holes, we need to resort on manual raycasting. The following functions
+ * have been inspired from SDL backend that does need to raycast all polygons.
  */
+
+/* Helper qsort callback for polygon drawing */
+static int gfxPrimitivesCompareInt(const void *a, const void *b) {
+    return (*(const int *) a) - (*(const int *) b);
+}
+
+/**
+ * @brief render filled polygon with holes by raycasting along the y axis
+ *
+ * This function renders a filled polygon that can have holes by SDL primitive
+ * graphic functions by raycasting along the y axis. This works basically the same
+ * as for complex polygons. Only difference is the "holes" are individual
+ * polygon loops not connected to the outer loop.
+ * FIXME: This draws well as long as the "hole" does not intersect with the
+ * outer polygon. However such multipolygons are seen a mapping error in OSM
+ * and therefore the rendering err may even help in detecting them.
+ * But this could be fixed by never starting a line on a vertex that came from a
+ * hole intersection.
+ *
+ * @param gr graphics instance
+ * @param gc graphics context
+ * @param p Array of points for the outer polygon
+ * @param count Number of points in outer polygon
+ * @param hole_count Number of hole polygons
+ * @param ccount number of points per hole polygon
+ * @oaram holes array of point arrays. One for each "hole"
+ */
+static void draw_polygon_with_holes (struct graphics_priv *gr, struct graphics_gc_priv *gc, struct point *p, int count,
+                                     int hole_count, int* ccount, struct point **holes) {
+    int vertex_max;
+    int vertex_count;
+    int * vertexes;
+    int miny, maxy;
+    int i;
+    int y;
+    HPEN holdpen;
+    HBRUSH holdbrush;
+    HPEN linepen;
+
+    /* Sanity check number of edges */
+    if (count < 3) {
+        return;
+    }
+
+    /*
+     * Prepare a buffer for vertexes. Maximum number of vertexes is the number of points
+     * of polygon and holes
+     */
+    vertex_max = count;
+    for(i =0; i < hole_count; i ++) {
+        vertex_max += ccount[i];
+    }
+    vertexes = g_malloc(sizeof(int) * vertex_max);
+    if(vertexes == NULL) {
+        return;
+    }
+
+    /* create pen to draw the lines */
+    linepen = CreatePen( PS_SOLID, 1, gc->fg_color );
+
+    /* remeber pen and brush */
+    holdpen = SelectObject( gr->hMemDC, linepen );
+    holdbrush = SelectObject( gr->hMemDC, gc->hbrush );
+
+    /* calculate y min and max coordinate. We can ignore the holes, as we won't render hole
+     * parts "bigger" than the surrounding polygon.*/
+    miny = p[0].y;
+    maxy = p[0].y;
+    for (i = 1; (i < count); i++) {
+        if (p[i].y < miny) {
+            miny = p[i].y;
+        } else if (p[i].y > maxy) {
+            maxy = p[i].y;
+        }
+    }
+
+    /* scan y coordinates from miny to maxy */
+    for(y = miny; y <= maxy ; y ++) {
+        int h;
+        vertex_count=0;
+        /* calculate the intersecting points of the polygon with current y and add to vertexes array*/
+        for (i = 0; (i < count); i++) {
+            int ind1;
+            int ind2;
+            struct point p1;
+            struct point p2;
+
+            if (!i) {
+                ind1 = count - 1;
+                ind2 = 0;
+            } else {
+                ind1 = i - 1;
+                ind2 = i;
+            }
+            p1.y = p[ind1].y;
+            p2.y = p[ind2].y;
+            if (p1.y < p2.y) {
+                p1.x = p[ind1].x;
+                p2.x = p[ind2].x;
+            } else if (p1.y > p2.y) {
+                p2.y = p[ind1].y;
+                p1.y = p[ind2].y;
+                p2.x = p[ind1].x;
+                p1.x = p[ind2].x;
+            } else {
+                continue;
+            }
+            if ( ((y >= p1.y) && (y < p2.y)) || ((y == maxy) && (y > p1.y) && (y <= p2.y)) ) {
+                vertexes[vertex_count++] = ((65536 * (y - p1.y)) / (p2.y - p1.y)) * (p2.x - p1.x) + (65536 * p1.x);
+            }
+        }
+        for(h= 0; h < hole_count; h ++) {
+            /* add the intersecting points from the holes as well */
+            for (i = 0; (i < ccount[h]); i++) {
+                int ind1;
+                int ind2;
+                struct point p1;
+                struct point p2;
+
+                if (!i) {
+                    ind1 = ccount[h] - 1;
+                    ind2 = 0;
+                } else {
+                    ind1 = i - 1;
+                    ind2 = i;
+                }
+                p1.y = holes[h][ind1].y;
+                p2.y = holes[h][ind2].y;
+                if (p1.y < p2.y) {
+                    p1.x = holes[h][ind1].x;
+                    p2.x = holes[h][ind2].x;
+                } else if (p1.y > p2.y) {
+                    p2.y = holes[h][ind1].y;
+                    p1.y = holes[h][ind2].y;
+                    p2.x = holes[h][ind1].x;
+                    p1.x = holes[h][ind2].x;
+                } else {
+                    continue;
+                }
+                if ( ((y >= p1.y) && (y < p2.y)) || ((y == maxy) && (y > p1.y) && (y <= p2.y)) ) {
+                    vertexes[vertex_count++] = ((65536 * (y - p1.y)) / (p2.y - p1.y)) * (p2.x - p1.x) + (65536 * p1.x);
+                }
+            }
+        }
+
+        /* sort the vertexes */
+        qsort(vertexes, vertex_count, sizeof(int), gfxPrimitivesCompareInt);
+        /* draw the lines between every second vertex */
+        for (i = 0; (i < vertex_count); i +=2) {
+            int xa;
+            int xb;
+            xa = (vertexes[i] >> 16);
+            xb = (vertexes[i+1] >> 16);
+            MoveToEx( gr->hMemDC, xa+1, y, NULL );
+            LineTo( gr->hMemDC, xb, y );
+        }
+    }
+    /* free vertex buffer */
+    g_free(vertexes);
+
+    /* restore pen and brush */
+    SelectObject( gr->hMemDC, holdbrush);
+    SelectObject( gr->hMemDC, holdpen);
+
+    /* delete linepen */
+    DeleteObject(linepen);
+}
 #else
 static void draw_polygon_with_holes (struct graphics_priv *gr, struct graphics_gc_priv *gc, struct point *p, int count,
                                      int hole_count, int* ccount, struct point **holes) {
@@ -1522,11 +1691,7 @@ static struct graphics_methods graphics_methods = {
     NULL, /* show_native_keyboard */
     NULL, /* hide_native_keyboard */
     NULL, /* get dpi */
-#if HAVE_API_WIN32_CE
-    NULL, /* draw_polygon_with_holes */
-#else
     draw_polygon_with_holes
-#endif
 };