В зависимости от ваших допусков. Грубая сила и принятие ошибки. Этот алгоритм может быть неправильным в некоторых редких случаях. Но в большинстве из них он найдет точку, очень близкую к правильному ответу, и результаты будут улучшаться по мере того, как вы будете устанавливать срезы. Он просто пробует каждую точку кривой через равные промежутки времени и возвращает лучшую найденную точку.
public double getClosestPointToCubicBezier(double fx, double fy, int slices, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3) {
double tick = 1d / (double) slices;
double x;
double y;
double t;
double best = 0;
double bestDistance = Double.POSITIVE_INFINITY;
double currentDistance;
for (int i = 0; i <= slices; i++) {
t = i * tick;
//B(t) = (1-t)**3 p0 + 3(1 - t)**2 t P1 + 3(1-t)t**2 P2 + t**3 P3
x = (1 - t) * (1 - t) * (1 - t) * x0 + 3 * (1 - t) * (1 - t) * t * x1 + 3 * (1 - t) * t * t * x2 + t * t * t * x3;
y = (1 - t) * (1 - t) * (1 - t) * y0 + 3 * (1 - t) * (1 - t) * t * y1 + 3 * (1 - t) * t * t * y2 + t * t * t * y3;
currentDistance = Point.distanceSq(x,y,fx,fy);
if (currentDistance < bestDistance) {
bestDistance = currentDistance;
best = t;
}
}
return best;
}
Вы можете стать намного лучше и быстрее, просто найдя ближайшую точку и повторяя ее вокруг.
public double getClosestPointToCubicBezier(double fx, double fy, int slices, int iterations, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3) {
return getClosestPointToCubicBezier(iterations, fx, fy, 0, 1d, slices, x0, y0, x1, y1, x2, y2, x3, y3);
}
private double getClosestPointToCubicBezier(int iterations, double fx, double fy, double start, double end, int slices, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3) {
if (iterations <= 0) return (start + end) / 2;
double tick = (end - start) / (double) slices;
double x, y, dx, dy;
double best = 0;
double bestDistance = Double.POSITIVE_INFINITY;
double currentDistance;
double t = start;
while (t <= end) {
//B(t) = (1-t)**3 p0 + 3(1 - t)**2 t P1 + 3(1-t)t**2 P2 + t**3 P3
x = (1 - t) * (1 - t) * (1 - t) * x0 + 3 * (1 - t) * (1 - t) * t * x1 + 3 * (1 - t) * t * t * x2 + t * t * t * x3;
y = (1 - t) * (1 - t) * (1 - t) * y0 + 3 * (1 - t) * (1 - t) * t * y1 + 3 * (1 - t) * t * t * y2 + t * t * t * y3;
dx = x - fx;
dy = y - fy;
dx *= dx;
dy *= dy;
currentDistance = dx + dy;
if (currentDistance < bestDistance) {
bestDistance = currentDistance;
best = t;
}
t += tick;
}
return getClosestPointToCubicBezier(iterations - 1, fx, fy, Math.max(best - tick, 0d), Math.min(best + tick, 1d), slices, x0, y0, x1, y1, x2, y2, x3, y3);
}
В обоих случаях вы можете сделать четырехугольник так же легко:
x = (1 - t) * (1 - t) * x0 + 2 * (1 - t) * t * x1 + t * t * x2; //quad.
y = (1 - t) * (1 - t) * y0 + 2 * (1 - t) * t * y1 + t * t * y2; //quad.
Сменив уравнение там.
Хотя принятый ответ правильный, и вы действительно можете выяснить корни и сравнить эти вещи. Если вам действительно нужно найти ближайшую точку на кривой, это сделает это.
По поводу Бена в комментариях. Вы не можете сократить формулу во многих сотнях контрольных точек, как я сделал для кубических и четырехугольных форм. Потому что количество, требуемое каждым новым добавлением кривой Безье, означает, что вы строите для них пифагорейские пирамиды, и мы в основном имеем дело с еще более и более массивными цепочками чисел. Для четырехугольника вы идете 1, 2, 1, для кубического - 1, 3, 3, 1. В конечном итоге вы строите все большие и большие пирамиды и заканчиваете тем, что разбиваете их по алгоритму Кастельжау (я написал это для полной скорости):
/**
* Performs deCasteljau's algorithm for a bezier curve defined by the given control points.
*
* A cubic for example requires four points. So it should get at least an array of 8 values
*
* @param controlpoints (x,y) coord list of the Bezier curve.
* @param returnArray Array to store the solved points. (can be null)
* @param t Amount through the curve we are looking at.
* @return returnArray
*/
public static float[] deCasteljau(float[] controlpoints, float[] returnArray, float t) {
int m = controlpoints.length;
int sizeRequired = (m/2) * ((m/2) + 1);
if (returnArray == null) returnArray = new float[sizeRequired];
if (sizeRequired > returnArray.length) returnArray = Arrays.copyOf(controlpoints, sizeRequired); //insure capacity
else System.arraycopy(controlpoints,0,returnArray,0,controlpoints.length);
int index = m; //start after the control points.
int skip = m-2; //skip if first compare is the last control point.
for (int i = 0, s = returnArray.length - 2; i < s; i+=2) {
if (i == skip) {
m = m - 2;
skip += m;
continue;
}
returnArray[index++] = (t * (returnArray[i + 2] - returnArray[i])) + returnArray[i];
returnArray[index++] = (t * (returnArray[i + 3] - returnArray[i + 1])) + returnArray[i + 1];
}
return returnArray;
}
Вам в основном нужно использовать алгоритм напрямую, не только для вычисления x, y, которые происходят на самой кривой, но вам также нужно, чтобы он выполнял действительный и правильный алгоритм подразделения Безье (есть и другие, но это то, что Я бы порекомендовал), чтобы рассчитать не только приближение, которое я даю, разделив его на отрезки, но и действительные кривые. Или скорее корпус многоугольника, который наверняка будет содержать кривую.
Вы делаете это, используя вышеупомянутый алгоритм, чтобы подразделить кривые в данном t. Таким образом, T = 0,5, чтобы разрезать кривые пополам (примечание 0.2 сократило бы его на 20%, 80% по кривой). Затем вы индексируете различные точки на стороне пирамиды и на другой стороне пирамиды, построенной из основания. Так, например, в куб.
9
7 8
4 5 6
0 1 2 3
Вы должны указать алгоритм 0 1 2 3 в качестве контрольных точек, а затем индексировать две идеально разделенные кривые на 0, 4, 7, 9 и 9, 8, 6, 3. Обратите особое внимание на то, что эти кривые начать и закончить в одной точке. и последний индекс 9, который является точкой на кривой, используется в качестве другой новой точки привязки. Учитывая это, вы можете идеально разделить кривую Безье.
Затем, чтобы найти ближайшую точку, вы хотите продолжить подразделение кривой на разные части, отмечая, что это тот случай, когда вся кривая Безье содержится внутри корпуса контрольных точек. То есть, если мы превращаем точки 0, 1, 2, 3 в замкнутый путь, соединяющий 0,3, эта кривая должна полностью попасть в этот корпус многоугольника. Поэтому мы определяем заданную точку P, а затем продолжаем подразделять кривые до тех пор, пока не узнаем, что самая дальняя точка одной кривой находится ближе, чем самая близкая точка другой кривой. Мы просто сравниваем эту точку P со всеми контрольными и опорными точками кривых. И отбросьте любую кривую из нашего активного списка, ближайшая точка которой (привязка или элемент управления) находится дальше, чем самая дальняя точка другой кривой. Затем мы подразделяем все активные кривые и делаем это снова. В конце концов у нас будут очень подразделенные кривые, отбрасывающие примерно половину каждого шага (то есть, это должно быть O (n log n)), пока наша ошибка в основном ничтожна. В этой точке мы называем наши активные кривые ближайшей точкой к этой точке (их может быть больше одной) и отмечаем, что ошибка в этом сильно подразделенном бите кривой в основном равна точке. Или просто решите проблему, сказав, какая из двух опорных точек ближе всего находится к нашей точке P. И мы знаем ошибку в очень определенной степени.
Это, однако, требует, чтобы мы на самом деле имели надежное решение и выполнили конечно правильный алгоритм и правильно нашли крошечную часть кривой, которая, безусловно, будет ближайшей точкой к нашей точке. И все еще должно быть относительно быстро.