Точечный и эллиптический (повернутый) позиционный тест: алгоритм

Как проверить, находится ли точка P = [xp, yp] внутри/вне некоторого повернутого эллипса, заданного центром C = [x, y], a, b и phi (угол поворота)?

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

Но есть много проверенных точек (тысяч), и я нахожу это решение медленным. Есть ли прямой и эффективный способ получить положение повернутого эллипса и точки?

Мне не нужен код, кроме алгоритма. Благодарим за помощь.

Ответы

Ответ 1

Другой вариант - просто выбросить все в уравнение для двумерного повернутого эллипса и посмотреть, не меньше ли результат.

Итак, точка находится внутри эллипса, если верно следующее неравенство

ellipse equation

Где (xp, yp) - координаты точки, а (x0, y0) - центр эллипса.

Я реализовал небольшую программу Mathematica, демонстрирующую, что это действительно работает: Manipulate screen shot

Здесь он находится в действии:

Animation

И вот код:

ellipse[x_, y_, a_, b_, \[Alpha]_, x0_: 0, y0_: 0] := 
     (((x - x0)*Cos[\[Alpha]] + (y - y0)*Sin[\[Alpha]])/a)^2
   + (((x - x0)*Sin[\[Alpha]] - (y - y0)*Cos[\[Alpha]])/b)^2;

Manipulate[
 RegionPlot[
  ellipse[x, y, a, b, \[Alpha] \[Degree], Sequence @@ pos] < 1, {x, -5, 5}, {y, -5, 5}, 
  PlotStyle -> If[ellipse[Sequence @@ p, a, b, \[Alpha] \[Degree], Sequence @@ pos] <= 1, Orange, LightBlue], 
  PlotPoints -> 25]
, {{a, 2}, 1, 5, Appearance -> "Labeled"}
, {{b, 4}, 2, 5, Appearance -> "Labeled"}
, {\[Alpha], 0, 180,  Appearance -> "Labeled"}
, {{p, {3, 1}}, Automatic, ControlType -> Locator}
, {{pos, {0, 0}}, Automatic, ControlType -> Locator}]

Ответ 2

Вы можете просто подавать свои данные в формулу, указанную выше. Вот реализация python, которую я сделал по рекомендациям Ajasja:

def pointInEllipse(x,y,xp,yp,d,D,angle):
    #tests if a point[xp,yp] is within
    #boundaries defined by the ellipse
    #of center[x,y], diameter d D, and tilted at angle

    cosa=math.cos(angle)
    sina=math.sin(angle)
    dd=d/2*d/2
    DD=D/2*D/2

    a =math.pow(cosa*(xp-x)+sina*(yp-y),2)
    b =math.pow(sina*(xp-x)-cosa*(yp-y),2)
    ellipse=(a/dd)+(b/DD)

    if ellipse <= 1:
        return True
    else:
        return False

Ответ 3

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

Если вы видите эллипс как единичный круг (радиус 1), масштабированный (a, b), повернутый на phi и преобразованный (x, y), то жизнь становится намного проще. Если у вас есть эта матрица преобразования, вы можете использовать ее для упрощения запроса на сдерживание. Если вы преобразуете точку в координатную систему, где эллипс является единичным кругом, все, что вам нужно сделать, - это тест окружности в виде единицы измерения, который тривиален. Если "transform" - это матрица, которая преобразует единый круг в ваш эллипс, как описано, тогда

transformedPoint = transform.Invert().Transform(point);
pointInEllipse = transformedPoint.DistanceTo(0,0) < 1.0;

Ответ 4

Вот алгоритм, я позволю вам разработать код:

  • Определите вектор v1 между центром эллипса и вашей точкой.
  • Определить угол a1 между вектором v1 и осью x в мировых координатах
  • Substract phi из a1, чтобы получить a2, наш векторный угол в локальных координатах
  • Определите точку P2 на эллипсе под углом a2 в локальных координатах, а не смещен на (x, y)
  • Вычислите L1 и L2, длину вектора a1 и a2

Оценка:

  • Если L1 < L2 точка находится внутри
  • Если L1 = L2 (плюс/минус небольшой допуск), точка находится на эллипсе
  • Если L2 > L2, то точка находится вне

Эллиптическая параметрическая формула:

x = a * cos (u)
y = b * sin (u)

действует для u между -pi и + pi. Добавьте phi в u, чтобы повернуть ваш эллипс.

Алгоритм выше может быть упрощен и оптимизирован из уравнений эллипса.

Удачи!

Ответ 5

Matplotlib имеет метод Ellipse в классе патчей, который позволяет задать вопрос, находится ли точка внутри или вне патча. Проверьте здесь и найдите метод contains_point(). Вам нужно будет создать эллипс с классом Ellipse, а затем, как будто внутри есть точка. BTW, matplotlib - это пакет для python.