The problem of calculating the distance function in the bezier compartment

I am trying to implement a curve interception algorithm known as bezier clipping, which is described in the section at the end of this article (although the article calls this “bold line cropping”). I read the article and the source code for the example (available here ).

Note. Additional sources include this document . More will be published if I can find them.

The central part of this algorithm computes the “distance function” between curve 1 and the “baseline” of curve 2 (which is the line from one endpoint of curve 2 to another). Therefore, I needed to compare something with my results, I used curves from the source code of the first example. I managed to reproduce the form of the distance function from the example, but the distance location of the function was disabled. When trying another curve, the distance function was nowhere near the other two curves, despite the fact that both of them clearly intersected. I might be naive for this algorithm to work, but I think that this will not lead to intersection detection.

From what I understand (which may well be wrong), the process of determining the distance function involves the expression of the baseline of curve 2 in the form xa + yb + c = 0 , where a ² + b ² = 1 . The coefficients were obtained by rearranging the line members in the form y = ux + v , where u is equal to the slope, and x and y are any points at the base level. The formula can be rearranged to give v : v = y - ux . Rearranging the formula again, we get -u * x + 1 * y - v = 0 , where a = -u , b = 1 , and c = -v . To provide condition a ²+ b ² = 1 , the coefficients are divided by the scalar Math.sqrt (uu + 1) . This line representation is then replaced with a function of another curve (one with which the baseline is not connected) to obtain a distance function. This distance function is represented as a bezier curve, with y _i= aP _ix + b * P _iy+ c and x _i= (1 - t) x1 + tx2 , where t is 0, 1/3, 2/3, and 3 m x1 and x2 are the end points of the baseline, and P _i - control points of the curve.

( ), , , , .

/**
 * Set up four points, to form a cubic curve, and a static curve that is used for intersection checks
 */
void setupPoints()
{
points = new Point[4];
points[0] = new Point(85,30);
points[1] = new Point(180,50);
points[2] = new Point(30,155);
points[3] = new Point(130,160);

curve = new Bezier3(175,25,  55,40,  140,140,  85,210);
curve.setShowControlPoints(false);
}

...

flcurve = new Bezier3(points[0].getX(), points[0].getY(),
                                        points[1].getX(), points[1].getY(),
                                        points[2].getX(), points[2].getY(),
                                        points[3].getX(), points[3].getY());

...

void drawClipping()
{
    double[] bounds = flcurve.getBoundingBox();

    // get the distances from C1 baseline to the two other lines
    Point p0 = flcurve.points[0];
    // offset distances from baseline
    double dx = p0.x - bounds[0];
    double dy = p0.y - bounds[1];
    double d1 = sqrt(dx*dx+dy*dy);
    dx = p0.x - bounds[2];
    dy = p0.y - bounds[3];
    double d2 = sqrt(dx*dx+dy*dy);

    ...

    double a, b, c;
a = dy / dx;
b = -1;
c = -(a * flcurve.points[0].x - flcurve.points[0].y);
// normalize so that a² + b² = 1
double scale = sqrt(a*a+b*b);
a /= scale; b /= scale; c /= scale;     

// set up the coefficients for the Bernstein polynomial that
// describes the distance from curve 2 to curve 1 baseline
double[] coeff = new double[4];
for(int i=0; i<4; i++) { coeff[i] = a*curve.points[i].x + b*curve.points[i].y + c; }
double[] vals = new double[4];
for(int i=0; i<4; i++) { vals[i] = computeCubicBaseValue(i*(1/3), coeff[0], coeff[1], coeff[2], coeff[3]); }

translate(0,100);

...

// draw the distance Bezier function
double range = 200;
for(float t = 0; t<1.0; t+=1.0/range) {
    double y = computeCubicBaseValue(t, coeff[0], coeff[1], coeff[2], coeff[3]);
    params.drawPoint(t*range, y, 0,0,0,255); }

...

translate(0,-100);
}

...

/**
 * compute the value for the cubic bezier function at time=t
 */
double computeCubicBaseValue(double t, double a, double b, double c, double d) {
double mt = 1-t;
return mt*mt*mt*a + 3*mt*mt*t*b + 3*mt*t*t*c + t*t*t*d; }

( javax.swing.JPanel), , :

package bezierclippingdemo2;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;

import javax.swing.JPanel;

