حساب مساحة التقاطع بين دائرة ومثلث؟

Question

كيف يحسب المرء مساحة تقاطع بين المثلث (المحدد كأزواج ثلاثة (س (س، ذ) ودائرة (X، Y، R)؟ لقد فعلت بعض البحث دون جدوى. هذا للعمل، وليس المدرسة. :)

سوف تبدو مثل هذا في C #:

struct { PointF vert[3]; } Triangle;
struct { PointF center; float radius; } Circle;

// returns the area of intersection, e.g.:
// if the circle contains the triangle, return area of triangle
// if the triangle contains the circle, return area of circle
// if partial intersection, figure that out
// if no intersection, return 0
double AreaOfIntersection(Triangle t, Circle c)
{
 ...
}

Answer 1

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

أحسب تسع حالات مختلفة (صنفت في الشكل أدناه من خلال عدد رؤوس المثلث داخل الدائرة، وعدد حواف المثلث الذي يتقاطع أو الوارد في الدائرة):

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

لذلك النهج هو:

1. تحديد كل قمة من المثلث إذا كان داخل الدائرة. سأفترض أنك تعرف كيف تفعل ذلك.

2. تحديد كل حافة من المثلث إذا تتقاطع الدائرة. (كتبت طريقة واحدة هنا, ، أو انظر أي كتاب هندسة حسابية.) ستحتاج إلى حساب نقطة أو نقاط التقاطع (إن وجدت) للاستخدام في الخطوة 4.

3. تحديد أي من الحالات التسعة لديك.

4. حساب مساحة التقاطع. الحالات 1، 2، و 9 هي سهلة. في الحالات الست المتبقية التي رسمتها خطوط متقطعة لإظهار كيفية تقسيم مساحة التقاطع في مثلثات شرائح دائرية بناء على القمم الأصلية للمثلث، وعلى نقاط التقاطع التي قمت بحسابها في الخطوة 2.

ستكون هذه الخوارزمية حساسة إلى حد ما وغير عرضة للأخطاء التي تؤثر فقط على واحدة من الحالات، لذلك تأكد من أن لديك حالات اختبار تغطي جميع الحالات التسعة (وأنا أقترح تصوير رؤوس مثلثات الاختبار أيضا). إيلاء اهتمام خاص للحالات التي يكون فيها أحد رؤوس المثلث على حافة الدائرة.

إذا لم تكن بحاجة إلى حل دقيق، فإن إعادة تنقيط الأرقام وعسق البكسل في التقاطع (كما اقترح من قبل اثنين من المشاركين الآخرين) يبدو وكأنه نهج أسهل بكثير في التعليمات البرمجية، وأقل عرضة للأخطاء.

Answer 2

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

كيفية العثور على مساحة المضلع

دعونا نلقي نظرة على حالة مثلث، لأن كل المنطق الأساسي يظهر هناك. دعونا نفترض أن لدينا مثلث مع رؤوس (x1، y1)، (x2، y2)، و (x3، y3) كما تذهب حول المثلث عكس عقارب الساعة، كما هو موضح في الشكل التالي:

ثم يمكنك حساب المنطقة من الصيغة

A = (X1 Y2 + X2 Y3 + X3 Y1 - X2Y1- X3 Y2 - X1Y3) / 2.

لمعرفة سبب عمل هذه الصيغة، دعونا إعادة ترتيبها لذلك في النموذج

a = (x1 y2 - x2 y1) / 2 + (x2 y3 - x3 y2) / 2 + (x3 y1 - x1y3) / 2.

الآن المصطلح الأول هو المنطقة التالية، والتي هي إيجابية في قضيتنا:

إذا لم يكن من الواضح أن منطقة المنطقة الخضراء هي بالفعل (X1 Y2 - X2 Y1) / 2، ثم اقرأ هذه.

المصطلح الثاني هو هذه المنطقة، وهو إيجابي مرة أخرى:

وتظهر المنطقة الثالثة في الشكل التالي. هذه المرة تقع المنطقة سلبية

إضافة هذه الثلاثة حتى نحصل على الصورة التالية

نرى أن المنطقة الخضراء التي كانت خارج المثلث تم إلغاؤها من قبل المنطقة الحمراء، بحيث تكون المنطقة الصافية هي مجرد منطقة المثلث، وهذا يدل على سبب وجود صيغةنا صحيحة في هذه الحالة.

ما قلته أعلاه كان التفسير البديهي لماذا كانت صيغة المنطقة صحيحة. سيكون شرحا أكثر صرامة هو مراعاة أنه عندما نحسب المنطقة من الحافة، فإن المنطقة التي نحصل عليها هي نفس المنطقة التي سنحصل عليها من التكامل r ^ 2dθ / 2، لذلك نحن ندمج بشكل فعال r ^ 2dθ / 2 حول الحدود من المضلع، وعن طريق Stokes Theorem، هذا يعطي نفس النتيجة كدمج RDRDθ على المنطقة التي يحدها المضلع. نظرا لأن دمج RDRDθ على المنطقة التي يحدها المضلع تعطي المنطقة، نستنتج أن إجراءنا يجب أن يعطي المنطقة بشكل صحيح.

مساحة تقاطع دائرة مع مضلع

الآن دعونا نناقش كيفية العثور على منطقة تقاطع دائرة من دائرة نصف قطرها r مع مضلع كما عرض في الشكل التالي:

نحن مهتمون بإيجاد منطقة المنطقة الخضراء. يجوز لنا، كما هو الحال في مضلع واحد، كسر حسابنا إلى العثور على منطقة لكل جانب من مضلع، ثم تضاف تلك المجالات.

ستبدو أول منطقتنا:

سوف تبدو المنطقة الثانية

والمنطقة الثالثة ستكون

مرة أخرى، أول مجاري إيجابية في حالتنا بينما سيكون الثالث سالبا. نأمل أن تعمل الإلغاء بحيث تكون المنطقة الصافية في الواقع المنطقة التي نهمها. دعونا نرى.

في الواقع، سيكون مجموع المناطق منطقة مهتمين به.

مرة أخرى، يمكننا تقديم شرح أكثر صرامة لماذا هذا يعمل. اسمحوا لي أن أكون المنطقة المحددة من قبل التقاطع وترك P يكون المضلع. ثم من المناقشة السابقة، نعلم أننا نريد أن نريد الكمبيوتر جزء لا يتجزأ من R ^ 2Dθ / 2 حول حدود I. ومع ذلك، فإن هذا يصعب القيام به لأنه يتطلب إيجاد تقاطع.

بدلا من ذلك، فعلنا جزءا لا يتجزأ عبر المضلع. نحن مدمج كحد أقصى (ص، ص) ^ 2 Dθ / 2 على حدود المضلع. لمعرفة لماذا يمنح هذا الإجابة الصحيحة، دعنا نحدد وظيفة π التي تأخذ نقطة الإحداثيات القطبية (R، θ) إلى هذه النقطة (Max (R، R)، θ). لا ينبغي أن يكون مربكا للإشارة إلى وظائف الإحداثيات الخاصة ب π (r) = Max (r، r) و π (θ) = θ. ثم ما فعلناه هو دمج π (r) ^ 2 dθ / 2 على حدود المضلع.

من ناحية أخرى منذ π (θ) = θ، هذا هو نفسه دمج π (r) ^ 2 dπ (θ) / 2 على حدود المضلع.

الآن القيام بتغيير المتغير، نجد أننا سنحصل على نفس الإجابة إذا تم دمجنا r ^ 2 dθ / 2 على حدود π (p)، حيث π (p) هي صورة p تحت π.

باستخدام Tokes Theorem مرة أخرى نحن نعرف أن دمج r ^ 2 dθ / 2 على حدود π (p) يعطينا مساحة π (p). بمعنى آخر، يعطي نفس الإجابة كدمج DXDY على π (P).

باستخدام تغيير المتغير مرة أخرى، نعلم أن دمج DXDY على π (P) هو نفس دمج JDXDY على P، حيث ي هو J هو Jacobian π.

الآن يمكننا تقسيم جزء من JDXDY إلى منطقتين: الجزء في الدائرة والجزء خارج الدائرة. الآن يترك النقاط في الدائرة وحدها لذا J = 1 هناك، لذلك فإن المساهمة من هذا الجزء من P هي مجال جزء من P الذي يكمن في الدائرة أي، مساحة التقاطع. المنطقة الثانية هي المنطقة خارج الدائرة. هناك J = 0 منذ انه ينهار هذا الجزء إلى حدود الدائرة.

وبالتالي ما نحسبه هو في الواقع مساحة التقاطع.

الآن بعد أن نعرف نسبيا نعلم عن المفاهيم كيفية العثور على المنطقة، دعونا نتحدث أكثر تحديدا حول كيفية حساب المساهمة من شريحة واحدة. لنبدأ بالنظر إلى شريحة في ما سأتصل به "الهندسة القياسية". يظهر أدناه.

في الهندسة القياسية، تذهب الحافة أفقيا من اليسار إلى اليمين. ويوصفها ثلاثة أرقام: XI، تنسيق X حيث يبدأ الحافة، XF، الإحداثيات X حيث ينتهي الحافة، و Y، تنسيق y من الحافة.

الآن نرى ذلك إذا كانت | ذ | <ص، كما هو الحال في الشكل، ثم تتقاطع الحافة الدائرة في النقاط (-xint، y) و (xint، y) حيث xint = (r ^ 2-y ^ 2) ^ (1/2). ثم المنطقة التي نحتاج إلى حسابها مكسورة إلى ثلاث قطع المسمى في الشكل. للحصول على مناطق المناطق 1 و 3، يمكننا استخدام ARCTAN للحصول على زوايا النقاط المختلفة ثم تساوي المنطقة إلى R ^ 2 θθ / 2. لذلك على سبيل المثال، سنقوم بتعيين θi = atan2 (y، xi) و θl = atan2 (y، -xint). ثم مساحة المنطقة واحدة هي R ^ 2 (θl-θi) / 2. يمكننا الحصول على مساحة المنطقة 3 بالمثل.

مساحة المنطقة 2 هي مجرد منطقة مثلث. ومع ذلك، يجب أن نكون حذرين في الإشارة. نريد أن تكون المنطقة إيجابية لذلك سنقول المنطقة - (Xint - (-xint)) Y / 2.

شيء آخر يجب مراعاته هو أنه بشكل عام، لا يجب أن يكون XI أقل من -xint و XF أكبر من Xint.

الحالة الأخرى للنظر هي | ذ | > R. هذه الحالة أبسط، لأن هناك قطعة واحدة فقط مماثلة لمنطقة 1 في الشكل.

الآن بعد أن نعرف كيفية حساب المنطقة من حافة في الهندسة القياسية، فإن الشيء الوحيد الذي ترك القيام به هو وصف كيفية تحويل أي حافة إلى هندسة قياسية.

ولكن هذا مجرد تغيير بسيط للإحداثيات. نظرا لبعض مع Vertex VI الأولي و Final Vertex VF، سيكون متجه وحدة X الجديد هو متجه الوحدة الذي يشير إلى VI إلى VF. ثم XI هو مجرد نزوح السادس من مركز الدائرة المنقط في x، و XF هو فقط XI بالإضافة إلى المسافة بين السادس و VF. وفي الوقت نفسه، يعطى Y من قبل منتج إسفين من X مع نزوح السادس من وسط الدائرة.

رمز

الذي يكمل وصف الخوارزمية، الآن حان الوقت لكتابة بعض التعليمات البرمجية. سوف تستخدم جافا.

أولا، لأننا نعمل مع دوائر، يجب أن يكون لدينا فئة دائرة

public class Circle {

    final Point2D center;
    final double radius;

    public Circle(double x, double y, double radius) {
        center = new Point2D.Double(x, y);
        this.radius = radius;
    }

    public Circle(Point2D.Double center, double radius) {
        this(center.getX(), center.getY(), radius);
    }

    public Point2D getCenter() {
        return new Point2D.Double(getCenterX(), getCenterY());
    }

    public double getCenterX() {
        return center.getX();
    }

    public double getCenterY() {
        return center.getY();
    }

    public double getRadius() {
        return radius;
    }

}

للحصول على مضلعات، سأستخدم جافا Shape صف دراسي. Shapes have PathIterator أنه يمكنني استخدامه للتكرار من خلال حواف المضلع.

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

لذلك لدي فئة عامة يحسب بعض الممتلكات من الفصل T حول تقاطع دائرة المضلع لدينا.

public abstract class CircleShapeIntersectionFinder<T> {

لديها ثلاث طرق ثابتة تساعد فقط في حساب الهندسة:

private static double[] displacment2D(final double[] initialPoint, final double[] finalPoint) {
    return new double[]{finalPoint[0] - initialPoint[0], finalPoint[1] - initialPoint[1]};
}

private static double wedgeProduct2D(final double[] firstFactor, final double[] secondFactor) {
    return firstFactor[0] * secondFactor[1] - firstFactor[1] * secondFactor[0];
}

static private double dotProduct2D(final double[] firstFactor, final double[] secondFactor) {
    return firstFactor[0] * secondFactor[0] + firstFactor[1] * secondFactor[1];
}

هناك طريقان مثيل، أ Circle الذي يحتفظ فقط نسخة من الدائرة، و currentSquareRadius, ، والتي تحافظ على نسخة من دائرة نصف قطرها المربع. قد يبدو هذا غريبا، لكن الفصل الذي أستخدمه هو مجهز بالفعل للعثور على مناطق مجموعة كاملة من تقاطعات المضللة. هذا هو السبب في أنني أشير إلى إحدى الدوائر "الحالية".

private Circle currentCircle;
private double currentSquareRadius;

التالي يأتي طريقة الحوسبة ما نريد حسابه:

public final T computeValue(Circle circle, Shape shape) {
    initialize();
    processCircleShape(circle, shape);
    return getValue();
}

initialize() و getValue() هي مجردة. initialize() من شأنه تعيين المتغير الذي يحتفظ بمجموع المنطقة إلى الصفر، و getValue() سوف تعيد فقط المنطقة. التعريف ل processCircleShape يكون

private void processCircleShape(Circle circle, final Shape cellBoundaryPolygon) {
    initializeForNewCirclePrivate(circle);
    if (cellBoundaryPolygon == null) {
        return;
    }
    PathIterator boundaryPathIterator = cellBoundaryPolygon.getPathIterator(null);
    double[] firstVertex = new double[2];
    double[] oldVertex = new double[2];
    double[] newVertex = new double[2];
    int segmentType = boundaryPathIterator.currentSegment(firstVertex);
    if (segmentType != PathIterator.SEG_MOVETO) {
        throw new AssertionError();
    }
    System.arraycopy(firstVertex, 0, newVertex, 0, 2);
    boundaryPathIterator.next();
    System.arraycopy(newVertex, 0, oldVertex, 0, 2);
    segmentType = boundaryPathIterator.currentSegment(newVertex);
    while (segmentType != PathIterator.SEG_CLOSE) {
        processSegment(oldVertex, newVertex);
        boundaryPathIterator.next();
        System.arraycopy(newVertex, 0, oldVertex, 0, 2);
        segmentType = boundaryPathIterator.currentSegment(newVertex);
    }
    processSegment(newVertex, firstVertex);
}

دعونا نأخذ ثانية للنظر في initializeForNewCirclePrivate بسرعة. تضع هذه الطريقة فقط حقول المثيل وتسمح للفئة المشتقة بتخزين أي خاصية للدائرة. التعريف الخاص به هو

private void initializeForNewCirclePrivate(Circle circle) {
    currentCircle = circle;
    currentSquareRadius = currentCircle.getRadius() * currentCircle.getRadius();
    initializeForNewCircle(circle);
}

initializeForNewCircle هو مجردة وتنفيذ واحد سيكون لتخزين دائرة نصف قطرها الدوائر لتجنب الاضطرار إلى القيام جذور مربعة. على أي حال العودة إلى processCircleShape. وبعد بعد الاتصال initializeForNewCirclePrivate, ، نتحقق مما إذا كان المضلع null (الذي أنا أفسد كضغط فارغ)، ونحن نعود إذا كان كذلك null. وبعد في هذه الحالة، ستكون المنطقة المحسوبة لدينا صفر. إذا كان المضلع ليس كذلك null ثم نحصل على PathIterator من المضلع. الحجة إلى getPathIterator الطريقة الأولى استدعاء هي تحول أفيركي يمكن تطبيقه على المسار. لا أريد تطبيق واحد رغم ذلك، لذلك أنا فقط تمر null.

التالي أعلن double[]التي سوف تتبع القمم. يجب أن أتذكر أول قمة لأن PathIterator فقط يعطيني كل قمة مرة واحدة، لذلك يجب أن أعود بعد أن أعطتني آخر قمة، وتشكيل حافة مع هذه القمة الأخيرة وقمة الأولى.

ال currentSegment الطريقة في السطر التالي تضع قمة الرأس التالية في حجةها. إرجاع رمز يخبرك عندما يكون خارج القمم. هذا هو السبب في أن تعبير التحكم عن حلقة بلدي في حين هو ما هو عليه.

معظم بقية رمز هذه الطريقة هو المنطق غير المتشابهين متعلقة بالتكرار من خلال القمم. الشيء المهم هو أنه بمجرد استدعاء الحلقة أثناء ذلك processSegment ثم اتصل processSegment مرة أخرى في نهاية الطريقة لمعالجة الحافة التي توصل آخر قمة إلى أعلى قمة.

دعونا نلقي نظرة على الرمز ل processSegment:

private void processSegment(double[] initialVertex, double[] finalVertex) {
    double[] segmentDisplacement = displacment2D(initialVertex, finalVertex);
    if (segmentDisplacement[0] == 0 && segmentDisplacement[1] == 0) {
        return;
    }
    double segmentLength = Math.sqrt(dotProduct2D(segmentDisplacement, segmentDisplacement));
    double[] centerToInitialDisplacement = new double[]{initialVertex[0] - getCurrentCircle().getCenterX(), initialVertex[1] - getCurrentCircle().getCenterY()};
    final double leftX = dotProduct2D(centerToInitialDisplacement, segmentDisplacement) / segmentLength;
    final double rightX = leftX + segmentLength;
    final double y = wedgeProduct2D(segmentDisplacement, centerToInitialDisplacement) / segmentLength;
    processSegmentStandardGeometry(leftX, rightX, y);
}

في هذه الطريقة، أقوم بتطبيق الخطوات لتحويل الحافة إلى الهندسة القياسية كما هو موضح أعلاه. أولا أنا حساب segmentDisplacement, ، النزوح من قمة الرأس الأولي إلى قمة الرأس النهائية. هذا يحدد المحور X من الهندسة القياسية. أفعل عودة مبكرة إذا كان هذا النزوح صفر.

بعد ذلك، أحسب طول النزوح، لأن هذا ضروري للحصول على ناقلات وحدة X. بمجرد أن يكون لدي هذه المعلومات، أحسب النزوح من مركز الدائرة إلى قمة الرأس الأولي. المنتج نقطة من هذا مع segmentDisplacement يعطيني leftX التي كنت أتصل xi. ثم rightX, ، الذي كنت أتصل XF، هو فقط leftX + segmentLength. وبعد أخيرا أفعل منتج إسفين للحصول على y كما هو موضح أعلاه.

الآن بعد أن تحولت المشكلة إلى الهندسة القياسية، سيكون من السهل التعامل معها. هذا هو ما processSegmentStandardGeometry طريقة لا. دعونا نلقي نظرة على الرمز

private void processSegmentStandardGeometry(double leftX, double rightX, double y) {
    if (y * y > getCurrentSquareRadius()) {
        processNonIntersectingRegion(leftX, rightX, y);
    } else {
        final double intersectionX = Math.sqrt(getCurrentSquareRadius() - y * y);
        if (leftX < -intersectionX) {
            final double leftRegionRightEndpoint = Math.min(-intersectionX, rightX);
            processNonIntersectingRegion(leftX, leftRegionRightEndpoint, y);
        }
        if (intersectionX < rightX) {
            final double rightRegionLeftEndpoint = Math.max(intersectionX, leftX);
            processNonIntersectingRegion(rightRegionLeftEndpoint, rightX, y);
        }
        final double middleRegionLeftEndpoint = Math.max(-intersectionX, leftX);
        final double middleRegionRightEndpoint = Math.min(intersectionX, rightX);
        final double middleRegionLength = Math.max(middleRegionRightEndpoint - middleRegionLeftEndpoint, 0);
        processIntersectingRegion(middleRegionLength, y);
    }
}

الأول if يميز الحالات التي y صغير بما فيه الكفاية أن الحافة قد تتقاطع الدائرة. إذا y كبير وليس هناك أي إمكانية للتقاطع، ثم استدعاء الطريقة للتعامل مع هذه الحالة. وإلا فإنني أتعامل مع القضية التي تكون فيها التقاطع ممكنة.

إذا كان التقاطع ممكنا، أحسب التنسيق X من التقاطع، intersectionX, وأنا أقسم الحافة حتى ثلاث أجزاء تتوافق مع المناطق 1 و 2 و 3 من رقم الهندسة القياسية أعلاه. أولا أتعامل مع المنطقة 1.

للتعامل مع المنطقة 1، أتحقق مما إذا leftX هو في الواقع أقل من -intersectionX وإلا فلن تكون هناك منطقة 1. إذا كانت هناك منطقة 1، فأنا بحاجة إلى معرفة متى ينتهي. ينتهي في الحد الأدنى rightX و -intersectionX. وبعد بعد أن وجدت هذه الإحداثيات X، أتعامل مع هذه المنطقة غير تقاطع.

أنا أفعل شيء مماثل للتعامل مع المنطقة 3.

للمنطقة 2، يجب أن أفعل بعض المنطق للتحقق من ذلك leftX و rightX هل بالفعل قوس بعض المنطقة بين -intersectionX و intersectionX. وبعد بعد العثور على المنطقة، أحتاج فقط إلى طول المنطقة و y, ، لذلك اجتاز هذين الأرقامين إلى طريقة مجردة تتعامل مع المنطقة 2.

الآن دعونا نلقي نظرة على الرمز ل processNonIntersectingRegion

private void processNonIntersectingRegion(double leftX, double rightX, double y) {
    final double initialTheta = Math.atan2(y, leftX);
    final double finalTheta = Math.atan2(y, rightX);
    double deltaTheta = finalTheta - initialTheta;
    if (deltaTheta < -Math.PI) {
        deltaTheta += 2 * Math.PI;
    } else if (deltaTheta > Math.PI) {
        deltaTheta -= 2 * Math.PI;
    }
    processNonIntersectingRegion(deltaTheta);
}

أنا ببساطة استخدام atan2 لحساب الفرق في زاوية بين leftX و rightX. وبعد ثم أضف رمز للتعامل مع التوقف في atan2, ، ربما هذا ربما غير ضروري، لأن الانقطاع يحدث إما عند 180 درجة أو 0 درجة. ثم اجتاز الفرق في زاوية على طريقة مجردة. أخيرا لدينا فقط طرق مجردة وآجيلة:

    protected abstract void initialize();

    protected abstract void initializeForNewCircle(Circle circle);

    protected abstract void processNonIntersectingRegion(double deltaTheta);

    protected abstract void processIntersectingRegion(double length, double y);

    protected abstract T getValue();

    protected final Circle getCurrentCircle() {
        return currentCircle;
    }

    protected final double getCurrentSquareRadius() {
        return currentSquareRadius;
    }

}

الآن دعونا ننظر إلى الطبقة التمديد، CircleAreaFinder

public class CircleAreaFinder extends CircleShapeIntersectionFinder<Double> {

public static double findAreaOfCircle(Circle circle, Shape shape) {
    CircleAreaFinder circleAreaFinder = new CircleAreaFinder();
    return circleAreaFinder.computeValue(circle, shape);
}

double area;

@Override
protected void initialize() {
    area = 0;
}

@Override
protected void processNonIntersectingRegion(double deltaTheta) {
    area += getCurrentSquareRadius() * deltaTheta / 2;
}

@Override
protected void processIntersectingRegion(double length, double y) {
    area -= length * y / 2;
}

@Override
protected Double getValue() {
    return area;
}

@Override
protected void initializeForNewCircle(Circle circle) {

}

}

لديها مجال area لتتبع المنطقة. initialize يحدد مساحة إلى الصفر، كما هو متوقع. عندما نقوم بمعالجة حافة غير متقيمة، فإننا نزيد من المنطقة عن طريق R ^ 2 θθ / 2 كما خلصنا إلى أننا يجب علينا أعلاه. للحصول على حافة تقاطع، ونحن نسين المنطقة y*length/2. وبعد كان هذا بحيث القيم السلبية ل y تتوافق مع المناطق الإيجابية، كما قررنا أنهم يجب عليهم.

الآن الشيء الأنيق هو إذا كنا نريد تتبع المحيط، فلا يجب علينا القيام بهذا العمل أكثر بكثير. أنا أعرف an. AreaPerimeter صف دراسي:

public class AreaPerimeter {

    final double area;
    final double perimeter;

    public AreaPerimeter(double area, double perimeter) {
        this.area = area;
        this.perimeter = perimeter;
    }

    public double getArea() {
        return area;
    }

    public double getPerimeter() {
        return perimeter;
    }

}

والآن نحتاج فقط إلى تمديد فئة مجردة لدينا مرة أخرى باستخدام AreaPerimeter كما النوع.

public class CircleAreaPerimeterFinder extends CircleShapeIntersectionFinder<AreaPerimeter> {

    public static AreaPerimeter findAreaPerimeterOfCircle(Circle circle, Shape shape) {
        CircleAreaPerimeterFinder circleAreaPerimeterFinder = new CircleAreaPerimeterFinder();
        return circleAreaPerimeterFinder.computeValue(circle, shape);
    }

    double perimeter;
    double radius;
    CircleAreaFinder circleAreaFinder;

    @Override
    protected void initialize() {
        perimeter = 0;
        circleAreaFinder = new CircleAreaFinder();
    }

    @Override
    protected void initializeForNewCircle(Circle circle) {
        radius = Math.sqrt(getCurrentSquareRadius());
    }

    @Override
    protected void processNonIntersectingRegion(double deltaTheta) {
        perimeter += deltaTheta * radius;
        circleAreaFinder.processNonIntersectingRegion(deltaTheta);
    }

    @Override
    protected void processIntersectingRegion(double length, double y) {
        perimeter += Math.abs(length);
        circleAreaFinder.processIntersectingRegion(length, y);
    }

    @Override
    protected AreaPerimeter getValue() {
        return new AreaPerimeter(circleAreaFinder.getValue(), perimeter);
    }

}

لدينا متغير perimeter لتتبع المحيط، نتذكر قيمة radius لتجنب الاتصال Math.sqrt كثيرا، ونحن تفوض حساب المنطقة لدينا CircleAreaFinder. وبعد يمكننا أن نرى أن الصيغ للمحيط سهلة.

للإشارة هنا هو رمز كامل لل CircleShapeIntersectionFinder

private static double[] displacment2D(final double[] initialPoint, final double[] finalPoint) {
        return new double[]{finalPoint[0] - initialPoint[0], finalPoint[1] - initialPoint[1]};
    }

    private static double wedgeProduct2D(final double[] firstFactor, final double[] secondFactor) {
        return firstFactor[0] * secondFactor[1] - firstFactor[1] * secondFactor[0];
    }

    static private double dotProduct2D(final double[] firstFactor, final double[] secondFactor) {
        return firstFactor[0] * secondFactor[0] + firstFactor[1] * secondFactor[1];
    }

    private Circle currentCircle;
    private double currentSquareRadius;

    public final T computeValue(Circle circle, Shape shape) {
        initialize();
        processCircleShape(circle, shape);
        return getValue();
    }

    private void processCircleShape(Circle circle, final Shape cellBoundaryPolygon) {
        initializeForNewCirclePrivate(circle);
        if (cellBoundaryPolygon == null) {
            return;
        }
        PathIterator boundaryPathIterator = cellBoundaryPolygon.getPathIterator(null);
        double[] firstVertex = new double[2];
        double[] oldVertex = new double[2];
        double[] newVertex = new double[2];
        int segmentType = boundaryPathIterator.currentSegment(firstVertex);
        if (segmentType != PathIterator.SEG_MOVETO) {
            throw new AssertionError();
        }
        System.arraycopy(firstVertex, 0, newVertex, 0, 2);
        boundaryPathIterator.next();
        System.arraycopy(newVertex, 0, oldVertex, 0, 2);
        segmentType = boundaryPathIterator.currentSegment(newVertex);
        while (segmentType != PathIterator.SEG_CLOSE) {
            processSegment(oldVertex, newVertex);
            boundaryPathIterator.next();
            System.arraycopy(newVertex, 0, oldVertex, 0, 2);
            segmentType = boundaryPathIterator.currentSegment(newVertex);
        }
        processSegment(newVertex, firstVertex);
    }

    private void initializeForNewCirclePrivate(Circle circle) {
        currentCircle = circle;
        currentSquareRadius = currentCircle.getRadius() * currentCircle.getRadius();
        initializeForNewCircle(circle);
    }

    private void processSegment(double[] initialVertex, double[] finalVertex) {
        double[] segmentDisplacement = displacment2D(initialVertex, finalVertex);
        if (segmentDisplacement[0] == 0 && segmentDisplacement[1] == 0) {
            return;
        }
        double segmentLength = Math.sqrt(dotProduct2D(segmentDisplacement, segmentDisplacement));
        double[] centerToInitialDisplacement = new double[]{initialVertex[0] - getCurrentCircle().getCenterX(), initialVertex[1] - getCurrentCircle().getCenterY()};
        final double leftX = dotProduct2D(centerToInitialDisplacement, segmentDisplacement) / segmentLength;
        final double rightX = leftX + segmentLength;
        final double y = wedgeProduct2D(segmentDisplacement, centerToInitialDisplacement) / segmentLength;
        processSegmentStandardGeometry(leftX, rightX, y);
    }

    private void processSegmentStandardGeometry(double leftX, double rightX, double y) {
        if (y * y > getCurrentSquareRadius()) {
            processNonIntersectingRegion(leftX, rightX, y);
        } else {
            final double intersectionX = Math.sqrt(getCurrentSquareRadius() - y * y);
            if (leftX < -intersectionX) {
                final double leftRegionRightEndpoint = Math.min(-intersectionX, rightX);
                processNonIntersectingRegion(leftX, leftRegionRightEndpoint, y);
            }
            if (intersectionX < rightX) {
                final double rightRegionLeftEndpoint = Math.max(intersectionX, leftX);
                processNonIntersectingRegion(rightRegionLeftEndpoint, rightX, y);
            }
            final double middleRegionLeftEndpoint = Math.max(-intersectionX, leftX);
            final double middleRegionRightEndpoint = Math.min(intersectionX, rightX);
            final double middleRegionLength = Math.max(middleRegionRightEndpoint - middleRegionLeftEndpoint, 0);
            processIntersectingRegion(middleRegionLength, y);
        }
    }

    private void processNonIntersectingRegion(double leftX, double rightX, double y) {
        final double initialTheta = Math.atan2(y, leftX);
        final double finalTheta = Math.atan2(y, rightX);
        double deltaTheta = finalTheta - initialTheta;
        if (deltaTheta < -Math.PI) {
            deltaTheta += 2 * Math.PI;
        } else if (deltaTheta > Math.PI) {
            deltaTheta -= 2 * Math.PI;
        }
        processNonIntersectingRegion(deltaTheta);
    }

    protected abstract void initialize();

    protected abstract void initializeForNewCircle(Circle circle);

    protected abstract void processNonIntersectingRegion(double deltaTheta);

    protected abstract void processIntersectingRegion(double length, double y);

    protected abstract T getValue();

    protected final Circle getCurrentCircle() {
        return currentCircle;
    }

    protected final double getCurrentSquareRadius() {
        return currentSquareRadius;
    }

على أي حال، هذا هو وصفي للخوارزمية. أعتقد أنه من الجيد لأنه دقيق ولا يوجد بالفعل العديد من الحالات للتحقق.

Answer 3

ما يقرب من عام ونصف متأخرا، لكنني اعتقدت ربما سيكون الناس مهتمين بهم الكود هنا أنني كتبت الذي أعتقد أنه يفعل هذا بشكل صحيح. انظر في الوظيفة تقاطعت في القاع. النهج العام هو اختيار مضلع المحدبة المحدبة من قبل الدائرة، ثم التعامل مع القبعات الدائرية الصغيرة.

Answer 4

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

إنها ليست صيغة لطيفة، أو سريعة بشكل خاص، لكنها تحصل على المنجز المهمة.

Answer 5

يحاول الهندسة الحسابية

ملاحظة: هذه ليست مشكلة تافهة، آمل أن تكون الواجبات المنزلية ؛-)

