Мне легче работать с векторными уравнениями, так как алгебра будет инвариантной к вращению (поэтому вам не нужно переписывать код, чтобы иметь дело, например, с "горизонтальной" параболой).
1. Представление кривой + тест пересечения
Рассмотрим квадратичную кривую Безье с конечными точками A, C, контрольной точкой B и параметром t:
И бесконечная линия с источником O, направлением D и параметром s:
Приравнивая P и R, получим пару квадратичных одновременных уравнений, которые можно переставить так, чтобы исключить s и найти параболический параметр t:
Решите это квадратное уравнение для t, и принимайте только реальные корни в диапазоне [0, 1]. Это гарантирует, что любая точка пересечения будет всегда на самом сегменте.
2. Работа с отрезками
Вы также можете ограничить точку пересечения линией сегмент , вычислив s из t с использованием приведенных выше уравнений и ограничив ее значение - равное расстоянию по линии от O если D нормализуется.
3. Вычисление контрольной точки B
Обратите внимание, что общее значение контрольной точки B не даст симметричную параболу. Чтобы вычислить B для общей симметричной кривой:
Определение переменных:
M: средняя точка ABn: по часовой стрелке, нормальный в направлении ACq: расстояние до выпуклости со знаком - абсолютное значение - это расстояние от M до средней точки кривой k: расстояние от M до B
Удивительно простой результат.
4. Пример кода C # (стиль)
public static Vector2[] computeIntersection
(
Vector2 A, Vector2 C, double q, // parabola segment
Vector2 O, Vector2 P // line segment
)
{
// quadratic solve
double[] solve(double a, double b, double c)
{
double d = b * b - 4.0 * a * c;
if (d < 0.0) // imaginary roots - no intersection at all
return null;
if (d > 0.0) // two distinct real roots
{
double sd = Math.Sqrt(d);
return new double[2] { (-b + sd) / (2.0 * a),
(-b - sd) / (2.0 * a) };
}
else // only one (line segment is tangent to curve)
{
return new double[1] { -b / (2.0 * a) };
}
}
// cross product (in-case undefined)
double cross(Vector2 i, Vector2 j)
{
return i.x * j.y - i.y * j.x;
}
// validity check for t and s
bool valid(double v)
{
return (v >= 0.0) && (v <= 1.0);
}
// compute control point B
Vector2 E = C - A;
Vector2 M = 0.5 * (A + C);
Vector2 N = (new Vector2(E.y, -E.x)).normalize();
Vector2 B = M + (2.0 * q) * N;
// solving for t
Vector2 D = P - O;
bool useX = Math.Abs(D.X) > Math.Abs(D.Y);
double[] T = solve(cross(A + C - 2.0 * B, D),
cross(B - A, D) * 2.0,
cross(A - O, D));
if (T == null) return null;
Vector2[] I = new Vector2[2];
int c = 0;
for (int i = 0; i < T.Length; i++)
{
// check if t is within curve range
double t = T[i];
if (!valid(t)) continue;
// solve for s and check if is within line range
double u = (1 - t) * (1 - t);
double v = 2 * t * (1 - t);
double w = t * t;
double s = useX ? ((u * A.X + v * B.X + w * C.X - O.X) / D.X)
: ((u * A.Y + v * B.Y + w * C.Y - O.Y) / D.Y);
if (!valid(s)) continue;
// compute the corresponding intersection point
I[c++] = O + s * D;
}
// only return valid solutions
if (c == 0) return null;
Array.Resize(ref I, c);
return I;
}