رسم الخرائط الشجرية

📅 آخر تحديث: ٣٠ يوليو ٢٠٢٦
✍️ نُشر في: ٣٠ يوليو ٢٠٢٦
📷 يحتوي على 13 صور
الموسوعة الحرة
خريطة شجرية لصادرات سنغافورة حسب فئة المنتج، 2012. تعد خرائط شجر صادرات المنتجات واحدة من أحدث تطبيقات هذا النوع من التصورات، والتي طورها مرصد هارفارد-معهد ماساتشوستس للتكنولوجيا للتعقيد الاقتصادي.

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

تعرض خرائط الشجرة البيانات الهرمية ( ذات البنية الشجرية ) على شكل مجموعة من المستطيلات المتداخلة. يُخصص لكل فرع من فروع الشجرة مستطيل، ثم يُقسّم هذا المستطيل إلى مستطيلات أصغر تمثل الفروع الفرعية. تتناسب مساحة مستطيل العقدة الطرفية مع بُعد محدد من أبعاد البيانات . [ 1 ] غالبًا ما تُلوّن العقد الطرفية لإظهار بُعد منفصل من أبعاد البيانات.

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

خوارزميات التبليط

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

  1. نسبة عرض إلى ارتفاع صغيرة - مثالية قريبة من الواحد. المناطق ذات نسبة العرض إلى الارتفاع الصغيرة (أي الأجسام السمينة ) يسهل إدراكها. [ 2 ]
  2. حافظ على بعض الترتيب في بيانات الإدخال (مرتبة).
  3. التغيير ليعكس التغييرات في البيانات الأساسية (استقرار عالٍ).

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

خرائط شجرية مستطيلة

حتى الآن، تم تطوير خمس عشرة خوارزمية أساسية لرسم خرائط الأشجار المستطيلة:

خوارزميات رسم الخرائط الشجرية [ 3 ]
الخوارزميةطلبنسب العرض إلى الارتفاعاستقرار
الشجرة الثنائيةتم الطلب جزئياعاليمستقر
تقطيع وفرم [ 4 ]تم الطلبمرتفع جداًمستقر
الشريط [ 5 ]تم الطلبواسطةثبات متوسط
التمحور من المنتصف [ 6 ]تم الطلبواسطةثبات متوسط
التمحور عن طريق التقسيم [ 6 ]تم الطلبواسطةاستقرار منخفض
التمحور حسب الحجم [ 6 ]تم الطلبواسطةثبات متوسط
الانقسام [ 7 ]تم الطلبواسطةثبات متوسط
حلزوني [ 8 ]تم الطلبواسطةثبات متوسط
هيلبرت [ 9 ]تم الطلبواسطةثبات متوسط
مور [ 9 ]تم الطلبواسطةثبات متوسط
مربع [ 10 ]غير مُرتبقليلاستقرار منخفض
خرائط شجرية مختلطة [ 11 ]غير مُرتبقليلثبات متوسط
التقريب [ 12 ]غير مُرتبقليلثبات متوسط
جيت [ 13 ]غير مُرتبواسطةمستقر
التحركات المحلية [ 14 ]غير مُرتبواسطةمستقر

خرائط شجرية محدبة

تتميز خرائط الأشجار المستطيلة بعيب يتمثل في أن نسبة أبعادها قد تكون عالية بشكل تعسفي في أسوأ الحالات. على سبيل المثال، إذا كان لجذر الشجرة طفلان فقط، أحدهما ذو وزن1/ن{\displaystyle 1/n}وواحد ذو وزن1-1/ن{\displaystyle 1-1/n}إذن، ستكون نسبة أبعاد الطفل الأصغر هين{\displaystyle n}والتي يمكن أن تكون عالية بشكل تعسفي. ولمعالجة هذه المشكلة، تم اقتراح العديد من الخوارزميات التي تستخدم مناطق عبارة عن مضلعات محدبة عامة ، وليست بالضرورة مستطيلة.