public class ReplicateBezierClippingPanel extends JPanel {

CubicCurveExtended curve1, curve2;

public ReplicateBezierClippingPanel(CubicCurveExtended curve1, CubicCurveExtended curve2) {

    this.curve1 = curve1;
    this.curve2 = curve2;

}

public void paint(Graphics g) {

    super.paint(g);
    Graphics2D g2d = (Graphics2D) g;
    g2d.setStroke(new BasicStroke(1));
    g2d.setColor(Color.black);
    drawCurve1(g2d);
    drawCurve2(g2d);
    drawDistanceFunction(g2d);

}

public void drawCurve1(Graphics2D g2d) {

    double range = 200;

    double t = 0;

    double prevx = curve1.x1*(1 - t)*(1 - t)*(1 - t) + 3*curve1.ctrlx1*(1 - t)*(1 - t)*t + 3*curve1.ctrlx2*(1 - t)*t*t + curve1.x2*t*t*t;
    double prevy = curve1.y1*(1 - t)*(1 - t)*(1 - t) + 3*curve1.ctrly1*(1 - t)*(1 - t)*t + 3*curve1.ctrly2*(1 - t)*t*t + curve1.y2*t*t*t;

    for(t += 1.0/range; t < 1.0; t += 1.0/range) {

        double x = curve1.x1*(1 - t)*(1 - t)*(1 - t) + 3*curve1.ctrlx1*(1 - t)*(1 - t)*t + 3*curve1.ctrlx2*(1 - t)*t*t + curve1.x2*t*t*t;
        double y = curve1.y1*(1 - t)*(1 - t)*(1 - t) + 3*curve1.ctrly1*(1 - t)*(1 - t)*t + 3*curve1.ctrly2*(1 - t)*t*t + curve1.y2*t*t*t;

        g2d.draw(new LineExtended(prevx, prevy, x, y));

        prevx = x;
        prevy = y;

    }

}

public void drawCurve2(Graphics2D g2d) {

    double range = 200;

    double t = 0;

    double prevx = curve2.x1*(1 - t)*(1 - t)*(1 - t) + 3*curve2.ctrlx1*(1 - t)*(1 - t)*t + 3*curve2.ctrlx2*(1 - t)*t*t + curve2.x2*t*t*t;
    double prevy = curve2.y1*(1 - t)*(1 - t)*(1 - t) + 3*curve2.ctrly1*(1 - t)*(1 - t)*t + 3*curve2.ctrly2*(1 - t)*t*t + curve2.y2*t*t*t;

    for(t += 1.0/range; t < 1.0; t += 1.0/range) {

        double x = curve2.x1*(1 - t)*(1 - t)*(1 - t) + 3*curve2.ctrlx1*(1 - t)*(1 - t)*t + 3*curve2.ctrlx2*(1 - t)*t*t + curve2.x2*t*t*t;
        double y = curve2.y1*(1 - t)*(1 - t)*(1 - t) + 3*curve2.ctrly1*(1 - t)*(1 - t)*t + 3*curve2.ctrly2*(1 - t)*t*t + curve2.y2*t*t*t;

        g2d.draw(new LineExtended(prevx, prevy, x, y));

        prevx = x;
        prevy = y;

    }

}

public void drawDistanceFunction(Graphics2D g2d) {

    double a = (curve1.y2 - curve1.y1)/(curve1.x2 - curve1.x1);
    double b = -1;
    double c = -(a*curve1.x1 - curve1.y1);

    double scale = Math.sqrt(a*a + b*b);

    a /= scale;
    b /= scale;
    c /= scale;

    double y1 = a*curve2.x1 + b*curve2.y1 + c;
    double y2 = a*curve2.ctrlx1 + b*curve2.ctrly1 + c;
    double y3 = a*curve2.ctrlx1 + b*curve2.ctrly2 + c;
    double y4 = a*curve2.x2 + b*curve2.y2 + c;

    double range = 200;
    double t = 0;
    double prevx = t*range;
    double prevy = (1 - t)*(1 - t)*(1 - t)*y1 + 3*(1 - t)*(1 - t)*t*y2 + 3*(1 - t)*t*t*y3 + t*t*t*y4;

    for(t += 1.0/range; t < 1.0; t += 1.0/range) {

        double x = t*range;
        double y = (1 - t)*(1 - t)*(1 - t)*y1 + 3*(1 - t)*(1 - t)*t*y2 + 3*(1 - t)*t*t*y3 + t*t*t*y4;

        g2d.draw(new LineExtended(prevx, prevy, x, y));

        prevx = x;
        prevy = y;

    }
}



}

CubicCurveExtended LineExtended - java.awt.geom.CubicCurve2D.Double java.awt.geom.Line2D.Double. , , , 1 , .

(485, 430, 580, 60, 430, 115, 530, 160) 1 (575, 25, 455, 60, 541, 140, 486, 210) 2 , 1), ( ):

, . y, -, , , . , , x , , y - , . - , , . , , . , .

: , . ax + by + c = 0, -, - , x1 y1. , , , f (x, y) = 0. , , , , , . , .