مجموعة المستويات (هياكل البيانات)

قامت طريقة مجموعة المستويات ذات النطاق الضيق، التي قدمها أدالستينسون وسيثيان عام 1995، ^{[ 2 ]} بتقييد معظم العمليات الحسابية على نطاق ضيق من وحدات البكسل النشطة المحيطة مباشرة بالواجهة، مما قلل من التعقيد الزمني في ثلاثة أبعاد إلى${\displaystyle O(n^{2})}$بالنسبة لمعظم العمليات، كانت هناك حاجة إلى تحديثات دورية لبنية النطاق الضيق، لإعادة بناء قائمة وحدات البكسل النشطة، الأمر الذي استلزم${\displaystyle O(n^{3})}$عملية يتم فيها الوصول إلى وحدات البكسل ثلاثية الأبعاد (فوكسل) في جميع أنحاء الحجم. ولا يزال تعقيد التخزين لهذا المخطط ذي النطاق الضيق${\displaystyle O(n^{3}).}$تتطلب عمليات البناء التفاضلية على حافة نطاق النطاق الضيق مخططات دقيقة للاستيفاء وتغيير النطاق لتحقيق استقرار الحل. ^{[ 3 ]}

هذا${\displaystyle O(n^{3})}$تم التخلص من تعقيد الوقت في طريقة مجموعة المستويات "الحقل المتفرق" التقريبية التي قدمها ويتاكر عام 1998. ^{[ 4 ]} تستخدم طريقة مجموعة المستويات "الحقل المتفرق" مجموعة من القوائم المرتبطة لتتبع وحدات البكسل النشطة حول الواجهة. وهذا يسمح بتوسيع المنطقة النشطة تدريجيًا حسب الحاجة دون تكبد أي تكلفة إضافية كبيرة.${\displaystyle O(n^{2})}$فعال من حيث الوقت،${\displaystyle O(n^{3})}$لا تزال مساحة التخزين مطلوبة لطريقة مجموعة مستوى الحقل المتفرق. انظر ^{[ 5 ]} للاطلاع على تفاصيل التنفيذ.

تقوم طريقة الشبكة الكتلية المتفرقة، التي قدمها بريدسون في عام 2003، ^{[ 6 ]} بتقسيم حجم المحيط بالكامل ذي الحجم${\displaystyle n^{3}}$إلى مكعبات صغيرة من${\displaystyle m^{3}}$كل فوكسل. شبكة خشنة بحجم${\displaystyle (n/m)^{3}}$ثم يخزن المؤشرات فقط إلى تلك الكتل التي تتقاطع مع النطاق الضيق لمجموعة المستويات. ويحدث تخصيص الكتل وإلغاء تخصيصها أثناء انتشار السطح للتكيف مع التشوهات. تتميز هذه الطريقة بتعقيد تخزين دون المستوى الأمثل.${\displaystyle O\left((nm)3+m^{3}n^{2}\right)}$، ولكنه يحتفظ بإمكانية الوصول الثابت للوقت المتأصلة في الشبكات الكثيفة.

تستخدم طريقة مجموعة المستويات الثمانية ، التي قدمها سترين عام 1999 ^{[ 7 ]} وطورها لوساسو وجيبو وفيدكيو ^{[ 8 ]} ، ومؤخرًا مين وجيبو ^{[ 9 ]،} شجرة من مكعبات متداخلة تحتوي عقدها الطرفية على قيم مسافة مُوَقَّعة. تتطلب مجموعات المستويات الثمانية حاليًا تحسينًا موحدًا على طول الواجهة (أي النطاق الضيق) للحصول على دقة كافية. هذا التمثيل فعال من حيث التخزين.${\displaystyle O(n^{2}),}$وفعالية نسبية من حيث استعلامات الوصول،${\displaystyle O(\log \,n).}$تتمثل إحدى مزايا طريقة المستوى على هياكل بيانات الأوكتري في إمكانية حل المعادلات التفاضلية الجزئية المرتبطة بمسائل الحدود الحرة النموذجية التي تستخدم طريقة مجموعة المستوى. وقد طور فريق بحث CASL ^{[ 10 ]} هذا المسار البحثي في ​​مجالات المواد الحاسوبية، وديناميكا الموائع الحاسوبية ، والحركية الكهربائية، والجراحة الموجهة بالصور، وأنظمة التحكم.

تُطبّق طريقة ترميز طول التشغيل ( RLE) لمجموعة المستويات، التي طُرحت عام 2004 ^{[ 11 ]،} مخطط RLE لضغط المناطق البعيدة عن النطاق الضيق إلى تمثيلها الإشاري فقط، مع تخزين النطاق الضيق بدقة كاملة. يُعدّ الاجتياز التسلسلي للنطاق الضيق مثاليًا، كما تتحسن كفاءة التخزين بشكل أكبر مقارنةً بمجموعة مستويات الشجرة الثمانية. وتتيح إضافة جدول بحث مُسرّع إمكانية الوصول السريع إلى البيانات.${\displaystyle O(\log r)}$الوصول العشوائي، حيث يمثل r عدد مرات التشغيل لكل مقطع عرضي. يتم تحقيق كفاءة إضافية من خلال تطبيق مخطط RLE بطريقة تكرارية متعددة الأبعاد، وهي تقنية قدمها نيلسن وموسيث في شبكة DT-Grid المشابهة. ^{[ 12 ]}

طُرحت طريقة مجموعة المستوى المحلية لجدول التجزئة في عام 2011 بواسطة إييوريكلي وبرين ^{[ 13 ]} ، ووُسِّعت في عام 2012 بواسطة برون، وجيتيت، وجيبو ^{[ 14 ].} تحسب هذه الطريقة بيانات مجموعة المستوى في نطاق ضيق حول الواجهة فقط، كما هو الحال في طريقة مجموعة المستوى ذات النطاق الضيق، ولكنها تخزن البيانات في هذا النطاق نفسه فقط. يُستخدم هيكل بيانات جدول التجزئة، الذي يوفر...${\displaystyle O(1)}$الوصول إلى البيانات. ومع ذلك، خلص برون وآخرون إلى أن طريقتهم، على الرغم من سهولة تطبيقها، إلا أنها تؤدي أداءً أسوأ من تطبيق شجرة رباعية. ووجدوا أن

كما هو الحال، [...] يبدو أن بنية بيانات الشجرة الرباعية أكثر ملاءمة من بنية بيانات جدول التجزئة لخوارزميات مجموعة المستويات.

تم سرد ثلاثة أسباب رئيسية لانخفاض الكفاءة:

1. للحصول على نتائج دقيقة، يلزم وجود نطاق كبير نوعًا ما بالقرب من الواجهة، وهو ما يعوض غياب عقد الشبكة البعيدة عن الواجهة؛
2. تتدهور الأداءات بسبب إجراءات الاستقراء على الحواف الخارجية للشبكة المحلية و
3. يؤدي عرض النطاق إلى تقييد الخطوة الزمنية وإبطاء الطريقة.

قدم كوربيت في عام 2005 ^{[ 15 ]} طريقة مجموعة المستوى القائمة على النقاط. وبدلاً من استخدام عينة منتظمة من مجموعة المستوى، يتم إعادة بناء دالة مجموعة المستوى المستمرة من مجموعة من عينات النقاط غير المنظمة عبر المربعات الصغرى المتحركة .