تم تطوير خرائط الأشجار المحدبة على عدة مراحل، حيث حسّنت كل مرحلة الحد الأعلى لنسبة العرض إلى الارتفاع. وتُعطى الحدود كدالة لـن{\displaystyle n}- العدد الإجمالي للعقد في الشجرة، ود{\displaystyle d}- العمق الكلي للشجرة.

  1. أثبت أوناك وسيديروبولوس [ 15 ] حدًا أعلى لـيا((دسجل⁡ن)17){\displaystyle O((d\log {n})^{17})}.
  2. قام كل من دي بيرغ وأوناك وسيديروبولوس [ 16 ] بتحسين الحد الأعلى لـيا(د+سجل⁡ن){\displaystyle O(d+\log {n})}، وأثبت حدًا أدنى لـيا(د){\displaystyle O(d)}.
  3. قام كل من دي بيرغ وسبيكمان وفان دير ويل [ 17 ] بتحسين الحد الأعلى لـيا(د){\displaystyle O(d)}، بما يتوافق مع الحد الأدنى النظري. (في الحالة الخاصة حيث يكون العمق 1، يقدمون خوارزمية تستخدم أربع فئات فقط من المضلعات ذات الزاوية 45 درجة (المستطيلات، والمثلثات القائمة الزاوية، وشبه المنحرف القائم الزاوية، والخماسيات ذات الزاوية 45 درجة)، وتضمن نسبة عرض إلى ارتفاع لا تتجاوز 34/7.)

تعمل الخوارزميتان الأخيرتان على مرحلتين (مبسطتان للغاية للتوضيح):

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

خرائط شجرية محدبة متعامدة

في خرائط الأشجار المحدبة، لا يمكن أن تكون نسبة العرض إلى الارتفاع ثابتة، بل تزداد مع عمق الشجرة. وللحصول على نسبة عرض إلى ارتفاع ثابتة، يمكن استخدام خرائط الأشجار المحدبة المتعامدة [ 17 ] . في هذه الخرائط، تكون جميع المناطق عبارة عن مضلعات مستطيلة محدبة متعامدة بنسبة عرض إلى ارتفاع لا تتجاوز 64؛ وتكون الأوراق إما مستطيلات بنسبة عرض إلى ارتفاع لا تتجاوز 8، أو أشكالًا على هيئة حرف L أو S بنسبة عرض إلى ارتفاع لا تتجاوز 32.

في الحالة الخاصة التي يكون فيها العمق 1، يقدمون خوارزمية تستخدم المستطيلات والأشكال على شكل حرف L فقط، ونسبة العرض إلى الارتفاع لا تتجاوز2+2/3≈3.15{\displaystyle 2+2/{\sqrt {3}}\approx 3.15}تستخدم العقد الداخلية مستطيلات فقط بنسبة عرض إلى ارتفاع لا تتجاوز1+3≈2.73{\displaystyle 1+{\sqrt {3}}\approx 2.73}.

خرائط شجرية أخرى

خرائط فورونوي الشجرية
[ 18 ] يعتمد علىمخطط فورونوي. الخوارزمية تكرارية ولا تعطي أي حد أعلى لنسبة العرض إلى الارتفاع.
خرائط الأشجار المتشابكة [ 19 ]
تعتمد هذه الطريقة على هندسة المنحنيات التي تملأ الفراغ. وتفترض أن الأوزان أعداد صحيحة وأن مجموعها عدد مربع. مناطق الخريطة عبارة عن مضلعات مستقيمة غير متعامدة محدبة بشكل كبير. ونسبة أبعادها مضمونة ألا تتجاوز 4.
خرائط جوسبر
[ 20 ] يعتمد على هندسةمنحنيات جوسبر. إنه منظم ومستقر، ولكنه يتمتع بنسبة عرض إلى ارتفاع عالية جدًا.

تاريخ

تم عرض استخدام مساحة القرص الصلب بشكل مرئي في برنامج TreeSize، الذي تم إصداره لأول مرة في عام 1996

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

