Подтвердить что ты не робот

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

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 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]

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

Повторите для [2]:

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

= > 

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

Давайте попробуем пример:

Рассмотрим эллипс в точке (0,0) с a = 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

Нас интересует t = -0.4636 и t = -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

Ответ 2

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

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

Для этого достаточно взять уравнение x (t) = эллипсовое уравнение (t) и y (t) = эллипсовое уравнение (t). Получите его первый порядок и решите его для него root. Поскольку мы имеем дело с эллипсами, которые основаны на тригонометрии, которые прямолинейны. Вы должны получить уравнение, которое либо получает корни через 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;

Ответ 3

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

Я применил его примерно так:

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

Ответ 4

Брилиан Йохан Нильссон. Я переписал ваш код на С# - 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);
}

Ответ 5

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

alt text

alt text

где (h, k) - центр, a и b размер главной и вспомогательной оси и t изменяется от -pi до pi.

Из этого вы должны получить вывод, для которого t dx/dt или dy/dt переходит в 0.

Ответ 6

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

А именно, если фокусы (x0, y0) и (x1, y1), а эксцентриситет - e, то

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 и Йохана Нильсона.

Ответ 7

Если вы работаете с OpenCV/С++ и используете функцию 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;
}

Ответ 8

Этот код основан на коде 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;

Ответ 9

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

У меня есть opencv rect и точка для реализации:

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

size - основная, вспомогательная ось эллипса

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

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