remove prototype pathops code

experimental/Intersection/NearestPoint.cpp

Index: experimental/Intersection/NearestPoint.cpp
diff --git a/experimental/Intersection/NearestPoint.cpp b/experimental/Intersection/NearestPoint.cpp
deleted file mode 100644
index 2b3c11d20a95099d3e143d082121fdb3b6d3441e..0000000000000000000000000000000000000000
--- a/experimental/Intersection/NearestPoint.cpp
+++ /dev/null
@@ -1,473 +0,0 @@
-/*
-Solving the Nearest Point-on-Curve Problem
-and
-A Bezier Curve-Based Root-Finder
-by Philip J. Schneider
-from "Graphics Gems", Academic Press, 1990
-*/
-
- /*    point_on_curve.c    */
-
-#include <stdio.h>
-#include <malloc.h>
-#include <math.h>
-#include "GraphicsGems.h"
-
-#define TESTMODE
-
-/*
- *  Forward declarations
- */
-Point2  NearestPointOnCurve();
-static    int    FindRoots();
-static    Point2    *ConvertToBezierForm();
-static    double    ComputeXIntercept();
-static    int    ControlPolygonFlatEnough();
-static    int    CrossingCount();
-static    Point2    Bezier();
-static    Vector2    V2ScaleII();
-
-int        MAXDEPTH = 64;    /*  Maximum depth for recursion */
-
-#define    EPSILON    (ldexp(1.0,-MAXDEPTH-1)) /*Flatness control value */
-#define    DEGREE    3            /*  Cubic Bezier curve        */
-#define    W_DEGREE 5            /*  Degree of eqn to find roots of */
-
-#ifdef TESTMODE
-/*
- *  main :
- *    Given a cubic Bezier curve (i.e., its control points), and some
- *    arbitrary point in the plane, find the point on the curve
- *    closest to that arbitrary point.
- */
-main()
-{
-
- static Point2 bezCurve[4] = {    /*  A cubic Bezier curve    */
-    { 0.0, 0.0 },
-    { 1.0, 2.0 },
-    { 3.0, 3.0 },
-    { 4.0, 2.0 },
-    };
-    static Point2 arbPoint = { 3.5, 2.0 }; /*Some arbitrary point*/
-    Point2    pointOnCurve;         /*  Nearest point on the curve */
-
-    /*  Find the closest point */
-    pointOnCurve = NearestPointOnCurve(arbPoint, bezCurve);
-    printf("pointOnCurve : (%4.4f, %4.4f)\n", pointOnCurve.x,
-        pointOnCurve.y);
-}
-#endif /* TESTMODE */
-
-
-/*
- *  NearestPointOnCurve :
- *      Compute the parameter value of the point on a Bezier
- *        curve segment closest to some arbtitrary, user-input point.
- *        Return the point on the curve at that parameter value.
- *
- */
-Point2 NearestPointOnCurve(P, V)
-    Point2     P;            /* The user-supplied point      */
-    Point2     *V;            /* Control points of cubic Bezier */
-{
-    Point2    *w;            /* Ctl pts for 5th-degree eqn    */
-    double     t_candidate[W_DEGREE];    /* Possible roots        */
-    int     n_solutions;        /* Number of roots found    */
-    double    t;            /* Parameter value of closest pt*/
-
-    /*  Convert problem to 5th-degree Bezier form    */
-    w = ConvertToBezierForm(P, V);
-
-    /* Find all possible roots of 5th-degree equation */
-    n_solutions = FindRoots(w, W_DEGREE, t_candidate, 0);
-    free((char *)w);
-
-    /* Compare distances of P to all candidates, and to t=0, and t=1 */
-    {
-        double     dist, new_dist;
-        Point2     p;
-        Vector2  v;
-        int        i;
-
-
-    /* Check distance to beginning of curve, where t = 0    */
-        dist = V2SquaredLength(V2Sub(&P, &V[0], &v));
-            t = 0.0;
-
-    /* Find distances for candidate points    */
-        for (i = 0; i < n_solutions; i++) {
-            p = Bezier(V, DEGREE, t_candidate[i],
-            (Point2 *)NULL, (Point2 *)NULL);
-            new_dist = V2SquaredLength(V2Sub(&P, &p, &v));
-            if (new_dist < dist) {
-                    dist = new_dist;
-                    t = t_candidate[i];
-            }
-        }
-
-    /* Finally, look at distance to end point, where t = 1.0 */
-        new_dist = V2SquaredLength(V2Sub(&P, &V[DEGREE], &v));
-            if (new_dist < dist) {
-                dist = new_dist;
-            t = 1.0;
-        }
-    }
-
-    /*  Return the point on the curve at parameter value t */
-    printf("t : %4.12f\n", t);
-    return (Bezier(V, DEGREE, t, (Point2 *)NULL, (Point2 *)NULL));
-}
-
-
-/*
- *  ConvertToBezierForm :
- *        Given a point and a Bezier curve, generate a 5th-degree
- *        Bezier-format equation whose solution finds the point on the
- *      curve nearest the user-defined point.
- */
-static Point2 *ConvertToBezierForm(P, V)
-    Point2     P;            /* The point to find t for    */
-    Point2     *V;            /* The control points        */
-{
-    int     i, j, k, m, n, ub, lb;
-    int     row, column;        /* Table indices        */
-    Vector2     c[DEGREE+1];        /* V(i)'s - P            */
-    Vector2     d[DEGREE];        /* V(i+1) - V(i)        */
-    Point2     *w;            /* Ctl pts of 5th-degree curve  */
-    double     cdTable[3][4];        /* Dot product of c, d        */
-    static double z[3][4] = {    /* Precomputed "z" for cubics    */
-    {1.0, 0.6, 0.3, 0.1},
-    {0.4, 0.6, 0.6, 0.4},
-    {0.1, 0.3, 0.6, 1.0},
-    };
-
-
-    /*Determine the c's -- these are vectors created by subtracting*/
-    /* point P from each of the control points                */
-    for (i = 0; i <= DEGREE; i++) {
-        V2Sub(&V[i], &P, &c[i]);
-    }
-    /* Determine the d's -- these are vectors created by subtracting*/
-    /* each control point from the next                    */
-    for (i = 0; i <= DEGREE - 1; i++) {
-        d[i] = V2ScaleII(V2Sub(&V[i+1], &V[i], &d[i]), 3.0);
-    }
-
-    /* Create the c,d table -- this is a table of dot products of the */
-    /* c's and d's                            */
-    for (row = 0; row <= DEGREE - 1; row++) {
-        for (column = 0; column <= DEGREE; column++) {
-            cdTable[row][column] = V2Dot(&d[row], &c[column]);
-        }
-    }
-
-    /* Now, apply the z's to the dot products, on the skew diagonal*/
-    /* Also, set up the x-values, making these "points"        */
-    w = (Point2 *)malloc((unsigned)(W_DEGREE+1) * sizeof(Point2));
-    for (i = 0; i <= W_DEGREE; i++) {
-        w[i].y = 0.0;
-        w[i].x = (double)(i) / W_DEGREE;
-    }
-
-    n = DEGREE;
-    m = DEGREE-1;
-    for (k = 0; k <= n + m; k++) {
-        lb = MAX(0, k - m);
-        ub = MIN(k, n);
-        for (i = lb; i <= ub; i++) {
-            j = k - i;
-            w[i+j].y += cdTable[j][i] * z[j][i];
-        }
-    }
-
-    return (w);
-}
-
-
-/*
- *  FindRoots :
- *    Given a 5th-degree equation in Bernstein-Bezier form, find
- *    all of the roots in the interval [0, 1].  Return the number
- *    of roots found.
- */
-static int FindRoots(w, degree, t, depth)
-    Point2     *w;            /* The control points        */
-    int     degree;        /* The degree of the polynomial    */
-    double     *t;            /* RETURN candidate t-values    */
-    int     depth;        /* The depth of the recursion    */
-{
-    int     i;
-    Point2     Left[W_DEGREE+1],    /* New left and right         */
-              Right[W_DEGREE+1];    /* control polygons        */
-    int     left_count,        /* Solution count from        */
-        right_count;        /* children            */
-    double     left_t[W_DEGREE+1],    /* Solutions from kids        */
-               right_t[W_DEGREE+1];
-
-    switch (CrossingCount(w, degree)) {
-           case 0 : {    /* No solutions here    */
-         return 0;
-    }
-    case 1 : {    /* Unique solution    */
-        /* Stop recursion when the tree is deep enough    */
-        /* if deep enough, return 1 solution at midpoint     */
-        if (depth >= MAXDEPTH) {
-            t[0] = (w[0].x + w[W_DEGREE].x) / 2.0;
-            return 1;
-        }
-        if (ControlPolygonFlatEnough(w, degree)) {
-            t[0] = ComputeXIntercept(w, degree);
-            return 1;
-        }
-        break;
-    }
-}
-
-    /* Otherwise, solve recursively after    */
-    /* subdividing control polygon        */
-    Bezier(w, degree, 0.5, Left, Right);
-    left_count  = FindRoots(Left,  degree, left_t, depth+1);
-    right_count = FindRoots(Right, degree, right_t, depth+1);
-
-
-    /* Gather solutions together    */
-    for (i = 0; i < left_count; i++) {
-        t[i] = left_t[i];
-    }
-    for (i = 0; i < right_count; i++) {
-         t[i+left_count] = right_t[i];
-    }
-
-    /* Send back total number of solutions    */
-    return (left_count+right_count);
-}
-
-
-/*
- * CrossingCount :
- *    Count the number of times a Bezier control polygon
- *    crosses the 0-axis. This number is >= the number of roots.
- *
- */
-static int CrossingCount(V, degree)
-    Point2    *V;            /*  Control pts of Bezier curve    */
-    int        degree;            /*  Degreee of Bezier curve     */
-{
-    int     i;
-    int     n_crossings = 0;    /*  Number of zero-crossings    */
-    int        sign, old_sign;        /*  Sign of coefficients    */
-
-    sign = old_sign = SGN(V[0].y);
-    for (i = 1; i <= degree; i++) {
-        sign = SGN(V[i].y);
-        if (sign != old_sign) n_crossings++;
-        old_sign = sign;
-    }
-    return n_crossings;
-}
-
-
-
-/*
- *  ControlPolygonFlatEnough :
- *    Check if the control polygon of a Bezier curve is flat enough
- *    for recursive subdivision to bottom out.
- *
- */
-static int ControlPolygonFlatEnough(V, degree)
-    Point2    *V;        /* Control points    */
-    int     degree;        /* Degree of polynomial    */
-{
-    int     i;            /* Index variable        */
-    double     *distance;        /* Distances from pts to line    */
-    double     max_distance_above;    /* maximum of these        */
-    double     max_distance_below;
-    double     error;            /* Precision of root        */
-    double     intercept_1,
-               intercept_2,
-               left_intercept,
-               right_intercept;
-    double     a, b, c;        /* Coefficients of implicit    */
-                        /* eqn for line from V[0]-V[deg]*/
-
-    /* Find the  perpendicular distance        */
-    /* from each interior control point to     */
-    /* line connecting V[0] and V[degree]    */
-    distance = (double *)malloc((unsigned)(degree + 1) *                     sizeof(double));
-    {
-    double    abSquared;
-
-    /* Derive the implicit equation for line connecting first *'
-    /*  and last control points */
-    a = V[0].y - V[degree].y;
-    b = V[degree].x - V[0].x;
-    c = V[0].x * V[degree].y - V[degree].x * V[0].y;
-
-    abSquared = (a * a) + (b * b);
-
-        for (i = 1; i < degree; i++) {
-        /* Compute distance from each of the points to that line    */
-            distance[i] = a * V[i].x + b * V[i].y + c;
-            if (distance[i] > 0.0) {
-                distance[i] = (distance[i] * distance[i]) / abSquared;
-            }
-            if (distance[i] < 0.0) {
-                distance[i] = -((distance[i] * distance[i]) /                         abSquared);
-            }
-        }
-    }
-
-
-    /* Find the largest distance    */
-    max_distance_above = 0.0;
-    max_distance_below = 0.0;
-    for (i = 1; i < degree; i++) {
-        if (distance[i] < 0.0) {
-            max_distance_below = MIN(max_distance_below, distance[i]);
-        };
-        if (distance[i] > 0.0) {
-            max_distance_above = MAX(max_distance_above, distance[i]);
-        }
-    }
-    free((char *)distance);
-
-    {
-    double    det, dInv;
-    double    a1, b1, c1, a2, b2, c2;
-
-    /*  Implicit equation for zero line */
-    a1 = 0.0;
-    b1 = 1.0;
-    c1 = 0.0;
-
-    /*  Implicit equation for "above" line */
-    a2 = a;
-    b2 = b;
-    c2 = c + max_distance_above;
-
-    det = a1 * b2 - a2 * b1;
-    dInv = 1.0/det;
-
-    intercept_1 = (b1 * c2 - b2 * c1) * dInv;
-
-    /*  Implicit equation for "below" line */
-    a2 = a;
-    b2 = b;
-    c2 = c + max_distance_below;
-
-    det = a1 * b2 - a2 * b1;
-    dInv = 1.0/det;
-
-    intercept_2 = (b1 * c2 - b2 * c1) * dInv;
-    }
-
-    /* Compute intercepts of bounding box    */
-    left_intercept = MIN(intercept_1, intercept_2);
-    right_intercept = MAX(intercept_1, intercept_2);
-
-    error = 0.5 * (right_intercept-left_intercept);
-    if (error < EPSILON) {
-        return 1;
-    }
-    else {
-        return 0;
-    }
-}
-
-
-
-/*
- *  ComputeXIntercept :
- *    Compute intersection of chord from first control point to last
- *      with 0-axis.
- *
- */
-/* NOTE: "T" and "Y" do not have to be computed, and there are many useless
- * operations in the following (e.g. "0.0 - 0.0").
- */
-static double ComputeXIntercept(V, degree)
-    Point2     *V;            /*  Control points    */
-    int        degree;         /*  Degree of curve    */
-{
-    double    XLK, YLK, XNM, YNM, XMK, YMK;
-    double    det, detInv;
-    double    S, T;
-    double    X, Y;
-
-    XLK = 1.0 - 0.0;
-    YLK = 0.0 - 0.0;
-    XNM = V[degree].x - V[0].x;
-    YNM = V[degree].y - V[0].y;
-    XMK = V[0].x - 0.0;
-    YMK = V[0].y - 0.0;
-
-    det = XNM*YLK - YNM*XLK;
-    detInv = 1.0/det;
-
-    S = (XNM*YMK - YNM*XMK) * detInv;
-/*  T = (XLK*YMK - YLK*XMK) * detInv; */
-
-    X = 0.0 + XLK * S;
-/*  Y = 0.0 + YLK * S; */
-
-    return X;
-}
-
-
-/*
- *  Bezier :
- *    Evaluate a Bezier curve at a particular parameter value
- *      Fill in control points for resulting sub-curves if "Left" and
- *    "Right" are non-null.
- *
- */
-static Point2 Bezier(V, degree, t, Left, Right)
-    int     degree;        /* Degree of bezier curve    */
-    Point2     *V;            /* Control pts            */
-    double     t;            /* Parameter value        */
-    Point2     *Left;        /* RETURN left half ctl pts    */
-    Point2     *Right;        /* RETURN right half ctl pts    */
-{
-    int     i, j;        /* Index variables    */
-    Point2     Vtemp[W_DEGREE+1][W_DEGREE+1];
-
-
-    /* Copy control points    */
-    for (j =0; j <= degree; j++) {
-        Vtemp[0][j] = V[j];
-    }
-
-    /* Triangle computation    */
-    for (i = 1; i <= degree; i++) {
-        for (j =0 ; j <= degree - i; j++) {
-            Vtemp[i][j].x =
-                  (1.0 - t) * Vtemp[i-1][j].x + t * Vtemp[i-1][j+1].x;
-            Vtemp[i][j].y =
-                  (1.0 - t) * Vtemp[i-1][j].y + t * Vtemp[i-1][j+1].y;
-        }
-    }
-
-    if (Left != NULL) {
-        for (j = 0; j <= degree; j++) {
-            Left[j]  = Vtemp[j][0];
-        }
-    }
-    if (Right != NULL) {
-        for (j = 0; j <= degree; j++) {
-            Right[j] = Vtemp[degree-j][j];
-        }
-    }
-
-    return (Vtemp[degree][0]);
-}
-
-static Vector2 V2ScaleII(v, s)
-    Vector2    *v;
-    double    s;
-{
-    Vector2 result;
-
-    result.x = v->x * s; result.y = v->y * s;
-    return (result);
-}