كوادري

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

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

يمكن استخدام شجرة رباعية المناطق بعمق n لتمثيل صورة تتكون من 2n ^× 2n ^بكسل ، حيث تكون قيمة كل بكسل إما 0 أو 1. تمثل العقدة الجذرية منطقة الصورة بأكملها. إذا لم تكن جميع البكسلات في أي منطقة إما 0 أو 1، يتم تقسيمها. في هذا التطبيق، تمثل كل عقدة طرفية مجموعة من البكسلات التي جميعها 0 أو 1. لاحظ التوفير المحتمل في المساحة عند استخدام هذه الأشجار لتخزين الصور؛ فغالبًا ما تحتوي الصور على العديد من المناطق ذات الحجم الكبير والتي لها نفس قيمة اللون. بدلًا من تخزين مصفوفة ثنائية الأبعاد كبيرة لكل بكسل في الصورة، يمكن للشجرة الرباعية التقاط نفس المعلومات على مستويات تقسيم أعلى بكثير من حجم الخلايا بدقة البكسل التي نحتاجها في الأحوال العادية. دقة الشجرة وحجمها الإجمالي محدودان بحجم البكسل وحجم الصورة.

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

شجرة النقاط الرباعية ^{[ 4 ]} هي نسخة معدلة من الشجرة الثنائية تُستخدم لتمثيل بيانات النقاط ثنائية الأبعاد. تشترك في خصائص جميع الأشجار الرباعية، لكنها شجرة حقيقية لأن مركز أي تقسيم فرعي يقع دائمًا على نقطة. غالبًا ما تكون فعالة جدًا في مقارنة نقاط البيانات ثنائية الأبعاد المرتبة، وعادةً ما تعمل في زمن O(log n) . تجدر الإشارة إلى أشجار النقاط الرباعية من باب الإكمال، لكنها أصبحت أقل كفاءة من أشجار k -d كأدوات للبحث الثنائي المعمم. ^{[ 5 ]} دُرست أشجار النقاط الرباعية مع الإدخال العشوائي تحت اسم الشبكات العشوائية المستوية الموزونة . ^{[ 6 ]}

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

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

تتشابه الأشجار الرباعية النقطية الإقليمية (PR) ^{[ 7 ] [ 8 ]} إلى حد كبير مع الأشجار الرباعية الإقليمية. ويكمن الاختلاف في نوع المعلومات المخزنة حول الخلايا. ففي الشجرة الرباعية الإقليمية، تُخزن قيمة موحدة تنطبق على كامل مساحة خلية الورقة. أما في الشجرة الرباعية النقطية الإقليمية، فتُخزن قائمة بالنقاط الموجودة داخل خلية الورقة. وكما ذُكر سابقًا، يعتمد ارتفاع الأشجار التي تتبع استراتيجية التقسيم هذه على التوزيع المكاني للنقاط. ومثل الشجرة الرباعية النقطية، قد يكون ارتفاع الشجرة الرباعية النقطية الإقليمية خطيًا عند إعطائها مجموعة "غير صحيحة".

تُستخدم أشجار الحواف الرباعية ^{[ 9 ] [ 10 ]} (على غرار أشجار PM الرباعية) لتخزين الخطوط بدلاً من النقاط. يتم تقريب المنحنيات بتقسيم الخلايا بدقة عالية جدًا، حتى يصبح لكل خلية قطعة مستقيمة واحدة. بالقرب من الزوايا/الرؤوس، تستمر أشجار الحواف الرباعية في التقسيم حتى تصل إلى أقصى مستوى من التجزئة. قد ينتج عن ذلك أشجار غير متوازنة للغاية، مما قد يُفقد الفهرسة جدواها.

شجرة الخرائط المضلعة الرباعية (أو شجرة الخرائط المضلعة الرباعية PM) هي نوع من أنواع الأشجار الرباعية، وتُستخدم لتخزين مجموعات من المضلعات التي قد تكون متدهورة (أي ذات رؤوس أو حواف معزولة). ^{[ 11 ] [ 12 ]} يتمثل أحد الفروق الرئيسية بين أشجار الخرائط المضلعة الرباعية وأشجار الحواف الرباعية في أن الخلية قيد الدراسة لا تُقسّم إذا التقت القطع المستقيمة عند رأس داخل الخلية.

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