استخدمت جميع خرائط الشجرة المبكرة خوارزمية التبليط البسيطة "التقطيع والتقسيم". ورغم مزاياها العديدة (فهي مستقرة، وتحافظ على الترتيب، وسهلة التطبيق)، إلا أن طريقة التقطيع والتقسيم غالبًا ما تُنتج تبليطات ذات مستطيلات طويلة ورفيعة. في عام ١٩٩٤، ابتكر مونتاز هاسكويت وميشيل بودوان-لافون خوارزمية "التربيع"، التي شاع استخدامها لاحقًا على يد جارك فان ويك ، والتي أنتجت تبليطات ذات مستطيلات أقرب إلى المربع. في عام ١٩٩٩، استخدم مارتن واتنبرغ نسخة معدلة من خوارزمية "التربيع" أطلق عليها اسم "التمحور والتقطيع" لإنشاء أول خريطة شجرة على الإنترنت، وهي خريطة سمارت موني للسوق، التي عرضت بيانات عن مئات الشركات في سوق الأسهم الأمريكية. بعد إطلاقها، لاقت خرائط الشجرة رواجًا كبيرًا، لا سيما في السياقات المالية.

ظهرت موجة ثالثة من ابتكارات خرائط الشجرة حوالي عام 2004، بعد أن ابتكر ماركوس ويسكامب خريطة الأخبار (Newsmap) ، وهي خريطة شجرة تعرض عناوين الأخبار. ألهم هذا المثال لخريطة شجرة غير تحليلية العديد من المقلدين، وقدم خرائط الشجرة لجمهور جديد وواسع. في السنوات الأخيرة، شقت خرائط الشجرة طريقها إلى وسائل الإعلام الرئيسية، بما في ذلك استخدامها من قبل صحيفة نيويورك تايمز. [ 23 ] [ 24 ] أنتج مشروع فن خرائط الشجرة [ 25 ] 12 صورة مؤطرة للأكاديميات الوطنية (الولايات المتحدة) ، عُرضت في معرض "كل خوارزمية تحمل فنًا بداخلها" [ 26 ] في واشنطن العاصمة، ومجموعة أخرى لمجموعة متحف الفن الحديث في نيويورك.

انظر أيضاً

