[dia] path: fix Difference sometimes not closing the path

[Hans Breuer <hans src gnome org>]

commit 2edd83fbcd2f5afe4464de2ec40d7d8c0cbe32a1
Author: Hans Breuer <hans breuer org>
Date:   Sun Sep 7 16:09:43 2014 +0200

    path: fix Difference sometimes not closing the path
    
    distance_bez_shape_point() was miscalculating the distance of
    non-closed path making selection harder. Now handled because
    such path can be created by other means, too.
    
    _curve_from_segment() did not correctly flip a line-to, the
    remaining changes should simply increase readability (typos,
    documentation updates)
    
    unrelated: stdpath_get_object_menu() make "Show Control Lines"
    a toggle menu.

 lib/geometry.c      |   15 ++++++++++++++-
 lib/path-math.c     |   50 +++++++++++++++++++++++++++++++++-----------------
 lib/standard-path.c |   15 ++++++++++-----
 3 files changed, 57 insertions(+), 23 deletions(-)
---
diff --git a/lib/geometry.c b/lib/geometry.c
index 1e95562..ebbe07a 100644
--- a/lib/geometry.c
+++ b/lib/geometry.c
@@ -341,6 +341,7 @@ distance_bez_shape_point(const BezPoint *b, guint npoints,
                          real line_width, const Point *point)
 {
   Point last;
+  const Point *close_to; /* path must be closed to calculate distance */
   guint i;
   real line_dist = G_MAXFLOAT;
   guint crossings = 0;
@@ -348,6 +349,7 @@ distance_bez_shape_point(const BezPoint *b, guint npoints,
   g_return_val_if_fail(b[0].type == BEZ_MOVE_TO, -1);
 
   last = b[0].p1;
+  close_to = &b[0].p1;
 
   for (i = 1; i < npoints; i++) {
     real dist;
@@ -356,12 +358,15 @@ distance_bez_shape_point(const BezPoint *b, guint npoints,
     case BEZ_MOVE_TO:
       /* no complains, there are renderers capable to handle this */
       last = b[i].p1;
+      close_to = &b[i].p1;
       break;
     case BEZ_LINE_TO:
       dist = distance_line_point(&last, &b[i].p1, line_width, point);
       crossings += line_crosses_ray(&last, &b[i].p1, point);
       line_dist = MIN(line_dist, dist);
       last = b[i].p1;
+      if (close_to && close_to->x == last.x && close_to->y == last.y)
+        close_to = NULL;
       break;
     case BEZ_CURVE_TO:
       dist = bez_point_distance_and_ray_crosses(&last, &b[i].p1, &b[i].p2,
@@ -369,11 +374,19 @@ distance_bez_shape_point(const BezPoint *b, guint npoints,
                                                &crossings);
       line_dist = MIN(line_dist, dist);
       last = b[i].p3;
+      if (close_to && close_to->x == last.x && close_to->y == last.y)
+        close_to = NULL;
       break;
     }
   }
+  if (close_to) {
+    /* final, implicit line-to */
+    real dist = distance_line_point(&last, close_to, line_width, point);
+    crossings += line_crosses_ray(&last, close_to, point);
+    line_dist = MIN(line_dist, dist);
+  }
   /* If there is an odd number of ray crossings, we are inside the polygon.
-   * Otherwise, return the minium distance from a line segment */
+   * Otherwise, return the minimum distance from a line segment */
   if (crossings % 2 == 1)
     return 0.0;
   else
diff --git a/lib/path-math.c b/lib/path-math.c
index 90b1e58..7adf6f6 100644
--- a/lib/path-math.c
+++ b/lib/path-math.c
@@ -150,6 +150,15 @@ _segment_is_moveto (const BezierSegment *bs)
     return TRUE;
   return FALSE;
 }
+static gboolean
+_segment_is_lineto (const BezierSegment *bs)
+{
+  if (   memcmp (&bs->p0, &bs->p1, sizeof (Point)) != 0 /* not move-to */
+      && memcmp (&bs->p1, &bs->p2, sizeof (Point)) == 0
+      && memcmp (&bs->p1, &bs->p3, sizeof (Point)) == 0)
+    return TRUE;
+  return FALSE;
+}
 
 /* search precision */
 static const real EPSILON = 0.0001;
@@ -201,9 +210,11 @@ bezier_bezier_intersection (GArray *crossing,
   /* if the boxes are small enough we can calculate the point */
   if (small_a && small_b) {
     /* intersecting and both small, should not matter which one is used */
-    Point pt = { (bbox.right + bbox.left) / 2, (bbox.bottom + bbox.top) / 2 };
+    Point pt = { (abox.right + abox.left + bbox.right + bbox.left) / 4,
+                (abox.bottom + abox.top + bbox.bottom + bbox.top) / 4 };
     Intersection is;
     int i;
+
     for (i = 0; i < crossing->len; ++i) {
       /* if it's already included we are done */
       if (distance_point_point (&g_array_index (crossing, Intersection, i).pt, &pt) < 1.4142*EPSILON)
@@ -262,7 +273,7 @@ _curve_from_segment (BezPoint *bp, const BezierSegment *a, gboolean flip)
 {
   if (_segment_is_moveto (a))
     bp->type = BEZ_MOVE_TO;
-  else if (memcmp (&a->p1, &a->p2, sizeof(Point)) == 0)
+  else if (_segment_is_lineto (a))
     bp->type = BEZ_LINE_TO;
   else
     bp->type = BEZ_CURVE_TO;
@@ -271,9 +282,13 @@ _curve_from_segment (BezPoint *bp, const BezierSegment *a, gboolean flip)
     bp->p2 = a->p2;
     bp->p3 = a->p3;
   } else {
-    bp->p1 = a->p2;
-    bp->p2 = a->p1;
-    bp->p3 = a->p0;
+    if (bp->type != BEZ_CURVE_TO) {
+      bp->p1 = bp->p2 = bp->p3 = a->p0;
+    } else {
+      bp->p1 = a->p2;
+      bp->p2 = a->p1;
+      bp->p3 = a->p0;
+    }
   }
 }
 
@@ -323,7 +338,14 @@ _path_to_segments (const GArray *path)
       g_array_append_val (segs, bs);
   }
   /* if the path is not closed do an explicit line-to */
-  if (memcmp (&last_move->p1, &bs.p3, sizeof(Point)) != 0) {
+  if (distance_point_point (&last_move->p1, &bs.p3) < EPSILON) {
+    /* if the error is small enough just modify the last point */
+    BezierSegment *e = &g_array_index (segs, BezierSegment, segs->len - 1);
+    if (_segment_is_lineto (e))
+      e->p1 = e->p2 = e->p3 = last_move->p1;
+    else
+      e->p3 = last_move->p1;
+  } else {
     bs.p0 = bs.p3;
     bs.p1 = bs.p2 = bs.p3 = last_move->p1;
     g_array_append_val (segs, bs);
@@ -354,7 +376,7 @@ _compare_split (gconstpointer as, gconstpointer bs)
  * all segment splits and create unique segment index.
  *
  * Split.seg is the index to the segment to split before this function.
- * After the split it indexes the last segment in the row of splits.
+ * After the splits are applied every split.seq is unique.
  */
 static void
 _split_segments (GArray *segs, GArray *splits, const GArray *other)
@@ -401,16 +423,14 @@ _split_segments (GArray *segs, GArray *splits, const GArray *other)
     Split *sp = &g_array_index (splits, Split, i);
     BezierSegment *bs = &g_array_index (segs, BezierSegment, sp->seg);
     BezierSegment left, right;
-    Point pt;
     int to, j;
 
     if (i == 0 && sp->seg > 0)
       g_array_append_vals (pending, &g_array_index (segs, BezierSegment, 0), sp->seg);
 
     bezier_split (bs, &left, &right);
-    pt = right.p0;
     sp->outside = distance_bez_shape_point (&g_array_index (other, BezPoint, 0), other->len,
-                                          0 /* line width */, &pt) > 0.0;
+                                          0 /* line width */, &right.p0) > 0.0;
     /* also remember the sub-path */
     to = g_array_index (splits, Split, (i+1)%splits->len).seg;
     sp->path = g_array_new (FALSE, FALSE, sizeof(BezierSegment));
@@ -711,9 +731,9 @@ _make_path (GArray *one, /*!< array<BezierSegment> from first path */
  * \brief Combine two path into a single one with the given operation
  *
  * This should (but does not) consider
+ *  - holes within the path more explicitely
  *  - self intersections in a path
- *  - winding rule
- *  - typical path operations (Union, Difference, Intersection, Exclusion, ...)
+ *  - winding rule?
  */
 GArray *
 path_combine (const GArray   *p1,
@@ -733,10 +753,6 @@ path_combine (const GArray   *p1,
   one = _path_to_segments (p1);
   two = _path_to_segments (p2);
   crossing = _find_intersections (one, two);
-
-  if (crossing)
-    g_print ("Total path intersections: %d\n", crossing->len);
-
   if (crossing) {
     /* Now crossing includes points in arbitrary order. Every point has four lines
      * going in or out - two from p1, two from p2. Split one and two into segments
@@ -747,7 +763,7 @@ path_combine (const GArray   *p1,
     _split_segments (one, one_splits, p2);
     _split_segments (two, two_splits, p1);
 
-    /* XXX: convert segments back to a single path */
+    /* convert segments back to a single path */
     if (one_splits->len < 2) { /* XXX: just joining again */
       result = _make_path0 (one, one_splits, two, two_splits);
     } else if (debug) {
diff --git a/lib/standard-path.c b/lib/standard-path.c
index 3f2f224..df77007 100644
--- a/lib/standard-path.c
+++ b/lib/standard-path.c
@@ -29,7 +29,7 @@
  * with a single move-to, too.
  * Instead of breaking forward compatibility this is implementing a new bezier
  * based object, which can render holes, even if the _DiaRenderer can not. It is 
- * using a newer file format representaion through BezPointarrayProperty.
+ * using a newer file format representation through BezPointarrayProperty.
  */
 #include <config.h>
 
@@ -143,7 +143,7 @@ static PropDescription stdpath_props[] = {
   PROP_STD_LINE_JOIN_OPTIONAL,
   PROP_STD_LINE_CAPS_OPTIONAL,
   PROP_STD_FILL_COLOUR_OPTIONAL,
-  /* just to simplify transfering properties between objects */
+  /* just to simplify transferring properties between objects */
   { "show_background", PROP_TYPE_BOOL, PROP_FLAG_DONT_SAVE,  N_("Draw background"), NULL, NULL },
   { "show_control_lines", PROP_TYPE_BOOL, PROP_FLAG_OPTIONAL, N_("Draw Control Lines") },
   { "pattern", PROP_TYPE_PATTERN, PROP_FLAG_VISIBLE|PROP_FLAG_OPTIONAL, N_("Pattern"), NULL },
@@ -551,7 +551,7 @@ _show_control_lines (DiaObject *obj, Point *clicked, gpointer data)
 static DiaMenuItem _stdpath_menu_items[] = {
   { N_("Convert to Bezier"), _convert_to_beziers_callback, NULL, DIAMENU_ACTIVE },
   { N_("Invert Path"), _invert_path_callback, NULL, DIAMENU_ACTIVE },
-  { N_("Show Control Lines"), _show_control_lines, NULL, DIAMENU_ACTIVE }
+  { N_("Show Control Lines"), _show_control_lines, NULL, DIAMENU_ACTIVE | DIAMENU_TOGGLE }
 };
 static DiaMenu _stdpath_menu = {
   "Path",
@@ -570,6 +570,11 @@ static DiaMenu _stdpath_menu = {
 static DiaMenu *
 stdpath_get_object_menu(StdPath *stdpath, Point *clickedpoint)
 {
+  const int i = G_N_ELEMENTS(_stdpath_menu_items) - 1;
+  if (stdpath->show_control_lines)
+    _stdpath_menu_items[i].active |= DIAMENU_TOGGLE_ON;
+  else
+    _stdpath_menu_items[i].active &= ~DIAMENU_TOGGLE_ON;
   return &_stdpath_menu;
 }
 /*!
@@ -605,8 +610,8 @@ stdpath_set_props (StdPath *stdpath, GPtrArray *props)
     else
       stdpath->stroke_or_fill &= ~PDO_FILL;
   }
-  /* now when transfering properties from text we'll loose stroke and fill
-   * Instead of drawing nothing maket it just fill.
+  /* now when transferring properties from text we'll loose stroke and fill
+   * Instead of drawing nothing make it just fill.
    */
   if (!stdpath->stroke_or_fill)
     stdpath->stroke_or_fill = PDO_FILL;