Answer 6

إذا كان لديك GPU تحت تصرفكم، فيمكنك استخدام هذه تقنية للحصول على عدد البكسل من التقاطع ..

Answer 7

أعتقد أنك يجب أن لا يجب أن تقريب الدائرة كحدد من المثلثات، بدلا من ذلك يمكنك تقريب شكله مع مضلع. يمكن أن تبدو الخوارزمية الساذجة مثل:

1. تحويل لك دائرة إلى المضلع مع عدد المرغوب فيه من القمم.
2. احسب تقاطع اثنين من المضلعات (الدائرة المحولة ومثلث).
3. حساب مربع من تلك التقاطع.

يمكنك تحسين هذه الخوارزمية من خلال الجمع بين الخطوة 2 والخطوة 3 في وظيفة واحدة.

قراءة هذه الروابط:
مساحة مضلع محدب
تقاطع مضللي محدب

Answer 8

نظرا لأن أشكالك محدبة، يمكنك استخدام تقدير منطقة مونتي كارلو.

ارسم مربع حول الدائرة والمثلث.

اختر نقاط عشوائية في المربع والحفاظ على عدد من عدد السقوط في الدائرة، وعدد الانخفاض في كل من الدائرة والمثلث.

مجال التقاطع ≅ منطقة الدائرة * # نقاط في دائرة ومثلث / # نقاط في دائرة