مراجع

  1. ↑ لي، ريتا يي مان؛ تشاو، كوونغ وينغ؛ زينغ، فرانكي فانجي (2019). "تصنيف المخاطر لأعمال البناء القائمة والجديدة" . الاستدامة . 11 (10): 2863. Bibcode : 2019Sust...11.2863L . doi : 10.3390/su11102863 .
  2. ↑ كونغ، ن؛ هير، ج؛ أغراوالا، م (2010). "إرشادات إدراكية لإنشاء خرائط شجرية مستطيلة". معاملات IEEE في التصور ورسومات الحاسوب . 16 (6): 990-998 . Bibcode : 2010ITVCG..16..990K . CiteSeerX 10.1.1.688.4140 . doi : 10.1109/TVCG.2010.186 . PMID 20975136. S2CID 11597084 .   
  3. ↑ فيرنييه، إي.؛ سونداغ، م.؛ كومبا، ج.؛ سبيكمان، ب.؛ تيليا، أ.؛ فيربيك، ك. (2020). "مقارنة كمية لخرائط الشجرة المعتمدة على الزمن". منتدى رسومات الحاسوب . 39 (3): 393-404 . arXiv : 1906.06014 . doi : 10.1111/cgf.13989 . S2CID 189898065 . 
  4. ↑ شنايدرمان، بن (2001). "تخطيطات خرائط الشجرة المرتبة" (ملف PDF) . إنفوفيس : 73.
  5. ↑ بنجامين، بيدرسون؛ شنايدرمان، بن؛ واتنبرغ، مارتن (2002). "خرائط الأشجار المرتبة والكمية: الاستخدام الفعال للفضاء ثنائي الأبعاد لعرض التسلسلات الهرمية" (ملف PDF) . معاملات ACM في الرسومات . 21 (4): 833-854 . CiteSeerX 10.1.1.145.2634 . doi : 10.1145/571647.571649 . hdl : 1903/6486 . S2CID 7253456 .  
  6. 1 2 3 شنايدرمان، بن؛ واتنبرغ، مارتن (2001). "تخطيطات خرائط الشجرة المرتبة". ندوة IEEE حول تصور المعلومات : 73-78 .
  7. ↑ إنجدال، بيورن. خرائط الأشجار المرتبة والكمية: الاستخدام الفعال للمساحة ثنائية الأبعاد لعرض التسلسلات الهرمية .
  8. ↑ تو، ي.؛ شين، هـ. (2007). "تصور تغيرات البيانات الهرمية باستخدام خرائط الشجرة" (ملف PDF) . معاملات IEEE في التصور ورسومات الحاسوب . 13 (6): 1286-1293 . Bibcode : 2007ITVCG..13.1286T . doi : 10.1109/TVCG.2007.70529 . PMID 17968076. S2CID 14206074. مؤرشف (ملف PDF) من الأصل في 8 أغسطس 2022.  
  9. 1 2 تاك، س.؛ كوكبيرن، أ. (2013). "تحسين الاستقرار المكاني باستخدام خرائط هيلبرت ومور الشجرية" (ملف PDF) . معاملات IEEE في التصور ورسومات الحاسوب . 19 (1): 141-148 . Bibcode : 2013ITVCG..19..141T . doi : 10.1109/TVCG.2012.108 . PMID: 22508907. S2CID : 6099935 .  
  10. ^ برولس ، مارك. هويزينج، كيس؛ فان ويجك، جارك ج. (2000). “الخرائط الشجرة المربعة”. في دي ليو، دبليو؛ فان ليير، ر. (محرران). تصور البيانات 2000: بروك. Eurographics المشتركة وIEEE TCVG Symp. على التصور (PDF) . سبرينغر-فيرلاغ. ص 33 – 42. .
  11. ^ رويل فليجن. إريك جان فان دير ليندن؛ جارك جيه فان ويجك . "تصور بيانات الأعمال باستخدام الخرائط الهيكلية المعممة" (PDF) . مؤرشفة من الأصلي (PDF) في 24 يوليو 2011 . تم الاسترجاع 24 فبراير، 2010 .
  12. ↑ ناغاموتشي، هـ.؛ آبي، ي.؛ واتنبرغ، مارتن (2007). "خوارزمية تقريبية لتقسيم مستطيل إلى مستطيلات بمساحات محددة" . الرياضيات التطبيقية المنفصلة . 155 (4): 523-537 . doi : 10.1016/j.dam.2006.08.005 .
  13. ↑ فاسين فيرنييه، إدواردو؛ ديل كومبا، جواو لويز؛ تيليا، ألكساندرو سي. (2018). "مقارنة كمية لخرائط الشجرة الديناميكية لتصور تطور البرمجيات" (ملف PDF) . وقائع المؤتمر السادس لمعهد مهندسي الكهرباء والإلكترونيات حول تصور البرمجيات . VISSOFT 2018. الصفحات 99-106 . doi : 10.1109/VISSOFT.2018.00018 . hdl : 11370/f2713bfd-5be7-4db4-89f8-cd161b033ce9 . S2CID 53278664. تاريخ الاسترجاع: 15 يناير 2025 .  
  14. ↑ سونداغ، م.؛ سبيكمان، ب.؛ فيربيك، ك. (2018). "خرائط شجرية مستقرة عبر عمليات نقل محلية" (ملف PDF) . معاملات IEEE في التصور ورسومات الحاسوب . 24 (1): 729-738 . Bibcode : 2018ITVCG..24..729S . doi : 10.1109/TVCG.2017.2745140 . PMID: 28866573. S2CID : 27739774 .  
  15. ↑ كريستوف أوناك؛ أناستاسيوس سيديروبولوس. "التقسيمات الدائرية مع تطبيقات في التصور والتضمين" . تم الاطلاع عليه في 26 يونيو 2011 .
  16. ↑ مارك دي بيرغ؛ أوناك، كريستوف؛ سيديروبولوس، أناستاسيوس (2013). "تقسيمات مضلعية سميكة مع تطبيقات في التصور والتضمين" . مجلة الهندسة الحسابية . 4 (1): 212-239 . arXiv : 1009.1866 .
  17. 1 2 دي بيرغ، مارك؛ سبيكمان، بيتينا ؛ فان دير ويل، فنسنت (2014). "خرائط شجرية ذات نسبة عرض إلى ارتفاع محدودة" . الهندسة الحسابية . 47 (6): 683. arXiv : 1012.1749 . doi : 10.1016/j.comgeo.2013.12.008 . S2CID 12973376 . نسخة المؤتمر: خرائط شجرية محدبة ذات نسبة عرض إلى ارتفاع محدودة (PDF) . EuroCG. 2011.
  18. ↑ بالزر، مايكل؛ ديوسن، أوليفر (2005). "خرائط فورونوي الشجرية". في ستاسكو، جون تي؛ وارد، ماثيو أو (محرران). ندوة IEEE حول تصور المعلومات (InfoVis 2005)، 23-25 ​​أكتوبر 2005، مينيابوليس، مينيسوتا، الولايات المتحدة الأمريكية (ملف PDF) . جمعية IEEE للحاسبات. ص 7. .
  19. ↑ واتنبرغ، مارتن (2005). "ملاحظة حول التصورات الفراغية والمنحنيات الفراغية". في: ستاسكو، جون ت.؛ وارد، ماثيو أو. (محرران). ندوة معهد مهندسي الكهرباء والإلكترونيات حول تصور المعلومات (InfoVis 2005)، 23-25 ​​أكتوبر 2005، مينيابوليس، مينيسوتا، الولايات المتحدة الأمريكية (ملف PDF) . جمعية الحاسبات التابعة لمعهد مهندسي الكهرباء والإلكترونيات. ص 24. .
  20. ^ أوبر، ديفيد؛ هيوت، تشارلز. لامبرت، أنطوان. رينوست، بنيامين. سالابيري، أرنو؛ سولنييه، أغنيس (2013). " خريطة جوسبر : استخدام منحنى جوسبر لوضع البيانات الهرمية " معاملات IEEE على التصور ورسومات الكمبيوتر . 19 (11): 1820–1832 . بيب كود : 2013ITVCG ..19.1820A . دوى : 10.1109/TVCG.2013.91 . بميد 24029903 . S2CID 15050386 .  .
  21. ↑ شنايدرمان، بن (1992). "تصوير الشجرة باستخدام خرائط الشجرة: منهج ملء الفراغ ثنائي الأبعاد". معاملات ACM في الرسومات . 11 : 92-99 . doi : 10.1145/102377.115768 . hdl : 1903/367 . S2CID 1369287 . 
  22. ↑ بن شنايدرمان ؛ كاثرين بلايسانت (25 يونيو 2009). "خرائط الشجرة لتصور التسلسلات الهرمية في المساحات المحدودة ~ بما في ذلك تاريخ أبحاث خرائط الشجرة في جامعة ميريلاند" . تم الاطلاع عليه في 23 فبراير 2010 .
  23. ↑ كوكس، أماندا؛ فيرفيلد، هانا (25 فبراير 2007). "صحة سوق السيارات والشاحنات الصغيرة وسيارات الدفع الرباعي والشاحنات" . صحيفة نيويورك تايمز . تم الاطلاع عليه في 12 مارس 2010 .
  24. ↑ كارتر، شان؛ كوكس، أماندا (14 فبراير 2011). "مقترح ميزانية أوباما لعام 2012: كيف تم إنفاق 3.7 تريليون دولار" . صحيفة نيويورك تايمز . تم الاطلاع عليه في 15 فبراير 2011 .
  25. ↑ "فن خرائط الأشجار" . مؤرشف من الأصل في 5 ديسمبر 2023.
  26. ↑ "كل خوارزمية تحتوي على فن: مشروع فن خرائط الشجرة" . CPNAS . مؤرشف من الأصل في 8 أكتوبر 2023.