يلخص هذا القسم قسمًا فرعيًا من كتاب سارييل هار-بيليد . ^{[ 13 ]}

إذا قمنا بتخزين كل عقدة تُقابل خلية مُقسّمة، فقد ينتهي بنا الأمر بتخزين عدد كبير من العقد الفارغة. يُمكننا تقليل حجم هذه الأشجار المتفرقة عن طريق تخزين الأشجار الفرعية التي تحتوي أوراقها على بيانات مهمة فقط (أي "الأشجار الفرعية المهمة"). بل يُمكننا تقليل الحجم أكثر من ذلك. عندما نحتفظ فقط بالأشجار الفرعية المهمة، قد تُخلّف عملية التقليم مسارات طويلة في الشجرة حيث تكون العقد الوسيطة من الدرجة الثانية (رابط إلى أحد الأبوين وابنه). يتضح أننا نحتاج فقط إلى تخزين العقدة${\displaystyle u}$في بداية هذا المسار (وربط بعض البيانات الوصفية به لتمثيل العقد المحذوفة) وربط الشجرة الفرعية المتجذرة في نهايته بـ${\displaystyle u}$لا يزال من الممكن أن يكون لهذه الأشجار المضغوطة ارتفاع خطي عند إعطائها نقاط إدخال "سيئة".

