aboutsummaryrefslogtreecommitdiff
path: root/generic/Geo.c
diff options
context:
space:
mode:
Diffstat (limited to 'generic/Geo.c')
-rw-r--r--generic/Geo.c348
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.
generated by cgit v1.1 at 2024-11-08 06:31:19 +0000