Implement support for dashed and dotted ellipses in pic. Based on

a patch from Hartmut Henkel <hartmut_henkel@gmx.de>.

* src/preproc/pic/common.cpp (common_output::ellipse_arc,
common_output::dashed_ellipse, common_output::dotted_ellipse): New
functions.  Ellipse arcs are approximated with circle arcs.
* src/preproc/pic/common.h (common_output): Updated.
* src/preproc/pic/tex.cpp (tex_output::ellipse): Use new ellipse
functions.
* src/preproc/pic/troff.cpp (simple_output::ellipse): Ditto.

* src/preproc/pic/TODO, src/preproc/pic/pic.man: Updated.

6 files changed, 182 insertions, 11 deletions

diff --git a/src/preproc/pic/TODO b/src/preproc/pic/TODO
index 2346b575..a1d7554d 100644
--- a/src/preproc/pic/TODO
+++ b/src/preproc/pic/TODO
@@ -1,5 +1,3 @@
-Dotted and dashed ellipses.
-
 In troff mode, dotted and dashed splines.
 
 Make DELIMITED have type lstr; this would allow us to give better
diff --git a/src/preproc/pic/common.cpp b/src/preproc/pic/common.cpp
index 5075e936..a2dfe921 100644
--- a/src/preproc/pic/common.cpp
+++ b/src/preproc/pic/common.cpp
@@ -78,6 +78,157 @@ void common_output::dotted_circle(const position &cent, double rad,
     dot(cent + position(cos(ang), sin(ang))*rad, lt);
 }
 
