Как вы вычисляете выровненную по оси ограничительную рамку эллипса?

Question

Если основная ось эллипса вертикальная или горизонтальная, легко вычислить ограничительную рамку, но как насчет вращения эллипса?

Единственный способ, о котором я могу думать, - рассчитать все точки по периметру и найти значения max/min x и y. Похоже, что должен быть более простой способ.

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

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

Answer 1

Вы можете попробовать использовать параметризованные уравнения для эллипса повернут под произвольным углом:

x = h + a*cos(t)*cos(phi) - b*sin(t)*sin(phi) [1] 
y = k + b*sin(t)*cos(phi) + a*cos(t)*sin(phi) [2] 

... где эллипс имеет центральную ось (h, k) полуосновную ось a и полуоси b и повернут на угол phi.

Вы можете дифференцировать и решить для градиента = 0:

0 = dx/dt = -a*sin(t)*cos(phi) - b*cos(t)*sin(phi) 

=>

tan(t) = -b*tan(phi)/a [3] 

Который должен дать вам множество решений для т (два из которых вы заинтересованы в), подключи чтобы вернуться в [1], чтобы получить максимальный и минимальный х.

Повторите [2]:

0 = dy/dt = b*cos(t)*cos(phi) - a*sin(t)*sin(phi) 

=>

tan(t) = b*cot(phi)/a [4] 

Позволяет попробовать пример:

Рассмотрим эллипс в точке (0,0) при а = 2 , b = 1, повернутый на PI/4:

[1] =>

x = 2*cos(t)*cos(PI/4) - sin(t)*sin(PI/4) 

[3] =>

tan(t) = -tan(PI/4)/2 = -1/2 

=>

t = -0.4636 + n*PI 

Мы заинтересованы в Т = -0,4636 и т = -3,6052

Таким образом, мы получаем:

x = 2*cos(-0.4636)*cos(PI/4) - sin(-0.4636)*sin(PI/4) = 1.5811 

и

x = 2*cos(-3.6052)*cos(PI/4) - sin(-3.6052)*sin(PI/4) = -1.5811 

Answer 2

Я думаю, что наиболее полезной формулой является этот. Многоточие поворачивается от угла Фи от начала координат имеет в качестве уравнения:

где (Н, К) является центром, а и б размера большой и малой оси и t изменяется от -pi до pi.

От того, вы должны быть в состоянии получить, для которых т йха/или д/д переходит в 0.

Answer 3

Это относительный простой, но немного трудно объяснить, так как вы не дали нам путь вы представляете эллипс. Существует так много способов сделать это.

В любом случае, общий принцип таков: вы не можете напрямую вычислить граничную рамку с осью. Однако вы можете рассчитать экстремумы эллипса по x и y как точки в 2D пространстве.

Для этого достаточно взять уравнение x (t) = эллипсовое уравнение (t) и y (t) = эллипсовое уравнение (t). Получите его первый порядок и решите его для своего корня. Поскольку мы имеем дело с эллипсами, которые основаны на тригонометрии, которая прямолинейна. Вы должны получить уравнение, которое либо получает корни через atan, acos или asin.

Подсказка: Чтобы проверить код, попробуйте его с помощью невращающегося эллипса: вы должны получить корни в 0, Pi/2, Pi и 3 * Pi/2.

Сделайте это для каждой оси (x и y). Вы получите максимум четыре корня (меньше, если ваш эллипс вырожден, например, один из радиусов равен нулю). Оцените позиции у корней, и вы получите все экстремальные точки эллипса.

Теперь вы почти у цели. Получение пограничного поля эллипса так же просто, как сканирование этих четырех точек для xmin, xmax, ymin и ymax.

Btw - если у вас есть проблемы с поиском уравнения вашего эллипса: попробуйте уменьшить его до случая, когда у вас есть ориентированный по оси эллипс с центром, двумя радиусами и углом поворота вокруг центра.

Если вы сделаете это уравнения становятся:

