Пересечение параболической кривой и отрезка прямой

Question

У меня есть уравнение для параболической кривой, пересекающей указанную точку, в моем случае, когда пользователь нажал на график.

 // 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):

Если это хоть как-то поможет, startX всегда есть < endX

У меня такое чувство, что есть довольно простой способ сделать это, но я действительно не знаю, что искать, и я не очень хорошо разбираюсь в "правильной" математике, поэтому я был бы очень признателен за реальные примеры кода.

Обновить:

У меня работает пересечение, но мое решение дает мне координату для неправильной стороны оси y.

Замена моих целевых координат на 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, возвращаемым последним вычислением, но это похоже на взлом.

РЕШЕНИЕ:

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

Answer 1

Или, еще более явные.

Если ваша параболическая кривая y(x)= A x2+ B x + C (Eq 1)

и ваша линия y(x) = m x + b (Eq 2)

Два возможных решения (+ и -) для х

x = ((-B + m +- Sqrt[4 A b + B^2 - 4 A C - 2 B m + m^2])/(2 A))   (Eq 3)

Вы должны проверить, содержит ли конечные точки вашего сегмента (в X) любой из этих двух точек. Если они сделают, просто замените соответствующие X в уравнении y = mx + b, чтобы получить координату Y для пересечения

Редактировать>

Чтобы получить последнее уравнение, вы просто говорите, что «Y» в эквалайзе 1 равно «y» в уравнении 2 (потому что вы ищете пересечение!). Это дает вам:

A x2+ B x + C = m x + b


и перегруппировка

A x2+ (B-m) x + (C-b) = 0

Который является квадратичным уравнением.

Уравнение 3 - это только два возможных решения для этого квадратичного.

Редактировать 2>

Перечитайте свой код, кажется, что ваша парабола определяется y(x) = A x2


куда
A = (target.y / (target.x)2)

Так что в вашем случае уравнение 3 становится просто

 x = ((m +- Sqrt[4 A b + m^2])/(2 A))   (Eq 3b)  

HTH!

Answer 2

Возьмите уравнение для кривой и поместите свою линию в форму y = mx + b. Решите для X, а затем определите, между вашим начальным и конечным точками для вашего сегмента LINE.

Проверить: http://mathcentl.uregina.ca/qq/database/qq.09.03/senthil1.html.

Answer 3

Вы делаете это достаточно часто, чтобы захотеть провести отдельный тест, чтобы увидеть, существует ли пересечение, прежде чем фактически вычислять точку пересечения?Если это так, учтите тот факт, что ваша парабола является уровнем, установленным для функции f (x, y) = y - (B * x * x) / (A * A) - в частности, той, для которой f (x, y) = 0.Подключите ваши две конечные точки к f (x, y) - если они имеют одинаковый знак, они находятся на одной стороне параболы, в то время как если у них разные знаки, они находятся на разных сторонах параболы.

Теперь у вас все еще может быть отрезок, пересекающий параболу дважды, и этот тест этого не улавливает.Но что-то в том, как вы определяете проблему, заставляет меня думать, что, возможно, это нормально для вашего приложения.

Answer 4

Другими словами, вам нужно оваривать уравнение для каждого сегмента строки y = Ax + B сравнить его с уравнением кривой y = Cx^2 + Dx + E так Ax + B - Cx^2 - Dx - E = 0 и посмотреть, есть ли решение между startX а также endX значения.