كيف يمكنني استخلاص مخطط فورونوي بالنظر إلى مجموعة النقاط الخاصة به وتثليث ديلوناي؟

Question

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

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

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

Answer 1

مخطط فورونوي هو مجرد رسم بياني مزدوج لتثليث ديلوناي.

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

لاحظ أن الكود الدقيق يعتمد على التمثيل الداخلي الذي تستخدمه للمخططين.

Answer 2

إذا لم تكن السرعة المثلى في الاعتبار، فسيقوم الكود الزائف التالي بإنشاء مخطط Voronoi بالطريقة الصعبة:

for yloop = 0 to height-1
  for xloop = 0 to width-1

    // Generate maximal value
    closest_distance = width * height

    for point = 0 to number_of_points-1
      // calls function to calc distance
      point_distance = distance(point, xloop, yloop)

      if point_distance < closest_distance
        closest_point = point
      end if
    next

  // place result in array of point types
  points[xloop, yloop] = point

  next
next

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

Answer 3

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

مقالة ويكيبيديا عن خوارزمية فورتشن يحتفظ بروابط جديدة للكود المصدري في C وC# وJavascript.كلهم كانوا من الطراز الأول وجاءوا بأمثلة جميلة.

Answer 4

أنا متأكد من أن "المثلث" http://www.cs.cmu.edu/~quake/triangle.html يمكن أن تولد فورونوي

Answer 5

يحتوي كل مثلث من مثلثات ديلوناي على نقطة واحدة من مخطط فورونوي.

يمكنك حساب هذه النقطة من خلال إيجاد تقاطع الثلاثة منصفات متعامدة لكل مثلث.

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

كيف تخطط للتعامل مع حالات الحافة؟