Correction de bug dans PolygonInBBox.

Adaptation de PointInAngle � des angles d�crits
dans le sens des aiguilles d'une montre.
Ajout de HorizLineToArc et VertLineToArc.
Ajout de GetArcPath permettant de convertir un arc
en courbes de Bezier.

1 files changed, 339 insertions, 9 deletions

diff --git a/generic/Geo.c b/generic/Geo.c
index 203d3d4..c2d569d 100644
--- a/generic/Geo.c
+++ b/generic/Geo.c
@@ -488,8 +488,9 @@ ShiftLine(RadarPoint	*p1,
     dx = -dx;
     dx_neg = True;
   }
-  else
+  else {
     dx_neg = False;
+  }
   if (dy < 0) {
     dy = -dy;
     dy_neg = True;
@@ -878,9 +879,10 @@ PolygonInBBox(RadarPoint	*points,
   int		inside, count;
   RadarPoint	*p, *head, *first, *second;
   RadarBool	closed;
-  
+
   p = head = points;
   closed = True;
+  count = num_points-2;
   /*
    * Check to see if closed. If not adjust num_points and
    * record this.
@@ -888,16 +890,18 @@ PolygonInBBox(RadarPoint	*points,
   if ((points[0].x != points[num_points-1].x) ||
       (points[0].y != points[num_points-1].y)) {
     closed = False;
+    count = num_points-1;
   }
 
   /*
    * Get the status of the first edge.
    */
-  inside = LineInBBox(&points[0], &points[1], bbox);
+  inside = LineInBBox(&p[0], &p[1], bbox);
+  p++;
   if (inside == 0) {
     return 0;
   }
-  for (count = num_points; count > 0; p++, count--) {
+  for (; count > 0; p++, count--) {
     first = &p[0];
     /*
      * Pretend the polygon is closed if this is not the case.
@@ -924,9 +928,9 @@ PolygonInBBox(RadarPoint	*points,
     return 1;
   }
 
-  printf("PolygonInBBox, np = %d, x = %g, y = %g, dist = %g\n",
+  /*printf("PolygonInBBox, np = %d, x = %g, y = %g, dist = %g\n",
 	 num_points, bbox->orig.x, bbox->orig.y,
-	 PolygonToPointDist(points, num_points, &bbox->orig));
+	 PolygonToPointDist(points, num_points, &bbox->orig));*/
   if (PolygonToPointDist(points, num_points, &bbox->orig) <= 0.0) {
     return 0;
   }
@@ -1058,7 +1062,7 @@ PointInAngle(int	start_angle,
     point_angle = 0.0;
   }
   else {
-    point_angle = -atan2(p->y, p->x) * 180.0 / M_PI;
+    point_angle = atan2(p->y, p->x) * 180.0 / M_PI;
   }
   angle_diff = (REAL_TO_INT(point_angle) - start_angle) % 360;
   if (angle_diff < 0) {
@@ -1070,6 +1074,102 @@ PointInAngle(int	start_angle,
 
 
 /*
+ * Tell if an horizontal line intersect an axis aligned
+ * elliptical arc.
+ *
+ * Returns True if the line described by (x1, x2, y) intersects
+ * the arc described by (r1, r2, start_angle and angle_extent).
+ * This arc is origin centered.
+ */
+RadarBool
+HorizLineToArc(RadarReal	x1,
+	       RadarReal	x2,
+	       RadarReal	y,
+	       RadarReal	rx,
+	       RadarReal	ry,
+	       RadarReal	start_angle,
+	       RadarReal	angle_extent)
+{
+  RadarReal	tmp, x;
+  RadarPoint	t;
+  
+  /*
+   * Compute the x-coordinate of one possible intersection point
+   * between the arc and the line.  Use a transformed coordinate
+   * system where the oval is a unit circle centered at the origin.
+   * Then scale back to get actual x-coordinate.
+   */
+  t.y = y/ry;
+  tmp = 1 - t.y*t.y;
+  if (tmp < 0.0) {
+    return False;
+  }
+  t.x = sqrt(tmp);
+  x = t.x*rx;
+  
+  /*
+   * Test both intersection points.
+   */  
+  if ((x >= x1) && (x <= x2) && PointInAngle(start_angle, angle_extent, &t)) {
+    return True;
+  }
+  t.x = -t.x;
+  if ((-x >= x1) && (-x <= x2) && PointInAngle(start_angle, angle_extent, &t)) {
+    return True;
+  }
+  return False;
+}
+
+
+/*
+ * Tell if an vertical line intersect an axis aligned
+ * elliptical arc.
+ *
+ * Returns True if the line described by (x1, x2, y) intersects
+ * the arc described by (r1, r2, start_angle and angle_extent).
+ * This arc is origin centered.
+ */
+RadarBool
+VertLineToArc(RadarReal	x,
+	      RadarReal	y1,
+	      RadarReal	y2,
+	      RadarReal	rx,
+	      RadarReal	ry,
+	      RadarReal	start_angle,
+	      RadarReal	angle_extent)
+{
+  RadarReal	tmp, y;
+  RadarPoint	t;
+  
+  /*
+   * Compute the y-coordinate of one possible intersection point
+   * between the arc and the line.  Use a transformed coordinate
+   * system where the oval is a unit circle centered at the origin.
+   * Then scale back to get actual y-coordinate.
+   */
+  t.x = x/rx;
+  tmp = 1 - t.x*t.x;
+  if (tmp < 0.0) {
+    return False;
+  }
+  t.y = sqrt(tmp);
+  y = t.y*ry;
+
+  /*
+   * Test both intersection points.
+   */
+  if ((y > y1) && (y < y2) && PointInAngle(start_angle, angle_extent, &t)) {
+    return True;
+  }
+  t.y = -t.y;
+  if ((-y > y1) && (-y < y2) && PointInAngle(start_angle, angle_extent, &t)) {
+    return True;
+  }
+  return False;
+}
+
+
+/*
  * Return the distance of the given point to the rectangle
  * described by rect. Return negative values for points in
  * the rectangle.
@@ -1548,6 +1648,123 @@ OvalToPointDist(RadarPoint	*center,
 }
 
 
+static int bezier_basis[][4] =
+{
+    {	-1,	3,     -3,	1},
+    {	 3,    -6,	3,	0},
+    {	-3,	3,	0,	0},
+    {	 1,	0,	0,	0}
+};
+
+/*
+ **********************************************************************************
+ *
+ * Arc2Param --
+ *
+ *	Given a Bezier curve describing an arc and an angle return the parameter
+ *	value for the intersection point between the arc and the ray at angle.
+ *
+ **********************************************************************************
+ */
+#define EVAL(coeff, t) (((coeff[0]*t + coeff[1])*t + coeff[2]) * t + coeff[3])
+static RadarReal
+Arc2Param(RadarPoint	*controls,
+	  RadarReal	angle)
+{
+  RadarReal	coeff_x[4], coeff_y[4];
+  RadarReal	min_angle, min_t, max_angle, max_t, cur_angle, cur_t;
+  int		i, j, depth = 0;
+
+  /* assume angle >= 0 */
+  while (angle > M_PI) {
+    angle -= 2 * M_PI;
+  }
+
+  for (i = 0; i < 4; i++) {
+    coeff_x[i] = coeff_y[i] = 0.0;
+    for (j = 0; j < 4; j++) {
+      coeff_x[i] += bezier_basis[i][j] * controls[j].x;
+      coeff_y[i] += bezier_basis[i][j] * controls[j].y;
+    }
+  }
+
+  min_angle = atan2(controls[0].y, controls[0].x);
+  max_angle = atan2(controls[3].y, controls[3].x);
+  if (max_angle < min_angle) {
+    min_angle -= M_PI+M_PI;
+  }
+  if (angle > max_angle) {
+    angle -= M_PI+M_PI;
+  }
+
+  min_t = 0.0; max_t = 1.0;
+
+  while (depth < 15) {
+    cur_t = (max_t + min_t) / 2.0;
+    cur_angle = atan2(EVAL(coeff_y, cur_t), EVAL(coeff_x, cur_t));
+    if (angle > cur_angle) {
+      min_t = cur_t;
+      min_angle = cur_angle;
+    }
+    else {
+      max_t = cur_t;
+      max_angle = cur_angle;
+    }
+    depth += 1;
+  }
+
+  if ((max_angle-angle) < (angle-min_angle)) {
+    return max_t;
+  }
+
+  return min_t;
+}
+#undef EVAL
+
+
+/*
+ **********************************************************************************
+ *
+ * BezierSubdivide --
+ *
+ *	Subdivide a Bezier curve given by controls at parameter t. Return
+ *	in controls, the first or the last part depending on boolean first.
+ *
+ **********************************************************************************
+ */
+void
+BezierSubdivide(RadarPoint	*controls,
+		RadarReal	t,
+		RadarBool	first)
+{
+  RadarReal	s = 1.0 - t;
+  RadarPoint	r[7];
+  RadarPoint	a;
+
+  r[0] = controls[0];
+  r[6] = controls[3];
+  a.x = s*controls[1].x + t*controls[2].x;
+  a.y = s*controls[1].y + t*controls[2].y;
+  r[1].x = s*r[0].x + t*controls[1].x;
+  r[1].y = s*r[0].y + t*controls[1].y;
+  r[2].x = s*r[1].x + t*a.x;
+  r[2].y = s*r[1].y + t*a.y;
+  r[5].x = s*controls[2].x + t*r[6].x;
+  r[5].y = s*controls[2].y + t*r[6].y;
+  r[4].x = s*a.x + t*r[5].x;
+  r[4].y = s*a.y + t*r[5].y;
+  r[3].x = s*r[2].x + t*r[4].x;
+  r[3].y = s*r[2].y + t*r[4].y;
+
+  if (first) {
+    memcpy(controls, r, 4*sizeof(RadarPoint));
+  }
+  else {
+    memcpy(controls, &r[3], 4*sizeof(RadarPoint));
+  }      
+}
+
+
 /*
  **********************************************************************************
  *
@@ -1644,8 +1861,13 @@ GetBezierPath(RadarList	from_points,
   for (i = 0; i < num_fp; ) {
     if (i < (num_fp-3)) {
       GetBezierPoints(fp, to_points, 1.0);
-      fp += 3;
-      i += 3;
+      if (i < (num_fp-4)) {
+	fp += 3;
+	i += 3;
+      }
+      else {
+	break;
+      }
     }
     else if (i == (num_fp-3)) {
       s[0] = fp[0];
@@ -1664,6 +1886,114 @@ GetBezierPath(RadarList	from_points,
 /*
  **********************************************************************************
  *
+ * GetArcCurve --
+ *	Compute in to_points a set of Bezier control points describing an arc
+ *	path given the start angle, the stop angle and the type: 0 for arc,
+ *	1 for chord, 2 for pie slice.
+ *	To obtain the actual polygonal shape, the client chould use GetBezierPath
+ *	on the returned controls (after applying transform). The returned arc
+ *	is circular and centered on 0,0.
+ *
+ **********************************************************************************
+ */
+static double arc_nodes_x[4] = { 1.0, 0.0, -1.0, 0.0 };
+static double arc_nodes_y[4] = { 0.0, 1.0,  0.0, -1.0 };
+static double arc_controls_x[8] = { 1.0, 0.55197, -0.55197, -1.0, -1.0, -0.55197, 0.55197, 1.0 };
+static double arc_controls_y[8] = { 0.55197, 1.0, 1.0, 0.55197, -0.55197, -1.0, -1.0, -0.55197 };
+void
+GetArcPath(RadarReal	start_angle,
+	   RadarReal	end_angle,
+	   int		type,
+	   RadarList	to_points)
+{
+  int		start_quad, end_quad, quadrant;
+  RadarPoint	center_p = { 0.0, 0.0 };
+  RadarPoint	start_p = center_p;
+  
+  /*
+   * make sure the output vector is empty.
+   */
+  RadarListEmpty(to_points);
+  
+  /*
+   * normalize start_angle and end_angle.
+   */
+  start_angle = fmod(start_angle, 2.0*M_PI);
+  if (start_angle < 0.0) {
+    start_angle += 2.0*M_PI;
+  }
+  end_angle = fmod(end_angle, 2.0*M_PI);
+  if (end_angle < 0.0) {
+    end_angle += 2.0*M_PI;
+  }
+  if (start_angle >= end_angle) {
+    if (start_angle == end_angle) {
+      type = 3;
+    }
+    end_angle += 2.0*M_PI;
+  }
+  
+  /*
+   * Now 0 <= start_angle < 2 * M_PI and start_angle <= end_angle.
+   */
+
+  start_quad = start_angle / (M_PI / 2.0);
+  end_quad = end_angle / (M_PI / 2.0);
+
+  for (quadrant = start_quad; quadrant <= end_quad; quadrant++) {
+    RadarPoint controls[4];
+    RadarReal  t;
+    
+    controls[0].x = arc_nodes_x[quadrant % 4];
+    controls[0].y = arc_nodes_y[quadrant % 4];
+    controls[1].x = arc_controls_x[2 * (quadrant % 4)];
+    controls[1].y = arc_controls_y[2 * (quadrant % 4)];
+    controls[2].x = arc_controls_x[2 * (quadrant % 4) + 1];
+    controls[2].y = arc_controls_y[2 * (quadrant % 4) + 1];
+    controls[3].x = arc_nodes_x[(quadrant + 1) % 4];
+    controls[3].y = arc_nodes_y[(quadrant + 1) % 4];
+    
+    if (quadrant == start_quad)	{
+      t = Arc2Param(controls, start_angle);
+      BezierSubdivide(controls, t, False);
+      /*
+       * The path is still empty and we have to create the first
+       * vertex.
+       */
+      start_p = controls[0];
+      RadarListAdd(to_points, &controls[0], RadarListTail);
+    }
+    if (quadrant == end_quad) {
+      t = Arc2Param(controls, end_angle);
+      if (!t) {
+	break;
+      }
+      BezierSubdivide(controls, t, True);
+    }
+    RadarListAdd(to_points, &controls[1], RadarListTail);
+    RadarListAdd(to_points, &controls[2], RadarListTail);
+    RadarListAdd(to_points, &controls[3], RadarListTail);
+  }
+
+  if (type == 2) {
+    RadarListAdd(to_points, &center_p, RadarListTail);
+    /*
+     * Can't add this one, it would be interpreted by GetBezierPath
+     * as an off-curve control. The path should be closed by the client
+     * after expansion by GetBezierPath.
+     *
+      RadarListAdd(to_points, &start_p, RadarListTail); 
+     */
+  }
+  else if (type == 1) {
+    RadarListAdd(to_points, &start_p, RadarListTail); 
+  }
+}
+
+
+/*
+ **********************************************************************************
+ *
  * SmoothPathWithBezier --
  *	Compute in to_points a new set of points describing a smoothed path based
  *	on the path given in from_points. The algorithm use Bezier cubic curves.