Проблема вычисления функции расстояния в отсечении Безье

Я пытаюсь реализовать алгоритм поиска кривых, известный как отсечение Безье, который описан в разделе ближе к концу этой статьи (хотя статья называет его "отсечение жирной линии"). Я следил за статьей и исходным кодом примера (доступно здесь).

Примечание: дополнительные источники включают эту статью. Больше будет размещена, если я могу найти их.

Центральной частью этого алгоритма является вычисление " расстояния функция "между curve1 и" базовой линией " curve2 (которая представляет собой линию от одной конечной точки curve2 до другой). Чтобы мне было с чем сравнить свои результаты, я использовал кривые из исходного кода первого примера. Мне удалось скопировать форму функции расстояния из примера, но расположение функции расстояния было отключено. Попробовав другую кривую, функция расстояния оказалась далеко не рядом с двумя другими кривыми, несмотря на то, что обе явно пересекались. Возможно, я наивен. к работе этого алгоритма, но я думаю, что это приведет к тому, что пересечение не будет обнаружено.

Из того, что я понимаю (что вполне может быть неверно), процесс определения функции расстояния включает в себя выражение базовой линии кривой 2 в виде x a + y b + c = 0 , где a² + b² = 1. Коэффициенты были получены путем перестановки членов прямой в виде y = ux + v, где именно u равно наклону, а x и y-любые точки На базовой линии. Формула может быть перестроена, чтобы дать v: v = y-ux . Переставляя формулу снова, получаем - u * x + 1 * y-v = 0 , где a = - u, b = 1 , и c = -v. Чтобы обеспечить условие a² + b² = 1, коэффициенты делятся на скаляр математики.sqrt(u u + 1). Это представление линии является затем подставляется в функцию другой кривой (той, с которой базовая линия не связана), чтобы получить функцию расстояния. Эта функция расстояния представлена в виде кривой Безье, с y_i = aP_{i x} + b*P_{i y} + c и x_i = (1-t) x1 + tx2 , где t равно чтобы0, 1/3, 2/3, и еще 3m x1 и x2 являются конечными точками базовой линии, и 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.качать.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.ОУ.геометрия.CubicCurve2D.Двойные и Java.ОУ.геометрия.Line2D.Двойной. Перед передачей кривых в конструктор кривые поворачиваются равномерно, так что конечные точки curve1 находятся на одном уровне, что приводит к нулевому наклону для базовой линии.

Для ввода (485, 430, 580, 60, 430, 115, 530, 160) для кривой 1 и (575, 25, 455, 60, 541, 140, 486, 210) для curve2 (имейте в виду, что эти значения поворачиваются на отрицательный угол между конечные точки кривой 1), результат показан ниже (функция расстояния-это относительно гладкая кривая на расстоянии):

Я действительно не уверен, что я ошибся. Значения y, по-видимому, расположены в правильном порядке, но далеки от двух кривых, на которых он основан. Я понимаю, что, возможно, у меня есть значения x, которые могут быть расположены через интервалы вдоль кривой, а не базовой линии, но значения y-это то, что я действительно путаю. Если кто-то может взять взгляните на это и объясните, что я сделал не так, я был бы очень признателен. Спасибо, что нашли время прочитать этот довольно длинный вопрос. Если вам нужны более подробные сведения, вы можете сообщить мне об этом в комментариях.

Обновление: я проверил представление вычисленной линии. Представление a x + b y + c = 0, по-видимому, все еще представляет ту же линию, поскольку я все еще могу подключить x1 и получить y1. Кроме того, для любых двух пар координат, включенных в функцию, f(x, y) = 0 выполняется. Кроме того, я обнаружил, что и представление, описанное в статье, и то, которое фактически используется в исходном коде, взаимозаменяемо представляют одну и ту же строку. Исходя из всего этого, я могу предположить, что проблема заключается не в вычислении линии. Дополнительная точка интереса