Fix:graphics/android: polygons with hole drawing (#973)

* graphics/android: Fix: array size

* g_malloc JNI arrays instead of using stack. Draw triangles.

We now know that polygons with holes tend to get big so don't even try
to allocate that on stack.

* Ensure polygons are correctly directed for android.

* Fix typos

* Explicit decisions

2 files changed, 74 insertions, 16 deletions

diff --git a/navit/android/src/org/navitproject/navit/NavitGraphics.java b/navit/android/src/org/navitproject/navit/NavitGraphics.java
index 855f93d87..79ee27d81 100644
--- a/navit/android/src/org/navitproject/navit/NavitGraphics.java
+++ b/navit/android/src/org/navitproject/navit/NavitGraphics.java
@@ -893,7 +893,7 @@ class NavitGraphics {
         // for every hole
         for (int i = 0; i < ccount.length; i++) {
             // drop holes with less than 3 coordinates
-            if (ccount[i] > 6) {
+            if (ccount[i] >= 6) {
                 path.moveTo(holes[coordinatesUsed + 0], holes[coordinatesUsed + 1]);
                 for (int j = 2; j < ccount[i]; j += 2) {
                     path.lineTo(holes[coordinatesUsed + j], holes[coordinatesUsed + j + 1]);
diff --git a/navit/graphics/android/graphics_android.c b/navit/graphics/android/graphics_android.c
index 030c9f3ab..ccc929432 100644
--- a/navit/graphics/android/graphics_android.c
+++ b/navit/graphics/android/graphics_android.c
@@ -295,16 +295,72 @@ static void draw_lines(struct graphics_priv *gra, struct graphics_gc_priv *gc, s
     (*jnienv)->DeleteLocalRef(jnienv, points);
 }
 
+/* calculate the area a polygon covers in pixels.
+ *
+ * Bonus: Positive area indicates clockwise, negative counter clockwise
+ */
+static int polygon_area(struct point* p, int count) {
+    int area =0;
+    int i;
+
+    /* initialize j with the last point */
+    int j = count -1;
+
+    for(i=0; i < count; i ++) {
+        area += (p[j].x + p[i].x) * (p[j].y - p[i].y);
+        j = i; /* j is previous vertex to i */
+    }
+    return area/2;
+}
+
+/* returns if vertexes of given polygon are clockwise
+ *
+ * @returns: > o if clockwise, otherwise counter clockwise.
+ *
+ * Note: On self intersecting polygons, it will return if it is
+ * "mostly" clockwise. Be warned.
+ */
+static inline int is_clockwise (struct point * p, int count) {
+    return polygon_area(p, count);
+}
+
+/* copy over vertexes to the jni array. Allows to reverse the polygon */
+static int add_vertex_to_java_array(struct point * p, int count, jint * j_p, int reverse) {
+    int i;
+    if(reverse > 0) {
+        for(i=0; i < count; i ++) {
+            j_p[i*2]=p[(count -1) -i].x;
+            j_p[i*2+1]=p[(count -1) -i].y;
+        }
+    } else {
+        for(i=0; i < count; i ++) {
+            j_p[i*2]=p[i].x;
+            j_p[i*2+1]=p[i].y;
+        }
+    }
+    return count * 2;
+}
+
+/* prepare the java call to draw a polygon with holes. As Java drawing code assumes polygons are directed
+ * clockwise for outer and counter clockwise for inner, all polygons are checked and reversed if required.
+ * While the reversing does not add significant overhead, the calculating adds some overhead.
+ *
+ * TODO: Find a more performant way of doing this probably NOT requiring the java code to get the polygons
+ * directd.
+ */
 static void draw_polygon_with_holes (struct graphics_priv *gra, struct graphics_gc_priv *gc, struct point *p, int count,
                                      int hole_count, int* ccount, struct point **holes) {
     int i;
     /* need to get us some arrays for java */
     int java_p_size;
     jintArray java_p;
+    jint * j_p=NULL;
     int java_ccount_size;
     jintArray java_ccount;
+    jint * j_ccount=NULL;
     int java_holes_size;
     jintArray java_holes;
+    jint * j_holes=NULL;
 
     /* Don't even try to draw a polygon with less than 3 points */
     if(count < 3)
@@ -313,34 +369,33 @@ static void draw_polygon_with_holes (struct graphics_priv *gra, struct graphics_
     /* get java array for coordinates */
     java_p_size=count*2;
     java_p = (*jnienv)->NewIntArray(jnienv,java_p_size);
-    jint j_p[java_p_size];
-    for (i = 0 ; i < count ; i++) {
-        j_p[i*2]=p[i].x;
-        j_p[(i*2)+1]=p[i].y;
-    }
+    j_p = g_malloc(sizeof(jint) * java_p_size);
+
+    /* add outer polygon to java array. Ensure it's clockwise */
+    add_vertex_to_java_array(p, count, j_p, (is_clockwise(p, count) > 0)? 0: 1);
 
     /* get java array for ccount */
     java_ccount_size = hole_count;
     java_ccount=(*jnienv)->NewIntArray(jnienv,java_ccount_size);
-    jint j_ccount[java_ccount_size];
+    j_ccount=g_malloc(sizeof(jint) * java_ccount_size);
     /* get java array for hole coordinates */
     java_holes_size = 0;
     for(i=0; i < hole_count; i ++) {
         java_holes_size += ccount[i] * 2;
     }
-    java_holes=(*jnienv)->NewIntArray(jnienv,java_ccount_size);
-    /* copy over the holes to the jint array */
+    java_holes=(*jnienv)->NewIntArray(jnienv,java_holes_size);
+    j_holes=g_malloc(sizeof(jint) * java_holes_size);
+
+    /* copy over the holes to the jint coordinate array */
     int j_holes_used=0;
-    jint j_holes[java_holes_size];
     for(i=0; i < hole_count; i ++) {
-        int j;
+        /* remember this holes ccount */
         j_ccount[i] = ccount[i] * 2;
-        for(j=0; j<ccount[i]; j ++) {
-            j_holes[j_holes_used + (j * 2)] = holes[i][j].x;
-            j_holes[j_holes_used + (j * 2) +1] = holes[i][j].y;
-        }
-        j_holes_used += j_ccount[i];
+        /* add inner polygon. ensure its counter clockwise */
+        j_holes_used += add_vertex_to_java_array(holes[i], ccount[i], &(j_holes[j_holes_used]), (is_clockwise(holes[i],
+                        ccount[i]) <= 0)? 0: 1);
     }
+
     /* attach the arrays with their storage to the JVM */
     (*jnienv)->SetIntArrayRegion(jnienv, java_p, 0, java_p_size, j_p);
     (*jnienv)->SetIntArrayRegion(jnienv, java_ccount, 0, java_ccount_size, j_ccount);
@@ -352,6 +407,9 @@ static void draw_polygon_with_holes (struct graphics_priv *gra, struct graphics_
     (*jnienv)->DeleteLocalRef(jnienv, java_holes);
     (*jnienv)->DeleteLocalRef(jnienv, java_ccount);
     (*jnienv)->DeleteLocalRef(jnienv, java_p);
+    g_free(j_p);
+    g_free(j_ccount);
+    g_free(j_holes);
 }
 
 static void draw_polygon(struct graphics_priv *gra, struct graphics_gc_priv *gc, struct point *p, int count) {