3

我正在尝试实现一种称为贝塞尔剪裁的曲线相交算法，该算法在本文末尾的一节中进行了描述（尽管本文称其为“粗线剪裁”）。我一直在阅读示例的文章和源代码（可在此处获得）。

注意：其他来源包括本文。如果我能找到它们，将发布更多内容。

该算法的核心部分是计算曲线 1 和曲线 2 的“基线”（曲线 2 的一个端点到另一个端点的线）之间的“距离函数”。所以我有一些东西可以比较我的结果，我使用了第一个示例源代码中的曲线。我设法从示例中复制了距离函数的形状，但函数的距离位置已关闭。在尝试另一条曲线时，距离函数与其他两条曲线相去甚远，尽管两条曲线明显相交。我可能对这个算法的工作很天真，但我认为这会导致没有检测到交叉点。

据我了解（这很可能是错误的），定义距离函数的过程涉及以x a + y b + c = 0的形式表示曲线 2 的基线，其中a 2 + b 2 = 1。系数是通过以y = u x + v的形式重新排列线的项来获得的，其中u等于斜率，x 和 y 是基线上的任意点。可以重新排列公式以给出v：v = y - u x。再次重新排列公式，我们得到-u*x + 1*y - v = 0，其中a = -u，b = 1，并且c = -v。为了确保条件a 2 + b 2 = 1，系数除以Math.sqrt(u u + 1)的标量。然后将线的这种表示代入另一条曲线的函数（与基线无关的曲线）以获得距离函数。此距离函数表示为贝塞尔曲线，其中y i = a P i x + b*P i y + c和x i = (1 - t) x1 + t x2，其中t等于0、1/3、2 /3和3米x1x2是基线的端点，P i是曲线 1 的控制点。

下面是与计算距离函数有关的示例程序（用语言处理编写）的一些源代码，奇怪的是，它使用与上述段落略有不同的方法来计算基线的替代表示。

/**
 * 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's 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's 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 的端点是水平的，导致基线的斜率为零。

对于曲线 1 的输入 (485, 430, 580, 60, 430, 115, 530, 160) 和曲线 2 的 (575, 25, 455, 60, 541, 140, 486, 210)（请记住，这些值以curve1的端点之间的负角旋转），结果如下图（距离函数是在距离处相对平滑的曲线）：

在此处输入图像描述

我真的不确定我做错了什么。y 值似乎以正确的模式排列，但与它所基于的两条曲线相距甚远。我意识到有可能我有可能沿着曲线而不是基线以间隔排列 x 值，但是 y 值是我真正感到困惑的。如果有人可以看看这个并解释我做错了什么，我会非常感激。感谢您花时间阅读这个相当冗长的问题。如果需要更多细节，请随时在评论中告诉我。

更新：我已经测试了我计算的线的表示。a x + b y + c = 0 表示显然仍然代表同一行，因为我仍然可以插入 x1 并获得 y1。此外，对于插入函数的任意两个坐标对，f(x, y) = 0 成立。此外，我发现文章中描述的表示和源代码中实际使用的表示可以互换地表示同一行。从这一切来看，我可以假设问题不在于计算线。额外的兴趣点

4

1 回答 1

1

您的距离函数不一定在您的两条原始曲线附近：它使用完全不同的坐标系，即 t vs D，而不是使用 x 和 y 的原始曲线。[编辑] 即 t 仅上升到 1.0，并测量沿曲线的总长度的比率，D 测量曲线 2 与曲线 1 基线的距离。

此外，当您说“curve1 和curve2 的“基线”之间的“距离函数””时，我认为您在这里混淆了curve1 和curve2，就像在您的代码中一样，您显然使用的是curve1 的基线。

该算法还假设“每条贝塞尔曲线都完全包含在连接所有起点/控制/终点的多边形中，称为其“凸包””，在您的情况下，[编辑]curve1是一个三角形，其中控制第二个起始值的点不是顶点。我不确定这如何影响算法。

否则，看起来您的距离计算很好（尽管您确实可以稍微优化一下:)）。

于 2012-05-18T05:51:14.063 回答