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

Question

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

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

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

Мне не нужен код, кроме алгоритма. Спасибо за вашу помощь.

Answer 1

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

Так точка находится внутри эллипса, если выполняется неравенство

Где (Xp, Yp) являются координаты точки и (х0, у0) является центром эллипса.

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

Здесь в действии:

А вот код:

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

Answer 2

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

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

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

Answer 3

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

1. определить вектор v1 между центр эллипса и ваша точка
2. Определить угол между вектором a1 v1 и осями х в мировых координатах
3. вычитать PHI от a1 получить a2, наш вектор угол в локальных координатах
4. Определить точку Р2 на эллипса под углом а2 в локальных координатах, не компенсируется (х, у)
5. Вычислить L1 и L2, длина вектора a1 и a2

Оценка:

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

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

х = а * соз (и)
у = Ь * Sin (и)

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

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

Удачи вам!

Answer 4

Вы можете просто отправить свои данные в форму ула, указанная выше. Вот реализация питон я сделал по рекомендациям 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 

Answer 5

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