خوارزمية لحساب مخطط Voronoi على كرة؟

Question

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

Answer 1

ها هي ورقة الرسوم البيانية كروية Voronoi..

أو إذا كنت grok fortran (bleah!) هناك هذا الموقع.

Answer 2

تحديث في يوليو 2016:

بفضل عدد من المتطوعين (وخاصة Nikolai Nowaczyk و I)، هناك الآن رمز أكثر قوة / صحيحة للتعامل مع مخططات Voronoi على سطح كرة في بيثون. هذا متاح رسميا كما scipy.spatial.SphericalVoronoi من الإصدار 0.18 من scipy فصاعدا. هناك مثال عمل للاستخدام والتخطيط في الرسمي مستندات.

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

• الجهد لتحسين تخطيط المضلعات كروية في matplotlib
• الجهد لتحسين معالجة حسابات مساحة سطح المضلع كروية في SCIPY

لمزيد من الخلفية حول النظرية / التنمية / التحديات المتعلقة بمدونة بيثون هذا وجهود الهندسة الحسابية ذات الصلة، يمكنك أيضا التحقق من بعض المحادثات من نيكولاي وأنا:

• نيكولاي بيداتا لندن 2016 نقاش
• Tyler Pydata London 2015 Talk
• Tyler Pycon 2016 التعليمية الهندسية الحسابية

---

الإجابة الأصلية:

لقد كتبت بالفعل بعض كود بيثون المصدر المفتوح للمصدر المفتوح لمعلومات مخططات Voronoi على سطح المجال: https://github.com/tylerjereddy/py_sphere_voronoi.

يتم توثيق الاستخدام والخوارزمية والقيود على ReadThedocs (http://py-sphere-voronoi.readtheedocs.org/en/latest/voronoi_utility.html.). هناك بعض الأمثلة التفصيلية هناك ولكني وضعت واحدا أو اثنين أدناه أيضا. تتعامل الوحدة أيضا بحساب المناطق السطحية لمنطقة Voronoi، وإن كان ذلك مع بعض نقاط الضعف العددية في إصدار التطوير الحالي.

لم أر العديد من التطبيقات المصدر المفتوحة موثقة جيدا من أجل مخططات Voronoi كروية، ولكن كان هناك القليل من الطنانة حول تنفيذ جافا سكريبت على موقع جيسون ديفيز (http://www.jasondavies.com/maps/voronoi/). لا أعتقد أن قانونه مفتوح رغم ذلك. كما رأيت منشورا مدونا حول استخدام Python للتعامل مع جزء من المشكلة (http://jellymatter.com/2017/01/29/Voronoi-Tesselation-ON-The-Surface-of-a-sphere-python-code/). يبدو أن العديد من مصادر الأدب الأولية المذكورة في الوظائف المذكورة أعلاه صعبة للغاية لتنفيذ (حاولت بعضها) ولكن ربما سيجد بعض الأشخاص تنفيذي مفيدا أو حتى اقتراح طرق لتحسينه.

أمثلة:

1) إنتاج مخطط Voronoi لمجموعة من النقاط ذات العشوائي الزائفة في مجال الوحدة:

import matplotlib
import matplotlib.pyplot as plt
import matplotlib.colors as colors
from mpl_toolkits.mplot3d import Axes3D
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
import numpy as np
import scipy as sp
import voronoi_utility
#pin down the pseudo random number generator (prng) object to avoid certain pathological generator sets
prng = np.random.RandomState(117) #otherwise, would need to filter the random data to ensure Voronoi diagram is possible
#produce 1000 random points on the unit sphere using the above seed
random_coordinate_array = voronoi_utility.generate_random_array_spherical_generators(1000,1.0,prng)
#produce the Voronoi diagram data
voronoi_instance = voronoi_utility.Voronoi_Sphere_Surface(random_coordinate_array,1.0)
dictionary_voronoi_polygon_vertices = voronoi_instance.voronoi_region_vertices_spherical_surface()
#plot the Voronoi diagram
fig = plt.figure()
fig.set_size_inches(2,2)
ax = fig.add_subplot(111, projection='3d')
for generator_index, voronoi_region in dictionary_voronoi_polygon_vertices.iteritems():
   random_color = colors.rgb2hex(sp.rand(3))
   #fill in the Voronoi region (polygon) that contains the generator:
   polygon = Poly3DCollection([voronoi_region],alpha=1.0)
   polygon.set_color(random_color)
   ax.add_collection3d(polygon)
ax.set_xlim(-1,1);ax.set_ylim(-1,1);ax.set_zlim(-1,1);
ax.set_xticks([-1,1]);ax.set_yticks([-1,1]);ax.set_zticks([-1,1]); 
plt.tick_params(axis='both', which='major', labelsize=6)

2) احسب المناطق السطحية من Voronoi Region Polygons وتحقق من أن مساحة السطح المعاد تشكيلها معقولة:

import math
dictionary_voronoi_polygon_surface_areas = voronoi_instance.voronoi_region_surface_areas_spherical_surface()
theoretical_surface_area_unit_sphere = 4 * math.pi
reconstituted_surface_area_Voronoi_regions = sum(dictionary_voronoi_polygon_surface_areas.itervalues())
percent_area_recovery = round((reconstituted_surface_area_Voronoi_regions / theoretical_surface_area_unit_sphere) * 100., 5)
print percent_area_recovery
97.87551 #that seems reasonable for now

Answer 3

لاحظ أن Delaunay Trangulation على الكرة هو مجرد بدن محدب. وبالتالي يمكنك حساب بدن محدب ثلاثي الأبعاد (على سبيل المثال باستخدام cgal) واتخاذ المزدوج.

Answer 4

باختصار، حاول cssgrid. من الرسومات NCAR. وبعد كتبت إجابة أطول لسؤال مماثل في Codereview.stackexchange.com.

Answer 5

هناك ورقة من INRIRA حول Treaunay Trangulation (DT) من النقاط ملقاة على كرة: كارولي، مانويل، وآخرون. قوية و EF Delaunay Delaunay Delaunay من النقاط أو بالقرب من المجال. 2009. حيث يتحدثون عن التنفيذ في cgal..

تشير الورقة إلى مختلف التنفيذ المتاح لخوارزميات DT.

نقلا عن الورقة:

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

لحسوس محدبة بدن الورقة تقترح:

1. هال، برنامج لهدوء محدب.
2. قول.
3. بدن محدب ثلاثي الأبعاد. في فورتران.
4. مخابز في فورتران.

فئة DT C ++ من CGAL لديها الطريقة dual للحصول على مخطط voronoi.

وفق هذا المشنور بقلم مونيك تيلود (أحد مؤلف الكتاب المذكور أعلاه) يبدو لي أنه في نوفمبر 2012 لم يكن التنفيذ جاهزا.

Answer 6

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

• "تجتاح المجال" من قبل دينيس ومخي، نشرت في الندوة الدولية لعام 2010 بشأن مخططات Voronoi في العلوم والهندسة. يمكن شراؤها في http://dx.doi.org/10.1109/isvd.2010.32.
• "خوارزمية الاجتياح الطائرة لفستان فورونوي من المجال" من Zheng et al. لست متأكدا من نشرها بسبب أول واحد، لكنها مؤرخة 13 ديسمبر 2011. وهي متوفرة مجانا في http://www.e-lc.org/tmp/xiaoyu__zheng_2011_12_05_14_35_11.pdf.

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

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

Answer 7

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

هذه ليست الإجابة بأكملها، ولكن هذا هو المكان الذي سأبدأه ..

Answer 8

هناك برنامج مثال مخطط Voronoi لطيف هنا (بما في ذلك شفرة المصدر ل Delphi 5/6).

أعتقد أن "النقاط على سطح الكرة" تعني أن عليك أولا إعادة إرسالها إلى إحداثيات ثنائية الأبعاد، وإنشاء مخطط Voronoi ثم إعادة إيقافها إلى إحداثيات سطح الكرة. هي الصيغان من Wikipedia UV رسم الخرائط العمل هنا؟

لاحظ أيضا أن مخطط Voronoi سيكون له طوبولوجيا خاطئة (داخل المستطيل ولا "التفاف حولها")، هنا يمكن أن يساعد في نسخ جميع النقاط من (0،0) - (x، y) إلى الجار المناطق أعلاه (0، -Y * 2) - (x، 0)، أدناه (0، Y) - (x، y * 2)، اليسار (-x، 0) - (0، y) واليمين (x، 0) - (x * 2، ذ). أتمنى أن تعرف ما أقصده، لا تتردد في طلب :)

Answer 9

cgal. يعمل على حزمة "Kernel Sperical"، والتي ستسمح لحساب هذا النوع من الأشياء بالضبط. لسوء الحظ، لم يتم إصداره بعد, ، ولكن ربما سيكون في الإصدار التالي، لأنهم بالفعل ذكرها في حديث جوجل التقنية في مارس

Answer 10

نقلا عن هذا المرجع: http://www.qull.org/html/qdelaun.htm.

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

Answer 11

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