我正在尝试实现一个称为bezier裁剪的曲线兴趣剖分算法,这在this article结尾的一节中有描述(尽管文章称之为“肥线裁剪”)。我一直在关注文章和示例的源代码(可用here)。
注:其他来源包括this paper。如果我能找到的话,会贴更多的。
该算法的中心部分是计算curve1和curve2的“基线”之间的“距离函数”(这是从curve2的一个端点到另一个端点的直线)。所以我要比较一下我的结果,我使用了第一个例子的源代码中的曲线。我设法从示例中复制了distance函数的形状,但函数的distance位置已关闭。在尝试另一条曲线时,尽管两条曲线明显相交,但距离函数远未接近其他两条曲线。我可能对这个算法的工作原理很幼稚,但我认为这会导致没有检测到交叉点。
根据我的理解(这很可能是错误的),定义距离函数的过程包括以xa+yb+c=0的形式表示曲线2的基线,其中a2+b2=1。这些系数是通过重新排列y=u x+v形式的直线项获得的,其中u等于斜率,x和y是基线上的任意点。公式可以重新排列,得到v:v=y-ux。重新排列公式,我们得到-u*x+1*y-v=0,其中a=-u,b=1和c=-v。为确保条件a2+b2=1,系数除以一个math.sqrt(uu+1)标量。然后将该线的表示替换为另一条曲线的函数(与基线无关的曲线)以获得距离函数。该距离函数表示为Bezier曲线,其中y= API x+b*pi y+c和x=(1 -t)x1+tx2,其中t等于0, 1/3, 2/3,3m x1和x2是基线的端点,而皮是Curv1的控制点。
下面是计算距离函数的示例程序(用语言处理编写)的一些源代码片段,奇怪的是,它使用与上一段稍有不同的方法来计算基线的替代表示。
/**
* 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)(请记住这些值是通过曲线1的端点之间的负角度旋转的),结果如下所示(距离函数是距离中看起来相对平滑的曲线):
我真的不知道我做错了什么。y值的排列方式似乎正确,但与它所基于的两条曲线相距甚远。我意识到有可能x值是沿着曲线而不是基线间隔排列的,但是y值是我真正困惑的。如果有人能看一眼并解释我做错了什么,我会非常感激的。感谢您抽出时间来阅读这个相当冗长的问题。如果需要更多的细节,请在评论中告诉我。
更新:我已经测试了我计算的行的表示。ax+by+c=0表示显然仍然代表同一行,因为我仍然可以插入x1并得到y1。另外,对于插入到函数中的任意两个坐标对,f(x,y)=0保持不变。此外,我发现本文中描述的表示和源代码中实际使用的表示可以互换地表示同一行。从所有这些,我可以假设问题不在于计算直线。另一个兴趣点
最佳答案
距离函数不一定要在两条原始曲线附近:它使用完全不同的坐标系,即T与D,而不是使用X和Y的原始曲线。[编辑]即T仅上升到1.0,并测量沿着曲线的距离,作为总长度的比率,测量曲线2与曲线1基线的距离。
另外,当你说curve1和curve2的“基线”之间的“距离函数”时,“我认为你在这里把curve1和curve2混淆了,就像在你的代码中一样,你显然是在使用curve1的基线。
该算法还假设“每个bézier曲线完全由连接所有起点/控制点/终点的多边形所包含,称为其“凸壳”,在曲线1的情况下[编辑]为三角形,其中第二个起点的控制点不是顶点。但我不确定这会对算法产生什么影响。
否则,看起来你的距离计算还不错(尽管你确实可以稍微优化一下)。
关于java - 计算贝塞尔剪裁中的距离函数时遇到问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10183230/