// the ellipse unrotated: 
    temp_x (t) = radius.x * cos(t); 
    temp_y (t) = radius.y = sin(t); 

    // the ellipse with rotation applied: 
    x(t) = temp_x(t) * cos(angle) - temp_y(t) * sin(angle) + center.x; 
    y(t) = temp_x(t) * sin(angle) + temp_y(t) * cos(angle) + center.y; 

Answer 4

Я нашел простую формулу в http://www.iquilezles.org/www/articles/ellipses/ellipses.htm (и игнорировали оси г).

Я реализовал это примерно так:

num ux = ellipse.r1 * cos(ellipse.phi); 
num uy = ellipse.r1 * sin(ellipse.phi); 
num vx = ellipse.r2 * cos(ellipse.phi+PI/2); 
num vy = ellipse.r2 * sin(ellipse.phi+PI/2); 

num bbox_halfwidth = sqrt(ux*ux + vx*vx); 
num bbox_halfheight = sqrt(uy*uy + vy*vy); 

Point bbox_ul_corner = new Point(ellipse.center.x - bbox_halfwidth, 
           ellipse.center.y - bbox_halfheight); 

Point bbox_br_corner = new Point(ellipse.center.x + bbox_halfwidth, 
           ellipse.center.y + bbox_halfheight); 

Answer 5

Этот код основан на коде user1789690 способствовало выше, но реализована в Delphi. Я тестировал это, и насколько я могу сказать, он работает отлично. Я целый день искал алгоритм или какой-то код, тестировал некоторые, которые не работали, и я был очень рад наконец найти код выше. Надеюсь, кто-то найдет это полезным. Этот код рассчитает ограничительную рамку повернутого эллипса. Ограничительная коробка ориентирована по оси и НЕ вращается с эллипсом. Радиусы для эллипса перед его вращением.

type 

    TSingleRect = record 
    X:  Single; 
    Y:  Single; 
    Width: Single; 
    Height: Single; 
    end; 

function GetBoundingBoxForRotatedEllipse(EllipseCenterX, EllipseCenterY, EllipseRadiusX, EllipseRadiusY, EllipseAngle: Single): TSingleRect; 
var 
    a: Single; 
    b: Single; 
    c: Single; 
    d: Single; 
begin 
    a := EllipseRadiusX * Cos(EllipseAngle); 
    b := EllipseRadiusY * Sin(EllipseAngle); 
    c := EllipseRadiusX * Sin(EllipseAngle); 
    d := EllipseRadiusY * Cos(EllipseAngle); 
    Result.Width := Hypot(a, b) * 2; 
    Result.Height := Hypot(c, d) * 2; 
    Result.X  := EllipseCenterX - Result.Width * 0.5; 
    Result.Y  := EllipseCenterY - Result.Height * 0.5; 
end; 

Answer 6

Вот формула для случая, если эллипс задается его фокусов и эксцентриситет (для случая, когда оно задается длиной оси, в центре и угол, см., Например. Ответ на user1789690).

А именно, если очаги (x0, y0) и (x1, y1) и эксцентриситета е, то

bbox_halfwidth = sqrt(k2*dx2 + (k2-1)*dy2)/2 
bbox_halfheight = sqrt((k2-1)*dx2 + k2*dy2)/2 

где

dx = x1-x0 
dy = y1-y0 
dx2 = dx*dx 
dy2 = dy*dy 
k2 = 1.0/(e*e) 

Я вывел формулы из ответа Пользователь1789690 и Йохан Нильссон.

Answer 7

Brilian Johan Nilsson. я переписал свой код на C# - ellipseAngle теперь в градусах:

private static RectangleF EllipseBoundingBox(int ellipseCenterX, int ellipseCenterY, int ellipseRadiusX, int ellipseRadiusY, double ellipseAngle) 
{ 
    double angle = ellipseAngle * Math.PI/180; 
    double a = ellipseRadiusX * Math.Cos(angle); 
    double b = ellipseRadiusY * Math.Sin(angle); 
    double c = ellipseRadiusX * Math.Sin(angle); 
    double d = ellipseRadiusY * Math.Cos(angle); 
    double width = Math.Sqrt(Math.Pow(a, 2) + Math.Pow(b, 2)) * 2; 
    double height = Math.Sqrt(Math.Pow(c, 2) + Math.Pow(d, 2)) * 2; 
    var x= ellipseCenterX - width * 0.5; 
    var y= ellipseCenterY + height * 0.5; 
    return new Rectangle((int)x, (int)y, (int)width, (int)height); 
} 

