Неисправность расчета функции расстояния в отсечении Безье
Я пытаюсь реализовать алгоритм пересечения кривых, известный как отсечение Безье, которое описано в разделе, приведенном в конце этой статьи (хотя в статье это называется "отсечение по жирной линии"). Я следил за статьей и исходным кодом примера (доступно здесь).
Примечание. Дополнительные источники включают эту статью. Больше будет опубликовано, если я смогу их найти.
Центральная часть этого алгоритма вычисляет "функцию расстояния" между кривой 1 и "базовой линией" кривой 2 (которая является линией от одной конечной точки кривой 2 к другой). Так что у меня было бы с чем сравнить свои результаты, я использовал кривые из исходного кода первого примера. Мне удалось воспроизвести форму функции расстояния из примера, но расположение функции расстояния было отключено. После попытки другой кривой, функция расстояния была далеко от двух других кривых, несмотря на то, что обе четко пересекались. Я мог бы быть наивным по отношению к работе этого алгоритма, но я думаю, что это не привело бы к обнаружению пересечения.
Из того, что я понимаю (что вполне может быть ошибочным), процесс определения функции расстояния включает в себя выражение базовой линии кривой 2 в виде xa + y b + c = 0, где a2 + b2 = 1. Коэффициенты были получены путем перестановки членов линии в виде y = ux + v, гдеu равно наклону, а x и y - любые точки на базовой линии. Формула может быть перестроена так, чтобы получитьv:v = y - u x. Переставляя формулу снова, мы получаем -u * x + 1 * y - v = 0, где a = -u, b = 1 и c = -v. Чтобы обеспечить условие a2 + b2 = 1, коэффициенты делятся на скаляр Math.sqrt (uu + 1). Это представление линии затем подставляется в функцию другой кривой (с которой базовая линия не связана), чтобы получить функцию расстояния. Эта функция расстояния представлена в виде кривой Безье, гдеyi= a Pix + b * Piy + c и xi = (1 - t)x1 + t x2, где t равно 0, 1/3, 2/3, и 3 m x1 и x2 - конечные точки базовой линии, а Pi - контрольные точки кривой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 находятся на одном уровне, что приводит к наклону нуля для базовой линии.
Для ввода (485, 430, 580, 60, 430, 115, 530, 160) для кривой 1 и (575, 25, 455, 60, 541, 140, 486, 210) для кривой 2 (имейте в виду, что эти значения повернуты на отрицательный угол между конечными точками кривой1), результат показан ниже (функция расстояния - это относительно гладкая кривая на расстоянии):
Я действительно не уверен, что я ошибся. Кажется, что значения y расположены по правильному шаблону, но они далеки от двух кривых, на которых он основан. Я понимаю, что возможно, у меня есть значения x, которые могут быть расположены с интервалами вдоль кривой, а не по базовой линии, но значения y - это то, что меня действительно смущает. Если кто-то может взглянуть на это и объяснить, в чем я ошибся, я был бы очень признателен. Спасибо, что нашли время, чтобы прочитать этот довольно длинный вопрос. Если нужно больше деталей, не стесняйтесь, сообщите мне в комментариях.
Обновление: я проверил представление линии, которую я рассчитал. Представление ax + b y + c = 0, очевидно, все еще представляет ту же строку, так как я все еще могу подключить x1 и получить y1. Кроме того, для любых двух координатных пар, включенных в функцию, выполняется f(x, y) = 0. Кроме того, я обнаружил, что как представление, описанное в статье, так и представление, фактически используемое в исходном коде, взаимозаменяемо представляют одну и ту же строку. Исходя из всего этого, я могу предположить, что проблема заключается не в расчете линии. Дополнительная достопримечательность
1 ответ
Ваша функция расстояния не обязательно должна быть где-то рядом с вашими двумя исходными кривыми: она использует совершенно другую систему координат, то есть t против D, в отличие от ваших исходных кривых, использующих x и y. [править] т. е. t поднимается только до 1,0 и измеряет, как далеко, как отношение общей длины, вы находитесь вдоль своей кривой, а D измеряет расстояние, на котором ваша кривая2 находится от базовой линии кривой1.
Кроме того, когда вы говорите "" функция расстояния "между кривой 1 и" базовой линией "кривой 2", я думаю, что вы смешали здесь кривые 1 и 2, так как в коде вы явно используете базовую линию кривой 1.
Также алгоритм предполагает, что "каждая кривая Безье полностью содержится в многоугольнике, соединяющем все начальные / контрольные / конечные точки, известном как" выпуклая оболочка "", который [править] в вашем случае для кривой 1 является треугольником, где элемент управления точка для второго начального значения не является вершиной. Я не уверен, как это влияет на алгоритм, хотя.
В противном случае, похоже, что ваши расчеты расстояния в порядке (хотя вы могли бы действительно немного оптимизировать вещи:)).