[dia] Misc - Ngon: special handling for Hexagram and more

[Hans Breuer <hans src gnome org>]

commit 42cde4cb7ad762284d39abb5d9de56f668c9796b
Author: Hans Breuer <hans breuer org>
Date:   Sat May 31 16:05:19 2014 +0200

    Misc - Ngon: special handling for Hexagram and more
    
    Drawing a crossing star take a little more points to be properly filled
    if the number of rays and windings are not relatively prime. Some more
    code needed to do that for {n/3} and higher.
    See http://en.wikipedia.org/wiki/Star_polygon for more details.

 lib/geometry.c       |   17 +++++++++++++++++
 lib/geometry.h       |    3 +++
 lib/libdia.def       |    1 +
 objects/Misc/n_gon.c |   50 +++++++++++++++++++++++++++++++++++++++-----------
 4 files changed, 60 insertions(+), 11 deletions(-)
---
diff --git a/lib/geometry.c b/lib/geometry.c
index 4936af6..d27f6b0 100644
--- a/lib/geometry.c
+++ b/lib/geometry.c
@@ -518,6 +518,23 @@ void point_perp(Point *p, real a, real b, real c, Point *perp) {
   return;
 }
 
+gboolean
+line_line_intersection (Point *crossing,
+                       const Point *p1, const Point *p2,
+                       const Point *p3, const Point *p4)
+{
+  real d = (p1->x - p2->x) * (p3->y - p4->y) - (p1->y - p2->y) * (p3->x - p4->x);
+  real a, b;
+
+  if (fabs(d) < 0.0000001)
+    return FALSE;
+  a = p1->x * p2->y - p1->y * p2->x;
+  b = p3->x * p4->y - p3->y * p4->x;
+  crossing->x = (a * (p3->x - p4->x) - (p1->x - p2->x) * b) / d;
+  crossing->y = (a * (p3->y - p4->y) - (p1->y - p2->y) * b) / d;
+  return TRUE;
+}
+
 /* Compute a circular arc fillet between lines L1 (p1 to p2)
    and L2 (p3 to p4) with radius r.
    The circle center is c.
diff --git a/lib/geometry.h b/lib/geometry.h
index 13b49e5..013de16 100644
--- a/lib/geometry.h
+++ b/lib/geometry.h
@@ -377,6 +377,9 @@ void transform_bezpoint (BezPoint *bpt, const DiaMatrix *m);
 real dot2(Point *p1, Point *p2);
 void line_coef(real *a, real *b, real *c, Point *p1, Point *p2);
 real line_to_point(real a, real b , real c, Point *p);
+gboolean line_line_intersection (Point *crossing,
+                                const Point *p1, const Point *p2,
+                                const Point *p3, const Point *p4);
 void point_perp(Point *p, real a, real b, real c, Point *perp);
 gboolean fillet(Point *p1, Point *p2, Point *p3, Point *p4,
                real r, Point *c, real *pa, real *aa);
diff --git a/lib/libdia.def b/lib/libdia.def
index 4bb03e2..38d1f65 100644
--- a/lib/libdia.def
+++ b/lib/libdia.def
@@ -523,6 +523,7 @@ EXPORTS
  new_layer
 
  line_bbox
+ line_line_intersection
 
  dia_error_quark
  
diff --git a/objects/Misc/n_gon.c b/objects/Misc/n_gon.c
index 3d92477..c41c80f 100644
--- a/objects/Misc/n_gon.c
+++ b/objects/Misc/n_gon.c
@@ -364,10 +364,9 @@ _ngon_make_name (Ngon *ng)
 /*!
  * \brief Sort points to produce a star with crossing edges
  *
- * We could support the different possibilities explained by
+ * We support the different possibilities explained by
  * http://en.wikipedia.org/wiki/Star_polygon
- * but first need a good user interface to select between this
- * number of point dependent selection.
+ * via the density parameter mostly.
  */
 static void
 _ngon_adjust_for_crossing (Ngon *ng)
@@ -380,10 +379,35 @@ _ngon_adjust_for_crossing (Ngon *ng)
   g_array_insert_vals (points, 0,
                       &g_array_index (ng->points, Point, 0),
                       ng->points->len);
-  for (i = 1; i < n; ++i) {
-    int j = (i * step) % n;
-    g_array_index (ng->points, Point, i).x = g_array_index (points, Point, j).x;
-    g_array_index (ng->points, Point, i).y = g_array_index (points, Point, j).y;
+  if (1 == step && n > 5 && (n % 2) == 0) {
+    /* calculate the crossing of edges as extra point */
+    Point crossing;
+    if (!line_line_intersection (&crossing,
+                                &g_array_index (points, Point, 0), &g_array_index (points, Point, n-2),
+                                &g_array_index (points, Point, 1), &g_array_index (points, Point, n-1)))
+      g_warning ("No intersection?");
+    step = 2;
+    for (i = 0; i < n/2; ++i) {
+      int j = (i * step) % n;
+      g_array_index (ng->points, Point, i).x = g_array_index (points, Point, j).x;
+      g_array_index (ng->points, Point, i).y = g_array_index (points, Point, j).y;
+    }
+    /* go backward for the second half */
+    for (i = 0; i < n/2; ++i) {
+      int j = (n - 1 - i * step) % n;
+      g_array_index (ng->points, Point, i + n/2).x = g_array_index (points, Point, j).x;
+      g_array_index (ng->points, Point, i + n/2).y = g_array_index (points, Point, j).y;
+    }
+    /* insert the crossing point at the end */
+    g_array_insert_val (ng->points, n, crossing);
+    /* insert the crossing point in the middle */
+    g_array_insert_val (ng->points, n/2, crossing);
+  } else {
+    for (i = 1; i < n; ++i) {
+      int j = (i * step) % n;
+      g_array_index (ng->points, Point, i).x = g_array_index (points, Point, j).x;
+      g_array_index (ng->points, Point, i).y = g_array_index (points, Point, j).y;
+    }
   }
   g_array_free (points, TRUE);
 }
@@ -405,11 +429,15 @@ _ngon_update_data (Ngon *ng)
     n = ng->num_rays * 2;
 
   /* ensure density stays in range */
-  if (ng->last_density > ng->density)
-    ng->density = _calc_step (ng->num_rays, ng->density);
-  else
+  if (ng->last_density > ng->density) {
+    real temp = _calc_step (ng->num_rays, ng->density);
+    /* special case for Hexagram and above */
+    if (temp == 1 && ng->kind == NGON_CROSSING && ng->num_rays > 5)
+      temp = 2;
+    ng->density = temp;
+  } else {
     ng->density = _calc_step_up (ng->num_rays, ng->density);
-
+  }
   _ngon_make_name (ng);
   if (1 || n != ng->points->len) {
     /* recalculate all points */