كيف يمكنك حساب المربع المحيط بمحاذاة المحور للقطع الناقص؟

Question

إذا كان المحور الرئيسي للقطع الناقص عموديًا أو أفقيًا، فمن السهل حساب المربع المحيط، ولكن ماذا عن وقت تدوير القطع الناقص؟

الطريقة الوحيدة التي يمكنني التفكير بها حتى الآن هي حساب جميع النقاط المحيطة بالمحيط والعثور على قيمتي الحد الأقصى/الدقيقة 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]

والتي من شأنها أن توفر لك العديد من الحلول لـ t (اثنين منها أنت مهتم بهما)، قم بتوصيل ذلك مرة أخرى في [1] للحصول على الحد الأقصى والحد الأدنى x.

كرر ل[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

Answer 2

لقد وجدت صيغة بسيطة في 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 3

هذا أمر بسيط نسبيًا ولكن من الصعب شرحه لأنك لم تقدم لنا الطريقة التي تمثل بها الشكل الناقص.هناك الكثير من الطرق للقيام بذلك..

على كل حال المبدأ العام كالتالي:لا يمكنك حساب مربع الحدود المحاذي للمحور مباشرة.ومع ذلك، يمكنك حساب الحد الأقصى للقطع الناقص في x وy كنقاط في مساحة ثنائية الأبعاد.

لهذا يكفي أن نأخذ المعادلة x(t) = ellipse_equation(t) و y(t) = ellipse_equation(t).احصل على المشتق الأول منه وحله لجذره.نظرًا لأننا نتعامل مع الأشكال الناقصية التي تعتمد على علم المثلثات، فهذا أمر مستقيم للأمام.يجب أن ينتهي بك الأمر بمعادلة تحصل على الجذور عبر آتان أو أكوس أو آسين.

تَلمِيح:للتحقق من الكود الخاص بك، جربه باستخدام شكل بيضاوي غير مستدير:يجب أن تحصل على الجذور عند 0 وPi/2 وPi و3*Pi/2.

افعل ذلك لكل محور (x و y).سوف تحصل على أربعة جذور على الأكثر (أقل إذا كان القطع الناقص لديك متدهورًا، على سبيل المثال.واحد من نصف القطر هو صفر).قم بتقييم المواضع عند الجذور وستحصل على جميع النقاط القصوى للقطع الناقص.

الآن أنت تقريبًا هناك.يعد الحصول على المربع الحدودي للقطع الناقص أمرًا بسيطًا مثل مسح هذه النقاط الأربع بحثًا عن xmin وxmax وymin وymax.

راجع للشغل - إذا كان لديك مشاكل في العثور على معادلة القطع الناقص الخاص بك:حاول تقليله إلى الحالة التي يكون فيها لديك محورًا بيضاويًا محاذيًا بمركز ونصف قطر وزاوية دوران حول المركز.

إذا قمت بذلك تصبح المعادلات:

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

بريليان يوهان نيلسون.لقد قمت بنسخ التعليمات البرمجية الخاصة بك إلى 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 5

أعتقد أن الصيغة الأكثر فائدة هي هذه.القطع الناقص الذي يتم تدويره من زاوية phi من الأصل له معادلة:

حيث (h,k) هو المركز، وa وb حجم المحور الرئيسي والثانوي وt يختلف من -pi إلى pi.

من ذلك، يجب أن تكون قادرًا على استخلاص أي قيمة t dx/dt أو dy/dt تساوي 0.

Answer 6

هنا هي صيغة الحالة إذا تم إعطاء القطع الناقص بواسطة البؤر والانحراف (بالنسبة للحالة التي يتم فيها إعطاء أطوال المحور والمركز والزاوية، انظر e.ز.الجواب بواسطة user1789690).

أي إذا كانت البؤرتان (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 ويوهان نيلسون.

Answer 7

إذا كنت تعمل مع 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;
}

Answer 8

يعتمد هذا الكود على الكود الذي ساهم به user1789690 أعلاه، ولكن تم تنفيذه في دلفي.لقد اختبرت هذا وبقدر ما أستطيع أن أقول أنه يعمل بشكل مثالي.لقد أمضيت يومًا كاملاً في البحث عن خوارزمية أو بعض التعليمات البرمجية، واختبرت بعضها الذي لم ينجح، وكنت سعيدًا جدًا بالعثور أخيرًا على الكود أعلاه.آمل أن يجد شخص ما هذا مفيدًا.سيقوم هذا الكود بحساب المربع المحيط للقطع الناقص الذي تم تدويره.المربع المحيط محاذي للمحور ولا يتم تدويره مع القطع الناقص.نصف القطر مخصص للقطع الناقص قبل تدويره.

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 9

هذه هي وظيفتي في العثور على مستطيل محكم الشكل للقطع الناقص باتجاه عشوائي

لدي opencv rect ونقطة للتنفيذ:

الفريق الاستشاري - مركز القطع الناقص

الحجم - المحور الرئيسي والثانوي للقطع الناقص

الزاوية - اتجاه القطع الناقص

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