ベジェクリッピングと呼ばれる曲線交差アルゴリズムを実装しようとしています。これについては、この記事の最後のセクションで説明しています（ただし、この記事では「太い線クリッピング」と呼んでいます）。私は例の記事とソースコード（ここで入手可能）をフォローしてきました。
注：追加のソースには、このペーパーが含まれます。見つけたらもっと投稿します。
このアルゴリズムの中心的な部分は、curve1とcurve2の「ベースライン」（curve2の1つの終点から別の終点までの線）の間の「距離関数」を計算することです。そのため、結果を比較するものがあります。最初の例のソースコードの曲線を使用しました。例から距離関数の形状を複製することができましたが、関数の距離位置がオフでした。別の曲線を試してみると、距離関数は、両方が明確に交差しているにもかかわらず、他の2つの曲線の近くにはありませんでした。私はこのアルゴリズムの働きにナイーブかもしれませんが、それでは交差点が検出されなくなると思います。
私が理解していることから（これはおそらく間違っている可能性があります）、距離関数を定義するプロセスには、曲線2のベースラインをx a + y b + c = 0の形式で表すことが含まれます。ここで、a 2 + b 2 =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 + b 2 = 1を保証するために、係数はMath.sqrt（u u + 1）のスカラーで除算されます。次に、この線の表現を他の曲線（ベースラインが関連付けられていない曲線）の関数に代入して、距離関数を取得します。この距離関数は、y i = a P i x + b * P i y +cおよびxi =（1-t）x1 + t x2のベジェ曲線として表されます。ここで、tは0、1 / 3、2に等しくなります。 / 3、および3 m x1x2はベースラインの端点であり、Piはcurve1の制御点です。
以下は、距離関数の計算に関連するサンプルプログラム（言語処理で記述された）のソースコードのいくつかのカットです。これは、奇妙なことに、ベースラインの代替表現を計算するために上記の段落とは少し異なるアプローチを使用します。
/**
* 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のマイナーな拡張です。曲線がコンストラクターに渡される前に、曲線は均一に回転されるため、curve1の端点は水平になり、ベースラインの勾配はゼロになります。
曲線1の場合は（485、430、580、60、430、115、530、160）、曲線2の場合は（575、25、455、60、541、140、486、210）の入力の場合（これらに注意してください値はcurve1）の端点間で負の角度だけ回転し、結果を以下に示します（distance関数は、距離が比較的滑らかに見える曲線です）。
何が悪かったのかよくわかりません。y値は正しいパターンで配置されているように見えますが、基になっている2つの曲線から離れています。x値がベースラインではなく曲線に沿って間隔を置いて配置されている可能性があることはわかっていますが、y値は私が本当に混乱しているものです。誰かがこれを見て、私が間違ったことを説明することができれば、私は本当に感謝しています。このかなり長い質問を読むために時間を割いてくれてありがとう。詳細が必要な場合は、コメントでお気軽にお知らせください。
更新：計算した線の表現をテストしました。a x + b y + c = 0の表現は、x1をプラグインしてy1を取得できるため、明らかに同じ線を表します。さらに、関数に接続されている任意の2つの座標ペアについて、f（x、y）=0が成り立ちます。さらに、記事で説明されている表現と、ソースコードで実際に使用されている表現の両方が同じ行を交換可能に表現していることがわかりました。これらすべてから、問題は線の計算にあるのではないと推測できます。追加の興味のあるポイント