** Date Started: 1984
**
** OVERVIEW
-** Routines to clip lines against objects
-** All routines get the endpoints of the line, and
-** the SNARK size of the object (u,v)
+** Routines to clip lines against objects
+** All routines get the endpoints of the line, and
+** the SNARK size of the object (u,v)
**
** This is part of the CTSim program
-** Copyright (C) 1983-2000 Kevin Rosenberg
+** Copyright (c) 1983-2001 Kevin Rosenberg
**
-** $Id: clip.cpp,v 1.2 2000/06/19 19:04:05 kevin Exp $
+** $Id$
**
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License (version 2) as
/* NAME
- * clip_segment Clip against a segment of a circle
+ * clip_segment Clip against a segment of a circle
*
* SYNOPSIS
* clip_segment (x1, y1, x2, y2, u, v)
- * double& x1,*y1,*x2,*y2 Endpoints of line
- * double u,v Dimensions of segment
+ * double& x1,*y1,*x2,*y2 Endpoints of line
+ * double u,v Dimensions of segment
*/
-int
+bool
clip_segment (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
{
double xc1 = x1 * u;
double xc2 = x2 * u;
double yc2 = y2 * v;
- if (yc1 > 0. && yc2 > 0.) // reject lines above y-axis
+ if (yc1 > 0. && yc2 > 0.) // reject lines above y-axis
return false;
double radius = sqrt (u * u + v * v);
if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
return false;
- if (yc1 > 0. && yc2 > 0.) // trivial reject above y-axis
+ if (yc1 > 0. && yc2 > 0.) // trivial reject above y-axis
return false;
- // clip above x-axis
+ // clip above x-axis
if (yc1 > 0.) {
xc1 = xc1 + (xc2-xc1)*(0.0-yc1)/(yc2-yc1);
yc1 = 0.0;
/* NAME
- * clip_sector Clip a line against a sector of a circle
+ * clip_sector Clip a line against a sector of a circle
*
* SYNOPSIS
* clip_sector (x1, y1, x2, y2, u, v)
- * double& x1,*y1,*x2,*y2 Endpoints of line
- * double u,v Size of sector
+ * double& x1,*y1,*x2,*y2 Endpoints of line
+ * double u,v Size of sector
*/
-int
+bool
clip_sector (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
{
double xc1 = x1 * u;
double yc1 = y1 * v;
double xc2 = x2 * u;
double yc2 = y2 * v;
-
+
double radius = sqrt (u * u + v * v);
if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
if (clip_triangle (xc1, yc1, xc2, yc2, u, v, false) == false)
return false;
-
+
x1 = xc1 / u;
y1 = yc1 / v;
x2 = xc2 / u;
y2 = yc2 / v;
-
+
return true;
}
/* NAME
- * clip_circle Clip a line against a circle
+ * clip_circle Clip a line against a circle
*
* SYNOPSIS
* clip_circle (x1,y1,x2,y2,cx,cy,radius,t1,t2)
- * double& x1,*y1,*x2,*y2 Endpoints of line to be clipped
- * double cx,cy Center of circle
- * double radius Radius of circle
- * double t1,t2 Starting & stopping angles of clipping
+ * double& x1,*y1,*x2,*y2 Endpoints of line to be clipped
+ * double cx,cy Center of circle
+ * double radius Radius of circle
+ * double t1,t2 Starting & stopping angles of clipping
*/
-int
+bool
clip_circle (double& x1, double& y1, double& x2, double& y2, const double cx, const double cy, const double radius, double t1, double t2)
{
double xc1 = x1;
double ccx = cx;
double ccy = cy;
- double xtrans = -xc1; // move (x1,y1) to origin
+ double xtrans = -xc1; // move (x1,y1) to origin
double ytrans = -yc1;
xc1 += xtrans;
ccx += xtrans;
ccy += ytrans;
- double theta = -atan2 (yc2, xc2); // rotate line to lie on x-axis
+ double theta = -atan2 (yc2, xc2); // rotate line to lie on x-axis
GRFMTX_2D rotmtx;
- rot_mtx2 (rotmtx, theta); // xc1,yc1 is at origin, no need to rot
+ rot_mtx2 (rotmtx, theta); // xc1,yc1 is at origin, no need to rot
xform_mtx2 (rotmtx, xc2, yc2);
xform_mtx2 (rotmtx, ccx, ccy);
- t1 += theta; // rotate start and stop angles
+ t1 += theta; // rotate start and stop angles
t2 += theta;
- t1 = norm_ang (t1);
- t2 = norm_ang (t2);
+ t1 = normalizeAngle (t1);
+ t2 = normalizeAngle (t2);
if (xc2 < -D_EPSILON || fabs(yc2) > F_EPSILON) {
sys_error (ERR_SEVERE, "Internal error in clip_circle\n x1=%6.2f, y1=%6.2f, x2=%6.2f, y2=%6.2f, xc2=%6.2f, yc2=%6.2f, theta=%6.2f", x1, y1, x2, y2, xc2, yc2, theta);
return false;
}
- if (fabs(ccy) > radius) /* check if can reject */
+ if (fabs(ccy) > radius) /* check if can reject */
return false;
-
+
double temp = sqrt (radius * radius - ccy * ccy);
double xcmin = ccx - temp;
double xcmax = ccx + temp;
-
+
if (fabs(t2 - t1) < D_EPSILON) {
if (xc1 < xcmin)
xc1 = xcmin;
} else if (t1 < t2) {
if (t1 < PI && t2 > PI)
if (xc1 < xcmin)
- xc1 = xcmin;
+ xc1 = xcmin;
} else if (t1 > t2) {
if (t1 < PI)
if (xc1 < xcmin)
- xc1 = xcmin;
+ xc1 = xcmin;
if (xc2 > xcmax)
xc2 = xcmax;
}
/* NAME
- * clip_triangle Clip a line against a triangle
+ * clip_triangle Clip a line against a triangle
*
* SYNOPSIS
* clip_triangle (x1, y1, x2, y2, u, v, clip_xaxis)
- * double& x1, *y1, *x2, *y2 Endpoints of line
- * double u, v Size of 1/2 base len & height
- * int clip_xaxis Boolean flag whether to clip against x axis
- * (Use true for all triangles)
- * (false if used internally by sector clipping routine)
+ * double& x1, *y1, *x2, *y2 Endpoints of line
+ * double u, v Size of 1/2 base len & height
+ * int clip_xaxis Boolean flag whether to clip against x axis
+ * (Use true for all triangles)
+ * (false if used internally by sector clipping routine)
*
* DESCRIPTION
- * x
- * /|\ Note that vertices of triangle are
- * / | \ (-u, 0)
- * / | \ (u, 0)
- * / | \ (0, v)
+ * x
+ * /|\ Note that vertices of triangle are
+ * / | \ (-u, 0)
+ * / | \ (u, 0)
+ * / | \ (0, v)
* / | v \
* / | \
* +------+------+
* 1) Inside of this routine, values of (u,v) are assumed to be (1,1)
*
* 2) Derivation of clipping equations:
- * Using parametric equations for the line
- * xv = x1 + t * (x2 - x1)
+ * Using parametric equations for the line
+ * xv = x1 + t * (x2 - x1)
* yv = y1 + t * (y2 - y1)
- * so,
+ * so,
* t = (xv - x1) / (x2 - x1)
* yv = y1 + (xv - x1) * (y2 - y1) / (x2 - x1)
* yv = y1 + (xv - x1) * dy / dx
*
- * Now, find the intersections with the following clipping boundries:
- * yv = v - (v/u) * xv (yv = mx + b)
- * yv = v + (v/u) * xv (m = v/u, b = v);
+ * Now, find the intersections with the following clipping boundries:
+ * yv = v - (v/u) * xv (yv = mx + b)
+ * yv = v + (v/u) * xv (m = v/u, b = v);
*/
static int tcode (const double x, const double y, const double m, const double b, const int clip_xaxis);
-int
+bool
clip_triangle (double& x1, double& y1, double& x2, double& y2, const double u, const double v, const int clip_xaxis)
{
- double m = v / u; // slope of triangle lines
- double b = v; // y-intercept of triangle lines
+ double m = v / u; // slope of triangle lines
+ double b = v; // y-intercept of triangle lines
int c1 = tcode (x1, y1, m, b, clip_xaxis);
int c2 = tcode (x2, y2, m, b, clip_xaxis);
-#ifdef DEBUG
- crt_set_cpos (1,1);
- printf ("x1:%6.2f y1:%6.2f code1:%2d x2:%6.2f y2:%6.2f code2:%2d",
- x1, y1, c1, x2, y2, c2);
+#if 0
+ printf ("x1:%6.2f y1:%6.2f code1:%2d x2:%6.2f y2:%6.2f code2:%2d\n", x1, y1, c1, x2, y2, c2);
#endif
while ( c1 || c2 ) {
if ( c1 & c2 ) {
- return false; // trivial reject
+ return false; // trivial reject
}
int c = c1;
if (c1 == 0)
c = c2;
double x = 0, y = 0;
- if (c & 1) { // below
+ if (c & 1) { // below
x = x1 + (x2-x1)*(0.0-y1)/(y2-y1);
y = 0.0;
- } else if (c & 2) { // right
+ } else if (c & 2) { // right
double dx, dy;
dx = x2 - x1;
dy = y2 - y1;
if (fabs(dx) > D_EPSILON)
- x = (-y1 + b + x1 * dy/dx) / (m + dy/dx);
+ x = (-y1 + b + x1 * dy/dx) / (m + dy/dx);
else
- x = x1;
+ x = x1;
y = -m * x + b;
- } else if (c & 4) { /* left */
+ } else if (c & 4) { /* left */
double dx, dy;
dx = x2 - x1;
dy = y2 - y1;
if (fabs(dx) > D_EPSILON) {
- x = (y1 - b - x1 * dy/dx);
- x /= (m - dy/dx);
+ x = (y1 - b - x1 * dy/dx);
+ x /= (m - dy/dx);
} else
- x = x1;
+ x = x1;
y = m * x + b;
}
-
+
if (c == c1) {
x1=x; y1=y; c1=tcode (x1,y1,m,b,clip_xaxis);
} else {
x2=x; y2=y; c2=tcode (x2,y2,m,b,clip_xaxis);
}
-#ifdef DEBUG
- crt_set_cpos (1,1);
- printf ("x1:%6.2f y1:%6.2f code1:%2d x2:%6.2f y2:%6.2f code2:%2d", x1, y1, c1, x2, y2, c2);
+#if 0
+ printf ("x1:%6.2f y1:%6.2f code1:%2d x2:%6.2f y2:%6.2f code2:%2d\n", x1, y1, c1, x2, y2, c2);
#endif
}
- return true; /* we have clipped the line, and it is good */
+ return true; /* we have clipped the line, and it is good */
}
/* compute region code */
-static int
+static int
tcode (const double x, const double y, const double m, const double b, const int clip_xaxis)
{
int c = 0;
- if (clip_xaxis && y < 0.) // below triange
+ if (clip_xaxis && y < 0.) // below triange
c = 1;
- if (y > -m * x + b + D_EPSILON) // right of triangle
+ if (y > -m * x + b + D_EPSILON) // right of triangle
c += 2;
- if (y > m * x + b + D_EPSILON) // left of triangle
+ if (y > m * x + b + D_EPSILON) // left of triangle
c += 4;
-
+
return (c);
-}
+}
/* NAME
- * clip_rect Clip a line against a rectangle
+ * clip_rect Clip a line against a rectangle
*
* SYNOPSIS
* clip_rect (x1, y1, x2, y2, rect)
- * double& x1, *y1, *x2, *y2 Endpoints of line
- * double rect[4] Rectangle to clip against
- * ordered xmin, ymin, xmax, ymax
+ * double& x1, *y1, *x2, *y2 Endpoints of line
+ * double rect[4] Rectangle to clip against
+ * ordered xmin, ymin, xmax, ymax
*/
static int rectcode (double x, double y, const double rect[4]);
-int
+bool
clip_rect (double& x1, double& y1, double& x2, double& y2, const double rect[4])
{
double x = 0, y = 0;
while (c1 || c2) {
if (c1 & c2)
- return false; // trivial reject
+ return false; // trivial reject
int c = c1;
if (c1 == 0)
c = c2;
- if (c & 1) { // left
+ if (c & 1) { // left
y = y1 + (y2-y1)*(rect[0]-x1)/(x2-x1);
x = rect[0];
- } else if (c & 2) { // right
+ } else if (c & 2) { // right
y = y1 + (y2-y1)*(rect[2]-x1)/(x2-x1);
x = rect[2];
- } else if (c & 4) { // bottom
+ } else if (c & 4) { // bottom
x = x1 + (x2-x1)*(rect[1]-y1)/(y2-y1);
y = rect[1];
- } else if (c & 8) { // top
+ } else if (c & 8) { // top
x = x1 + (x2-x1)*(rect[3]-y1)/(y2-y1);
y = rect[3];
}
-
+
if (c == c1) {
x1=x; y1=y; c1=rectcode(x1,y1,rect);
} else {
x2=x; y2=y; c2=rectcode(x2,y2,rect);
}
}
- return true; // we have clipped the line, and it is good
+ return true; // we have clipped the line, and it is good
}
/* NAME
- * rectcode INTERNAL routine to return position of
- * point relative to a rectangle
+ * rectcode INTERNAL routine to return position of
+ * point relative to a rectangle
*
* SYNOPSIS
* c = rectcode (x, y, rect)
- * int c Position of point relative to the window
- * double x, y Point to test against window
- * double rect[4] Coordinates of rectangle extent
- * Ordered [xmin, ymin, xmax, ymax]
+ * int c Position of point relative to the window
+ * double x, y Point to test against window
+ * double rect[4] Coordinates of rectangle extent
+ * Ordered [xmin, ymin, xmax, ymax]
*/
-static int
-rectcode (double x, double y, const double rect[4])
+static int
+rectcode (double x, double y, const double rect[4])
{
int c = 0;
else if (y > rect[3])
c += 8;
return (c);
-}
+}