Answer 8

Это моя функция поиска плотно подходит прямоугольнику эллипса с произвольной ориентацией

У меня есть OpenCV прямоугольник и точка реализации:

CG - центр эллипса

размер - основная, малая ось эллипса

угла - ориентация эллипса

cv::Rect ellipse_bounding_box(const cv::Point2f &cg, const cv::Size2f &size, const float angle) { 

    float a = size.width/2; 
    float b = size.height/2; 
    cv::Point pts[4]; 

    float phi = angle * (CV_PI/180); 
    float tan_angle = tan(phi); 
    float t = atan((-b*tan_angle)/a); 
    float x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi); 
    float y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi); 
    pts[0] = cv::Point(cvRound(x), cvRound(y)); 

    t = atan((b*(1/tan(phi)))/a); 
    x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi); 
    y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi); 
    pts[1] = cv::Point(cvRound(x), cvRound(y)); 

    phi += CV_PI; 
    tan_angle = tan(phi); 
    t = atan((-b*tan_angle)/a); 
    x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi); 
    y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi); 
    pts[2] = cv::Point(cvRound(x), cvRound(y)); 

    t = atan((b*(1/tan(phi)))/a); 
    x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi); 
    y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi); 
    pts[3] = cv::Point(cvRound(x), cvRound(y)); 

    long left = 0xfffffff, top = 0xfffffff, right = 0, bottom = 0; 
    for (int i = 0; i < 4; i++) { 
     left = left < pts[i].x ? left : pts[i].x; 
     top = top < pts[i].y ? top : pts[i].y; 
     right = right > pts[i].x ? right : pts[i].x; 
     bottom = bottom > pts[i].y ? bottom : pts[i].y; 
    } 
    cv::Rect fit_rect(left, top, (right - left) + 1, (bottom - top) + 1); 
    return fit_rect; 
} 

Answer 9

Если вы работаете с OpenCV/C++ и использовать cv::fitEllipse(..) функции, возможно, потребуется ограничивающим прямоугольник эллипса. Здесь я сделал решение, используя ответ Майка:

// tau = 2 * pi, see tau manifest 
const double TAU = 2 * std::acos(-1); 

cv::Rect calcEllipseBoundingBox(const cv::RotatedRect &anEllipse) 
{ 
    if (std::fmod(std::abs(anEllipse.angle), 90.0) <= 0.01) { 
     return anEllipse.boundingRect(); 
    } 

    double phi = anEllipse.angle * TAU/360; 
    double major = anEllipse.size.width/2.0; 
    double minor = anEllipse.size.height/2.0; 

    if (minor > major) { 
     std::swap(minor, major); 
     phi += TAU/4; 
    } 

    double cosPhi = std::cos(phi), sinPhi = std::sin(phi); 
    double tanPhi = sinPhi/cosPhi; 

    double tx = std::atan(-minor * tanPhi/major); 
    cv::Vec2d eqx{ major * cosPhi, - minor * sinPhi }; 
    double x1 = eqx.dot({ std::cos(tx),   std::sin(tx)   }); 
    double x2 = eqx.dot({ std::cos(tx + TAU/2), std::sin(tx + TAU/2) }); 

    double ty = std::atan(minor/(major * tanPhi)); 
    cv::Vec2d eqy{ major * sinPhi, minor * cosPhi }; 
    double y1 = eqy.dot({ std::cos(ty),   std::sin(ty)   }); 
    double y2 = eqy.dot({ std::cos(ty + TAU/2), std::sin(ty + TAU/2) }); 

    cv::Rect_<float> bb{ 
     cv::Point2f(std::min(x1, x2), std::min(y1, y2)), 
     cv::Point2f(std::max(x1, x2), std::max(y1, y2)) 
    }; 

    return bb + anEllipse.center; 
}