تقارب نقاط التوقف في خوارزمية فورتشن

Question

أقوم بتنفيذ خوارزمية خط المسح الخاصة بـ Fortune لحساب مخططات Voronoi.مرجعي الأساسي هو "الهندسة الحسابية:الخوارزميات والتطبيقات" بقلم دي بيرج وآخرون، وعلى الرغم من أن تغطيتهم للموضوع واضحة للغاية، إلا أنهم يمررون العديد من التفاصيل الصغيرة ولكن المهمة التي كنت أواجه صعوبة في حلها بنفسي.لقد بحثت في الويب للحصول على المساعدة، لكن مواقع الويب الأخرى إما تقدم نظرة عامة أفضل من الكتاب المدرسي، أو تقدم نفس الكود المستعار الذي يوفره الكتاب.

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

المعلومات الوحيدة التي يجب أن أعمل بها هي موقع x وy للمواقع الثلاثة والإحداثي y الحالي لخط المسح (أنا أستخدم خط مسح أفقي).

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

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

Answer 1

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

يقول:

1. currentSweeplineY = 1.0f; circleCenterY = 0.5f (ونحن نتحرك إلى الأسفل، أي:في اتجاه y المتناقص).

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY) / 10.0f (يتم اختيار المقسوم عليه 10.0f بشكل تعسفي).

3. Check new breakpoint positions at new sweepline position.

4. Check distance to circle center.

5. If both distances are less than current distances, the breakpoints converge.

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

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

Answer 2

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

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

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

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

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

Given left, middle, right sites
    if they are collinear, return false
    center = ComputeCircleCenterDefinedBy3Points(left, middle, right)
    return IsRightOfLine(left, middle, center) && IsRightOfLine(middle, right, center)

IsRightOfLine(start, end, point)
    ((end.X - start.X) * (point.Y - start.Y) - (end.Y - start.Y) * (point.X - start.X)) <= 0

Answer 3

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

إليك مقتطف من رمز C # لحساب النقاط المحترف D للنقاط A، B، C: giveacodicetagpre.