على الرغم من أننا نختصر جزءًا كبيرًا من الشجرة عند إجراء هذا الضغط، فإنه لا يزال من الممكن تحقيق عمليات البحث والإدراج والحذف في زمن لوغاريتمي بالاستفادة من منحنيات الترتيب Z. يرسم منحنى الترتيب Z كل خلية من خلايا الشجرة الرباعية الكاملة (وبالتالي حتى الشجرة الرباعية المضغوطة) في${\displaystyle O(1)}$تحويل الزمن إلى خط أحادي البعد (وإعادة رسمه في${\displaystyle O(1)}$(مع مراعاة عامل الوقت أيضًا)، مما يُنشئ ترتيبًا كليًا للعناصر. لذلك، يمكننا تخزين الشجرة الرباعية في بنية بيانات للمجموعات المرتبة (حيث نخزن عقد الشجرة).

يجب أن نذكر افتراضًا معقولًا قبل أن نتابع: نفترض أنه بالنظر إلى عددين حقيقيين${\displaystyle \alpha ,\beta \in [0,1)}$عند التعبير عنها بالصيغة الثنائية، يمكننا إجراء العمليات الحسابية في${\displaystyle O(1)}$نحسب وقت فهرس أول بت يختلفان فيه. نفترض أيضًا أنه يمكننا الحساب في${\displaystyle O(1)}$نحسب الوقت لأدنى سلف مشترك لنقطتين/خليتين في الشجرة الرباعية ونحدد ترتيبهما النسبي Z ، ويمكننا حساب دالة الجزء الصحيح في${\displaystyle O(1)}$وقت.

بناءً على هذه الافتراضات، تحديد موقع نقطة معينة${\displaystyle q}$(أي تحديد الخلية التي ستحتوي${\displaystyle q}$يمكن إجراء عمليات الإضافة والحذف في${\displaystyle O(\log {n})}$الوقت (أي الوقت الذي يستغرقه البحث في بنية بيانات المجموعة المرتبة الأساسية).

لتحديد موقع نقطة ما${\displaystyle q}$(أي إيجاد خليتها في الشجرة المضغوطة):

1. ابحث عن الخلية الموجودة في الشجرة المضغوطة التي تسبق${\displaystyle q}$بترتيب Z. سمِّ هذه الخلية${\displaystyle v}$.
2. لو${\displaystyle q\in v}$، يعود${\displaystyle v}$.
3. وإلا، فابحث عن السلف المشترك الأدنى للنقطة${\displaystyle q}$والخلية${\displaystyle v}$في شجرة رباعية غير مضغوطة. سمِّ هذه الخلية السلفية${\displaystyle u}$.
4. ابحث عن الخلية الموجودة في الشجرة المضغوطة التي تسبق${\displaystyle u}$بترتيب Z وإعادته.

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

إحدى مزايا استخدام الأشجار الرباعية لمعالجة الصور هي سهولة وسرعة تنفيذ عمليات الاتحاد والتقاطع. ^{[ 5 ] [ 19 ] [ 20 ] [ 21 ] [ 22 ]} عند وجود صورتين ثنائيتين، ينتج عن اتحاد الصورتين (أو ما يُسمى بالتراكب ) صورة يكون فيها البكسل أسودًا إذا احتوت أي من الصورتين الأصليتين على بكسل أسود في نفس الموقع. أي أن البكسل في الصورة الناتجة يكون أبيض فقط عندما يكون البكسل المقابل له أبيض في كلتا الصورتين الأصليتين، وإلا يكون البكسل الناتج أسود. بدلًا من إجراء العملية بكسلًا بكسلًا، يمكننا حساب الاتحاد بكفاءة أكبر بالاستفادة من قدرة الشجرة الرباعية على تمثيل عدة بكسلات بعقدة واحدة. لأغراض المناقشة أدناه، إذا احتوت شجرة فرعية على بكسلات سوداء وبيضاء، فسنقول إن جذر تلك الشجرة الفرعية مُلوّن باللون الرمادي.

تعمل الخوارزمية عن طريق اجتياز شجرتي الإدخال الرباعيتين (${\displaystyle T_{1}}$و${\displaystyle T_{2}}$) أثناء بناء شجرة الإخراج الرباعية${\displaystyle T}$بصورة غير رسمية، تكون الخوارزمية كما يلي. لنفترض العقد${\displaystyle v_{1}\in T_{1}}$و ${\displaystyle v_{2}\in T_{2}}$يتوافق مع نفس المنطقة في الصور.

• لو${\displaystyle v_{1}}$أو${\displaystyle v_{2}}$إذا كان اللون أسود، يتم إنشاء العقدة المقابلة في${\displaystyle T}$ويكون لونه أسود. إذا كان أحدهما أسود والآخر رمادي، فستحتوي العقدة الرمادية على شجرة فرعية تحتها. ولا يلزم اجتياز هذه الشجرة الفرعية.
• لو${\displaystyle v_{1}}$(على التوالى،${\displaystyle v_{2}}$) أبيض،${\displaystyle v_{2}}$(على التوالى،${\displaystyle v_{1}}$) ويتم نسخ الشجرة الفرعية الموجودة أسفلها (إن وجدت) إلى${\displaystyle T}$.
• إذا كان كلاهما${\displaystyle v_{1}}$و${\displaystyle v_{2}}$إذا كانت رمادية، فإن الأطفال المقابلين لـ${\displaystyle v_{1}}$و${\displaystyle v_{2}}$يتم أخذها في الاعتبار.

على الرغم من أن هذه الخوارزمية تعمل، إلا أنها لا تضمن بحد ذاتها شجرة رباعية ذات حجم أدنى. على سبيل المثال، لننظر إلى النتيجة إذا قمنا بدمج رقعة شطرنج (حيث كل بلاطة تمثل بكسلًا) بحجم ${\displaystyle 2^{k}\times 2^{k}}$مع مكملها. والنتيجة هي مربع أسود ضخم كان من المفترض أن يُمثل بشجرة رباعية تحتوي فقط على العقدة الجذرية (الملونة بالأسود)، ولكن بدلاً من ذلك، تُنتج الخوارزمية شجرة رباعية كاملة بعمق${\displaystyle k}$ولحل هذه المشكلة، نقوم باجتياز الشجرة الرباعية الناتجة من الأسفل إلى الأعلى، حيث نتحقق مما إذا كانت العقد الأربعة الفرعية لها نفس اللون، وفي هذه الحالة نستبدل العقدة الأب بورقة من نفس اللون. ^{[ 5 ]}

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

لنفترض وجود بكسلين أسودين متجاورين في صورة ثنائية. يُعتبران متجاورين إذا كانا يشتركان في حافة أفقية أو رأسية. وبشكل عام، يكون البكسلان الأسودان متصلين إذا أمكن الوصول إلى أحدهما من الآخر بالانتقال فقط إلى البكسلات المجاورة (أي يوجد مسار من البكسلات السوداء بينهما حيث يكون كل زوج متتالي متجاورًا). كل مجموعة قصوى من البكسلات السوداء المتصلة تُسمى مكونًا متصلًا . باستخدام تمثيل الصور بشجرة رباعية، أوضح ساميت ^{[ 23 ]} كيفية إيجاد هذه المكونات المتصلة وتصنيفها في وقت يتناسب مع حجم الشجرة الرباعية. ^{[ 5 ] [ 24 ]} يمكن أيضًا استخدام هذه الخوارزمية لتلوين المضلعات.

تعمل الخوارزمية في ثلاث خطوات:

1. تحديد علاقات التجاور بين البكسلات السوداء
2. قم بمعالجة علاقات التكافؤ من الخطوة الأولى للحصول على تسمية فريدة لكل مكون متصل
3. قم بتسمية البكسلات السوداء بالعلامة المرتبطة بالمكون المتصل بها

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

تُنجز الخطوة الأولى من خلال اجتياز شجرة رباعية بترتيب لاحق . لكل ورقة سوداء${\displaystyle v}$ننظر إلى العقدة أو العقد التي تمثل الخلايا المجاورة الشمالية والجيران الشرقية (أي الخلايا الشمالية والشرقية التي تشترك في حواف مع خلية${\displaystyle v}$بما أن الشجرة منظمة بترتيب Z ، فإن لدينا الثابت الذي ينص على أن الجيران الجنوبيين والغربيين قد تم أخذهم في الاعتبار بالفعل. لنفترض أن الجار الشمالي أو الشرقي قيد الدراسة حاليًا هو${\displaystyle u}$. لو${\displaystyle u}$يمثل البكسلات السوداء:

• لو كان واحد فقط من${\displaystyle u}$أو${\displaystyle v}$إذا كان للخلية تسمية، فقم بتعيين تلك التسمية للخلية الأخرى.
• إذا لم يكن لأي منهما تصنيفات، فأنشئ تصنيفًا وقم بتعيينه لكليهما.
• لو${\displaystyle u}$و${\displaystyle v}$إذا كانت لها تسميات مختلفة، فقم بتسجيل معادلة هذه التسمية وانتقل إلى الخطوة التالية.

يمكن إنجاز الخطوة الثانية باستخدام بنية بيانات الاتحاد والبحث . ^{[ 25 ]} نبدأ بكل تصنيف فريد كمجموعة منفصلة. لكل علاقة تكافؤ مُلاحظة في الخطوة الأولى، ندمج المجموعات المتناظرة. بعد ذلك، تُربط كل مجموعة متبقية مميزة بمكون متصل مميز في الصورة.

تُجري الخطوة الثالثة عملية اجتياز لاحقة أخرى. هذه المرة، لكل عقدة سوداء${\displaystyle v}$نستخدم عملية البحث الخاصة بـ union-find (مع التسمية القديمة لـ${\displaystyle v}$) للعثور على وتعيين${\displaystyle v}$علامتها الجديدة (المرتبطة بالمكون المتصل بها)${\displaystyle v}$(جزء).

من المفترض استخدام هذه الهياكل.

// كائن إحداثيات بسيط لتمثيل النقاط والمتجهات struct XY { float x ; float y ; function __construct ( float _x , float _y ) {...} } // صندوق محيط محاذٍ للمحاور بنصف بُعد ومركز struct AABB { XY center ; float halfDimension ; function __construct ( XY _center , float _halfDimension ) {...} function containsPoint ( XY point ) {...} function intersectsAABB ( AABB other ) {...} }

يمثل هذا الصنف كلاً من شجرة رباعية واحدة والعقدة التي تتجذر فيها.

class QuadTree { // ثابت اختياري لتحديد عدد العناصر التي يمكن تخزينها في عقدة شجرة رباعية int QT_NODE_CAPACITY = 4 ; // صندوق محيط محاذٍ للمحاور مخزن كمركز بأبعاد نصفية // لتمثيل حدود هذه الشجرة الرباعية AABB boundary ; // نقاط في عقدة هذه الشجرة الرباعية Array of XY [ size = QT_NODE_CAPACITY ] points ; // أبناء QuadTree * northWest ; QuadTree * northEast ; QuadTree * southWest ; QuadTree * southEast ; // الدوال function __construct ( AABB_boundary ) {...} function insert ( XY p ) {...} function subdivide () { ...} // إنشاء أربعة أبناء يقسمون هذه الشجرة الرباعية بالكامل إلى أربعة مربعات متساوية المساحة function queryRange ( AABB range ) {...} }

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

class QuadTree { ... // إدراج نقطة في شجرة رباعية function insert ( XY p ) { // تجاهل الكائنات التي لا تنتمي إلى هذه الشجرة الرباعية if ( ! boundary . containsPoint ( p )) return false ; // لا يمكن إضافة الكائن // إذا كانت هناك مساحة في هذه الشجرة الرباعية وإذا لم يكن بها تقسيمات فرعية، فأضف الكائن هنا if ( points . size < QT_NODE_CAPACITY && northWest == null ) { points . append ( p ); return true ; } // وإلا، قسّم الشجرة ثم أضف النقطة إلى أي عقدة تقبلها if ( northWest == null ) subdivide (); // يجب علينا إضافة النقاط/البيانات الموجودة في مصفوفة هذه الشجرة الرباعية إلى الأشجار الرباعية الجديدة إذا أردنا فقط // أن تحتوي العقدة الأخيرة على البيانات if ( northWest -> insert ( p )) return true ; if ( northEast -> insert ( p )) return true ; if ( southWest -> insert ( p )) return true ; إذا ( تم إدراج النقطة في منطقة الجنوب الشرقي )، فسيتم إرجاع القيمة true ؛ // وإلا، فلا يمكن إدراج النقطة لسبب غير معروف (وهذا لا ينبغي أن يحدث أبدًا) فسيتم إرجاع القيمة false ؛ } }

الطريقة التالية تجد جميع النقاط الموجودة ضمن نطاق معين.

class QuadTree { ... // البحث عن جميع النقاط التي تظهر ضمن نطاق دالة queryRange ( AABB range ) { // تجهيز مصفوفة من النتائج Array of XY pointsInRange ; // إيقاف العملية تلقائيًا إذا لم يتقاطع النطاق مع هذا المربع if ( ! boundary . intersectsAABB ( range )) return pointsInRange ; // قائمة فارغة // التحقق من الكائنات على مستوى هذا المربع for ( int p = 0 ; p < points . size ; p ++ ) { if ( range . containsPoint ( points [ p ])) pointsInRange . append ( points [ p ]); } // إنهاء العملية هنا، إذا لم يكن هناك أبناء if ( northWest == null ) return pointsInRange ; // وإلا، أضف النقاط من الأبناء pointsInRange . appendArray ( northWest -> queryRange ( range )); pointsInRange . appendArray ( northEast -> queryRange ( range )); pointsInRange . أضف مصفوفة ( نطاق الاستعلام من الجنوب الغربي ( النطاق ) )؛ أضف مصفوفة ( نطاق الاستعلام من الجنوب الشرقي ( النطاق ))؛ أرجع نقاط النطاق ؛ } }

1. رافائيل فينكل وجيه إل بنتلي (1974). "الأشجار الرباعية: بنية بيانات للاسترجاع باستخدام المفاتيح المركبة". مجلة أكتا إنفورماتيكا . 4 (1): 1-9 . doi : 10.1007/BF00288933 . S2CID 33019699 . 
2. مارك دي بيرج ، مارك فان كريفيلد ، مارك أوفرمارس ، وأوتفريد شوارزكوف (2000). الهندسة الحسابية (الطبعة الثانية المنقحة  ). سبرينغر-فيرلاغ . رقم ISBN 3-540-65620-0.{{cite book}}: CS1 maint: multiple names: authors list ( link ) Chapter 14: Quadtrees: pp.  291–306.
3. سامت، حنان ؛ ويبر، روبرت (يوليو 1985). "تخزين مجموعة من المضلعات باستخدام الأشجار الرباعية" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 17 يونيو 2012. تم الاطلاع عليه بتاريخ 23 مارس 2012 .