javascript - 寻找线段和贝塞尔曲线交点的程序

Question

考虑给定的足球场图像

正如您在图像中看到的各种球运动，其中一些是弯曲的(即在图像中的 (1)、(2)、(3) 的情况下))而有些可能不是(即一条线( 4)),

所以我需要找到球路径与球门线和边线的交点。有时输入可能不是曲线(即直线)，如(4)给定图像的情况

我写了一个程序，我不知道哪里出了问题 - 这是解决这种程序的正确方法吗。

如果是那么如何将贝塞尔曲线转化为方程更好的求解

考虑给定的

beizer curve eqaution -> a(x*x) + b*x + c
and line segment equation -> y = y1 + m(x-x1)

//maxCurvedPoint是曲线的最顶端

var getIntersectionPoint = function (room, ballFromPosition, ballToPosition, maxCurvePoint) 
{
    var linepoints = [[m1,n1], [m2, n2], [m3, n3], [m4, n4]];

    //converting three points(ballFromPosition, maxCurvePoint, ballToPosition) into the quadratic equation (Bezier curve) --(1)
    //getting the equation of the line segment using the linepoints --(2)

    //equating (1) and (2) and getting a quadratic equation and solving and finding intersection points
    return intersectionPoint;
}

// solves //(-b(+-)sqrt(b*b - 4ac)/2ac)
function solve(a, b, c) 
{        
 //check curve intersects line or not
   if((Math.pow(b, 2) - (4 * a * c)) >= 0) 
   {
       result1 = (-1 * b + Math.sqrt(Math.pow(b, 2) - (4 * a * c))) / (2 * a);
       result2 = (-1 * b - Math.sqrt(Math.pow(b, 2) - (4 * a * c))) / (2 * a);
       return [result1, result2];
   } 

   return [];
}

谁能帮我解决这个问题？也就是最弯曲的点可以称为曲线的顶点吗？

Answer 1

我发现使用向量方程更容易，因为代数将是旋转不变的(因此您不必重新编写代码来处理例如“水平”抛物线)。

---

<强>1。曲线表示+交点测试

考虑一个 quadratic Bezier curve具有端点 A、C、控制点 B 和参数 t:

还有一条无限线，源O，方向D，参数s:

使 P 和 R 等式给出一对二次联立方程，可以重新排列它们以消除 s 并找到抛物线参数t:

为 t 求解此二次方程，并且只接受 [0, 1] 范围内的实根。这可确保任何交点始终在线段本身上。

---

<强>2。处理线段

您还可以通过使用上面的等式从 t 计算 s 并限制其值，将交点限制为线 段 - 如果 D 被归一化，它等于从 O 沿线的距离。

---

<强>3。计算控制点B

请注意，控制点 B 的一般值不会给出对称抛物线。要计算一般对称曲线的 B:

定义变量:

• M:AB的中点
• n:顺时针方向 AC
• q:signed bulge distance - 绝对值是从M到曲线中点的距离
• k:从M到B
的有符号距离

一个出奇简单的结果。

---

<强>4。示例 C#(-style)代码

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;
}