كيف يمكنني استخلاص مخطط فورونوي بالنظر إلى مجموعة النقاط الخاصة به وتثليث ديلوناي؟
-
01-07-2019 - |
سؤال
أنا أعمل على لعبة حيث أقوم بإنشاء خريطة عشوائية للمقاطعات (مثل المخاطر أو الدبلوماسية).لإنشاء تلك الخريطة، أقوم أولاً بتوليد سلسلة من النقاط شبه العشوائية، ثم أحسب مثلثات ديلوناي لتلك النقاط.
بعد الانتهاء من ذلك، أتطلع الآن إلى إنشاء مخطط فورونوي للنقاط ليكون بمثابة نقطة بداية لحدود المقاطعة.تتكون بياناتي في هذه المرحلة (لا أقصد التورية) من سلسلة النقاط الأصلية ومجموعة من مثلثات ديلوناي.
لقد رأيت عددًا من الطرق للقيام بذلك على الويب، لكن معظمها مرتبط بكيفية اشتقاق ديلوناي.أرغب في العثور على شيء لا يحتاج إلى التكامل مع Delaunay، ولكن يمكنه العمل بناءً على البيانات وحدها.إذا فشل ذلك، فأنا أبحث عن شيء مفهوم لمبتدئ في الهندسة النسبية، بدلاً من السرعة المثالية.شكرًا!
المحلول
مخطط فورونوي هو مجرد رسم بياني مزدوج لتثليث ديلوناي.
- إذن، حواف مخطط فورونوي تقع على طول المنصفات المتعامدة لحواف مثلث ديلوناي، لذا قم بحساب تلك الخطوط.
- ثم قم بحساب رؤوس مخطط فورونوي من خلال إيجاد تقاطعات الحواف المجاورة.
- أخيرًا، الحواف هي المجموعات الفرعية للخطوط التي حسبتها والتي تقع بين القمم المقابلة.
لاحظ أن الكود الدقيق يعتمد على التمثيل الداخلي الذي تستخدمه للمخططين.
نصائح أخرى
إذا لم تكن السرعة المثلى في الاعتبار، فسيقوم الكود الزائف التالي بإنشاء مخطط 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 المألوف عند عرض الإخراج.
بعد محاولة استخدام هذا الموضوع كمصدر للحصول على إجابات لسؤالي المماثل، وجدت أن خوارزمية Fortune — على الأرجح لأنها الأكثر شهرة وبالتالي الأكثر توثيقًا — كانت الأسهل في الفهم.
مقالة ويكيبيديا عن خوارزمية فورتشن يحتفظ بروابط جديدة للكود المصدري في C وC# وJavascript.كلهم كانوا من الطراز الأول وجاءوا بأمثلة جميلة.
أنا متأكد من أن "المثلث" http://www.cs.cmu.edu/~quake/triangle.html يمكن أن تولد فورونوي
يحتوي كل مثلث من مثلثات ديلوناي على نقطة واحدة من مخطط فورونوي.
يمكنك حساب هذه النقطة من خلال إيجاد تقاطع الثلاثة منصفات متعامدة لكل مثلث.
سيربط مخطط فورونوي الخاص بك هذه المجموعة من النقاط، كل منها مع أقرب ثلاث جيران لها.(يشترك كل جار في جانب من مثلث ديلوناي)
كيف تخطط للتعامل مع حالات الحافة؟