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

标签 javascript geometry

考虑给定的足球场图像

enter image description here

正如您在图像中看到的各种球运动,其中一些是弯曲的(即在图像中的 (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 [];
}

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

最佳答案

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


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

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

image

enter image description here

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

enter image description here

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

enter image description here

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


<强>2。处理线段

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


<强>3。计算控制点B

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

enter image description here

定义变量:

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

enter image description here

一个出奇简单的结果。


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

关于javascript - 寻找线段和贝塞尔曲线交点的程序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50129580/

相关文章:

javascript - 无法调用其类型缺少调用签名的表达式。类型没有兼容的调用签名 2349

algorithm - 检测 2D 空间中距离最大的两个点的最快方法是什么?

javascript - 为白板应用程序发送一个大数据包还是许多较小的数据包?

javascript - ReactJS:执行函数后重新加载组件?

javascript - await 函数返回一个 promise,即使条件为 false 也返回 true | react 功能组件

javascript - 触摸事件在 IOS 7 Iphone 中不起作用

c++ - 将点数组转换为多边形

algorithm - 给定多个圆和一个点,如何找到哪个圆包含该点

geometry - 平行线的凸包

WPF:是否可以使用 GeometryDrawing 渲染一个圆?