抛物线与线段的交点

4

我有一个关于抛物线曲线与指定点相交的方程,这里指用户在图表上单击的位置。

 // this would typically be mouse coords on the graph
 var _target:Point = new Point(100, 50);

 public static function plot(x:Number, target:Point):Number{
  return (x * x) / target.x * (target.y / target.x);
 }

这将生成如下图所示的图形:

抛物线曲线

我还有一系列由起始坐标和结束坐标定义的线段:
startX:Number, startY:Number, endX:Number, endY:Number

我需要找出这条曲线与这些线段(A)相交的位置:

alt text

如果有帮助的话,startX总是小于endX

我感觉有一个相当简单的方法来做到这一点,但我不知道要搜索什么,也不太精通“适当”的数学,所以实际的代码示例将非常受欢迎。

更新:

我已经解决了交点的问题,但我的解决方案给出了错误侧面的坐标。

用A和B替换我的目标坐标,得到了该图的方程:

(x * x) / A * (B/A)

// this simplifies down to:
(B * x * x) / (A * A)

// which i am the equating to the line's equation
(B * x * x) / (A * A) =  m * x + b

// i run this through wolfram alpha (because i have no idea what i'm doing) and get:
(A * A * m - A * Math.sqrt(A * A * m * m + 4 * b * B)) / (2 * B)

这是一个正确的答案,但我想要第二种可能的变化。我已经通过在计算前将m乘以-1来进行修正,并在最后一次计算返回的x值上执行相同的操作来纠正这个问题,但感觉像是一个hack。

解决方案:

 public static function intersectsSegment(targetX:Number, targetY:Number, startX:Number, startY:Number, endX:Number, endY:Number):Point {
  // slope of the line
  var m:Number = (endY - startY) / (endX - startX);

  // where the line intersects the y-axis
  var b:Number = startY - startX * m;

  // solve the two variatons of the equation, we may need both
  var ix1:Number = solve(targetX, targetY, m, b);
  var ix2:Number = solveInverse(targetX, targetY, m, b);

  var intersection1:Point;
  var intersection2:Point;

  // if the intersection is outside the line segment startX/endX it's discarded
  if (ix1 > startX && ix1 < endX) intersection1 = new Point(ix1, plot(ix1, targetX, targetY));
  if (ix2 > startX && ix2 < endX) intersection2 = new Point(ix2, plot(ix2, targetX, targetY));

  // somewhat fiddly code to return the smallest set intersection
  if (intersection1 && intersection2) {
   // return the intersection with the smaller x value
   return intersection1.x < intersection2.x ? intersection1 : intersection2;
  } else if (intersection1) {
   return intersection1;
  }

  // this effectively means that we return intersection2 or if that's unset, null
  return intersection2;
 }

 private static function solve(A:Number, B:Number, m:Number, b:Number):Number {
  return (m + Math.sqrt(4 * (B / (A * A)) * b + m * m)) / (2 * (B / (A * A)));
 }

 private static function solveInverse(A:Number, B:Number, m:Number, b:Number):Number {
  return (m - Math.sqrt(4 * (B / (A * A)) * b + m * m)) / (2 * (B / (A * A)));
 }

 public static function plot(x:Number, targetX:Number, targetY:Number):Number{
  return (targetY * x * x) / (targetX * targetX);
 }

你的解决方案和我的一样。我认为你应该只选择正数选项(+A * Math.sqrt),而不是(-A * Math.sqrt),然后其他保持不变///一个二次方程有两个解...只需选择另一个即可。 - Dr. belisarius
1
注意 //// 你的 (B/(A*A)) = 我的 A - Dr. belisarius
4个回答

6
或者更加明确一些。
如果你的抛物线曲线是 y(x) = Ax2 + Bx + C (方程1) 而你的直线是 y(x) = mx + b (方程2) 则x的两个可能解(+和-)是:
x = ((-B + m +- Sqrt[4 A b + B^2 - 4 A C - 2 B m + m^2])/(2 A))   (Eq 3)

您需要检查您的线段端点(在x轴上)是否包含这两个点。如果是,则只需替换y = mx + b方程中对应的x,以获取交点的y坐标。
编辑>
要得到最后一个方程式,您只需说“方程1中的y等于方程2中的y”(因为您正在寻找交点!)。 这给出了:
A x² + B x + C = m x + b
重新组合:
A x² + (B-m) x + (C-b) = 0
这是一个二次方程。
方程3只是此二次方程的两个可能解。
编辑2> 重新阅读您的代码,似乎您的抛物线是由以下方式定义的
y(x) = Ax²
其中,
A = target.y / (target.x²)
因此,在您的情况下,方程3变得非常简单。
 x = ((m +- Sqrt[4 A b + m^2])/(2 A))   (Eq 3b)  

HTH!


我不明白你是如何从曲线/直线的函数推导出最后的方程式的,常数(4/2)是从哪里来的? - grapefrukt
是的,我终于解决了。如果没有你的帮助,我永远不会做到这一点。 - grapefrukt
@grapefrukt 很高兴能帮到你。试试这个软件 http://geometryexpressions.com/ ... 免费版本可以帮助你解决这类问题。祝你好运! - Dr. belisarius

3

“解出x”是我遇到的问题,如果有任何详细说明,我将不胜感激! - grapefrukt
没错!抱歉,用笔和纸解决X的问题很容易,但使用计算机就是另一回事了。因此,我们想要使用矩阵来解决线性方程。这里有一个C#示例http://www.extremeoptimization.com/QuickStart/StructuredLinearEquationsCS.aspx如果这不起作用,还有其他几个资源可以使用矩阵来解决线性方程,但最终你需要做的就是这样。 - Matthew
以下是更多的资源链接: http://www.daniweb.com/forums/thread263798.html 和 http://www.codeproject.com/KB/recipes/matrixoperations.aspx如果需要更多帮助,请告诉我 :) - Matthew
使用矩阵有点粗暴,但可以扩展到使用除抛物线曲线以外的不同曲线。然而,如果你只想使用抛物线曲线,我认为belisarius的答案非常好。 - Matthew

3
您是否经常需要在计算交点之前进行分离测试以确定是否存在交点?如果是,可以考虑这个事实:您的抛物线是函数f(x,y)= y-(B * x * x)/(A * A)的水平集,特别地,当f(x,y)= 0时。将两个端点插入f(x,y)中--如果它们具有相同的符号,则它们在抛物线的同一侧,而如果它们具有不同的符号,则它们在抛物线的不同侧。
现在,您仍然可能有一个段与抛物线交叉两次,而这个测试无法捕获它。但是根据您定义问题的方式,我认为这可能适用于您的应用程序。

那本来是我接下来要做的事情,但结果证明它足够快以完成完整检查。我正在使用它来检查先前生成的样条段的片段,我可以在大约30毫秒内运行所有80k个分布在3k条样条线上的片段。对于一个花费了六个小时在15行代码上的人来说,我感到非常高兴!;) - grapefrukt

0
换句话说,您需要为每个线段计算方程式 y = Ax + B,将其与曲线方程式 y = Cx^2 + Dx + E 进行比较,因此 Ax + B - Cx^2 - Dx - E = 0 并查看在 startXendX 值之间是否存在解决方案。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接