التوقف عن اختيار النقاط عندما لا تتغير المنطقة المقدرة بأكثر من مبلغ معين عبر عدد معين من الجولات، أو فقط اختر عدد ثابت من النقاط بناء على منطقة المربع. يجب أن يتوقف تقدير المنطقة بسرعة كبيرة ما لم يكن أحد أشكالك مساحة صغيرة جدا.

ملاحظة: إليك كيفية تحديد ما إذا كانت النقطة في مثلث: الإحداثيات الحجرية

Answer 9

ما مدى الدقة التي تحتاجها؟ إذا كنت تستطيع تقريب الدائرة بأشكال أبسط، فيمكنك تبسيط المشكلة. لن يصعب تصميم دائرة كمجموعة من اجتماعات مثلثات ضيقة للغاية في المركز، على سبيل المثال.

Answer 10

إذا تتبادل إحدى قطاعات خط المثلث فقط الدائرة، فإن حل الرياضيات النقي ليس صعبا للغاية. بمجرد معرفة متى تكون نقطتان من التقاطع، يمكنك استخدام صيغة المسافة للعثور على طول الوتر.

وفق هذه المعادلات:

ϑ = 2 sin⁻¹(0.5 c / r)
A = 0.5 r² (ϑ - sin(ϑ))

حيث C هو طول الوتر، R هو دائرة نصف قطرها، θ يصبح الزاوية من خلال المركز، وهي المنطقة. لاحظ أن هذا الحل ينهار إذا تم قطع أكثر من نصف الدائرة.

ربما لا يستحق الجهد إذا كنت بحاجة فقط إلى تقريب، لأنها تجعل العديد من الافتراضات حول ما يبدو عليه التقاطع الفعلي.

Answer 11

ستكون غريزتي الأولى هي تحويل كل شيء بحيث تركز الدائرة على الأصل، وتقليل المثلث إلى الإحداثيات القطبية، وحلها من التقاطع (أو المشمور) من المثلث مع الدائرة. لم أعمل في الواقع من خلال الورق حتى الآن على الرغم من أن هذا مجرد حدز.