From 8e39d5bd6f4e40a4425ad4d984714dcd5215070a Mon Sep 17 00:00:00 2001 From: lecoanet Date: Wed, 26 Jan 2000 13:35:20 +0000 Subject: 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. --- generic/Geo.c | 348 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 339 insertions(+), 9 deletions(-) (limited to 'generic/Geo.c') 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, ¢er_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. -- cgit v1.1