+// recursive function for dash drawing, used by dashed_ellipse
+
+void common_output::ellipse_arc(const position &cent,
+				const position &z0, const position &z1,
+				const distance &dim, const line_type &lt)
+{
+  assert(lt.type == line_type::solid);
+  assert(dim.x != 0 && dim.y != 0);
+  double eps = 0.0001;
+  position zml = (z0 + z1) / 2;
+  // apply affine transformation (from ellipse to circle) to compute angle
+  // of new position, then invert transformation to get exact position
+  double psi = atan2(zml.y / dim.y, zml.x / dim.x);
+  position zm = position(dim.x * cos(psi), dim.y * sin(psi));
+  // to approximate the ellipse arc with one or more circle arcs, we
+  // first compute the radius of curvature in zm
+  double a_2 = dim.x * dim.x;
+  double a_4 = a_2 * a_2;
+  double b_2 = dim.y * dim.y;
+  double b_4 = b_2 * b_2;
+  double e_2 = a_2 - b_2;
+  double temp = a_4 * zm.y * zm.y + b_4 * zm.x * zm.x;
+  double rho = sqrt(temp / a_4 / b_4 * temp / a_4 / b_4 * temp);
+  // compute center of curvature circle
+  position M = position(e_2 * zm.x / a_2 * zm.x / a_2 * zm.x,
+			-e_2 * zm.y / b_2 * zm.y / b_2 * zm.y);
+  // compute distance between circle and ellipse arc at start and end
+  double phi0 = atan2(z0.y - M.y, z0.x - M.x);
+  double phi1 = atan2(z1.y - M.y, z1.x - M.x);
+  position M0 = position(rho * cos(phi0), rho * sin(phi0)) + M;
+  position M1 = position(rho * cos(phi1), rho * sin(phi1)) + M;
+  double dist0 = hypot(z0 - M0) / sqrt(z0 * z0);
+  double dist1 = hypot(z1 - M1) / sqrt(z1 * z1);
+  if (dist0 < eps && dist1 < eps)
+    solid_arc(M + cent, rho, phi0, phi1, lt);
+  else {
+    ellipse_arc(cent, z0, zm, dim, lt);
+    ellipse_arc(cent, zm, z1, dim, lt);
+  }
+}
+
+// output a dashed ellipse as a series of straight lines
+
+void common_output::dashed_ellipse(const position &cent, const distance &dim,
+				   const line_type &lt)
+{
+  assert(lt.type == line_type::dashed);
+  double dim_x = dim.x / 2;
+  double dim_y = dim.y / 2;
+  line_type slt = lt;
+  slt.type = line_type::solid;
+  double dw = lt.dash_width;
+  // we use an approximation to compute the ellipse length (found in:
+  // Bronstein, Semendjajew, Taschenbuch der Mathematik)
+  double lambda = (dim.x - dim.y) / (dim.x + dim.y);
+  double le = M_PI / 2 * (dim.x + dim.y)
+	      * ((64 - 3 * lambda * lambda * lambda * lambda )
+		 / (64 - 16 * lambda * lambda));
+  // for symmetry we make nmax a multiple of 8
+  int nmax = 8 * int(le / dw / 8 + 0.5);
+  if (nmax < 8) {
+    nmax = 8;
+    dw = le / 8;
+  }
+  int ndash = nmax / 2;
+  double gapwidth = (le - dw * ndash) / ndash;
+  double l = 0;
+  position z = position(dim_x, 0);
+  position zdot = z;
+  int j = 0;
+  int jmax = int(10 / lt.dash_width);
+  for (int i = 0; i <= nmax; i++) {
+    position zold = z;
+    position zpre = zdot;
+    double ld = (int(i / 2) + 0.5) * dw + int((i + 1) / 2) * gapwidth;
+    double lold = 0;
+    double dl = 1;
+    // find next position for fixed arc length
+    while (l < ld) {
+      j++;
+      lold = l;
+      zold = z;
+      double phi = j * 2 * M_PI / jmax;
+      z = position(dim_x * cos(phi), dim_y * sin(phi));
+      dl = hypot(z - zold);
+      l += dl;
+    }
+    // interpolate linearly between the last two points,
+    // using the length difference as the scaling factor
+    double delta = (ld - lold) / dl;
+    zdot = zold + (z - zold) * delta;
+    // compute angle of new position on the affine circle
+    // and use it to get the exact value on the ellipse
+    double psi = atan2(zdot.y / dim_y, zdot.x / dim_x);
+    zdot = position(dim_x * cos(psi), dim_y * sin(psi));
+    if ((i % 2 == 0) && (i > 1))
+      ellipse_arc(cent, zpre, zdot, dim / 2, slt);
+  }
+}
+
+// output a dotted ellipse as a series of dots
+
+void common_output::dotted_ellipse(const position &cent, const distance &dim,
+				   const line_type &lt)
+{
+  assert(lt.type == line_type::dotted);
+  double dim_x = dim.x / 2;
+  double dim_y = dim.y / 2;
+  line_type slt = lt;
+  slt.type = line_type::solid;
+  // we use an approximation to compute the ellipse length (found in:
+  // Bronstein, Semendjajew, Taschenbuch der Mathematik)
+  double lambda = (dim.x - dim.y) / (dim.x + dim.y);
+  double le = M_PI / 2 * (dim.x + dim.y)
+	      * ((64 - 3 * lambda * lambda * lambda * lambda )
+		 / (64 - 16 * lambda * lambda));
+  // for symmetry we make nmax a multiple of 4
+  int ndots = 4 * int(le / lt.dash_width / 4 + 0.5);
+  if (ndots < 4)
+    ndots = 4;
+  double l = 0;
+  position z = position(dim_x, 0);
+  int j = 0;
+  int jmax = int(10 / lt.dash_width);
+  for (int i = 1; i <= ndots; i++) {
+    position zold = z;
+    double lold = l;
+    double ld = i * le / ndots;
+    double dl = 1;
+    // find next position for fixed arc length
+    while (l < ld) {
+      j++;
+      lold = l;
+      zold = z;
+      double phi = j * 2 * M_PI / jmax;
+      z = position(dim_x * cos(phi), dim_y * sin(phi));
+      dl = hypot(z - zold);
+      l += dl;
+    }
+    // interpolate linearly between the last two points,
+    // using the length difference as the scaling factor
+    double delta = (ld - lold) / dl;
+    position zdot = zold + (z - zold) * delta;
+    // compute angle of new position on the affine circle
+    // and use it to get the exact value on the ellipse
+    double psi = atan2(zdot.y / dim_y, zdot.x / dim_x);
+    zdot = position(dim_x * cos(psi), dim_y * sin(psi));
+    dot(cent + zdot, slt);
+  }
+}
+
 // return non-zero iff we can compute a center
 
 int compute_arc_center(const position &start, const position &cent,
diff --git a/src/preproc/pic/common.h b/src/preproc/pic/common.h
index 90b65fa9..d04da97a 100644
--- a/src/preproc/pic/common.h
+++ b/src/preproc/pic/common.h
@@ -1,5 +1,5 @@
 // -*- C++ -*-
-/* Copyright (C) 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
+/* Copyright (C) 1989, 1990, 1991, 1992, 1993 Free Software Foundation, Inc.
      Written by James Clark (jjc@jclark.com)
 
 This file is part of groff.
@@ -33,8 +33,13 @@ private:
 	       double gap_width, double *offsetp);
 protected:
   virtual void dot(const position &, const line_type &) = 0;
+  void ellipse_arc(const position &, const position &,
+		   const position &, const distance &,
+		   const line_type &);
   void dashed_circle(const position &, double rad, const line_type &);
   void dotted_circle(const position &, double rad, const line_type &);
+  void dashed_ellipse(const position &, const distance &, const line_type &);
+  void dotted_ellipse(const position &, const distance &, const line_type &);
   void dashed_arc(const position &, const position &, const position &,
 		  const line_type &);
   void dotted_arc(const position &, const position &, const position &,
diff --git a/src/preproc/pic/pic.man b/src/preproc/pic/pic.man
index c12e93ab..45bc2d62 100644
--- a/src/preproc/pic/pic.man
+++ b/src/preproc/pic/pic.man
@@ -675,8 +675,8 @@ Arcs now have compass points
 determined by the circle of which the arc is a part.
 .
 .LP
-Circles and arcs can be dotted or dashed.
-In \*(tx mode splines can be dotted or dashed.
+Circles, ellipses, and arcs can be dotted or dashed.
+In \*(tx mode splines can be dotted or dashed also.
 .
 .LP
 Boxes can have rounded corners.
diff --git a/src/preproc/pic/tex.cpp b/src/preproc/pic/tex.cpp
index dbebe461..961c0dca 100644
--- a/src/preproc/pic/tex.cpp
+++ b/src/preproc/pic/tex.cpp
@@ -324,12 +324,25 @@ void tex_output::ellipse(const position &cent, const distance &dim,
     printf("    \\special{sh %.3f}%%\n", fill);
   }
   position c = transform(cent);
-  printf("    \\special{%s %d %d %d %d 0 6.28319}%%\n",
-	 (lt.type == line_type::invisible ? "ia" : "ar"),
-	 milliinches(c.x),
-	 milliinches(c.y),
-	 milliinches(dim.x/(2.0*scale)),
-	 milliinches(dim.y/(2.0*scale)));
+  switch (lt.type) {
+  case line_type::solid:
+  case line_type::invisible:
+    printf("    \\special{%s %d %d %d %d 0 6.28319}%%\n",
+	   (lt.type == line_type::invisible ? "ia" : "ar"),
+	   milliinches(c.x),
+	   milliinches(c.y),
+	   milliinches(dim.x/(2.0*scale)),
+	   milliinches(dim.y/(2.0*scale)));
+    break;
+  case line_type::dashed:
+    dashed_ellipse(cent, dim / scale, lt);
+    break;
+  case line_type::dotted:
+    dotted_ellipse(cent, dim / scale, lt);
+    break;
+  default:
+    assert(0);
+  }
 }
 
 void tex_output::command(const char *s, const char *, int)
diff --git a/src/preproc/pic/troff.cpp b/src/preproc/pic/troff.cpp
index cf8f5eee..ddda45db 100644
--- a/src/preproc/pic/troff.cpp
+++ b/src/preproc/pic/troff.cpp
@@ -197,7 +197,11 @@ void simple_output::ellipse(const position &cent, const distance &dim,
   case line_type::invisible:
     break;
   case line_type::dotted:
+    dotted_ellipse(cent, dim, lt);
+    break;
   case line_type::dashed:
+    dashed_ellipse(cent, dim, lt);
+    break;
   case line_type::solid:
     simple_ellipse(0, cent, dim);
     break;