موضوع مقاله: چاردرخت | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # چاردرخت | مقدمه: این داده‌ساختار معمولاً برای افراز یک فضای دوبعدی به صورت بازگشتی به تعدادی ناحیه (چارک) استفاده می‌شود. | ## بخش 1: چاردرخت | همۀ انواع چاردرخت، در تعدادی ویژگی مشترکند: فضا را به تعدادی ناحیه تقسیم می‌کنند. انواع چاردرخت‌ها را می‌توان بر اساس نوع داده‌ای که نمایش می‌دهند (مثل سطح، نقطه، خط یا منحنی) تقسیم‌بندی کرد. یک نحوۀ دیگر تقسیم‌بندی بر این اساس است که آیا شکل درخت ایجادشده مستقل از ترتیب پردازش داده‌ها است یا خیر. تعدادی از چاردرخت‌های متداول عبارتند از: چاردرخت ناحیه‌ای این نوع چاردرخت، نمایشگر افرازی از یک صفحۀ دوبعدی است که در آن افراز، صفحۀ دوبعدی به چهار ناحیۀ برابر افراز شده و برخی ناحیه‌ها خود به چهار زیرناحیۀ برابر افراز شده‌اند و به همین ترتیب فرایند افراز می‌تواند ادامه پیدا کند. هر برگ از درخت مربوط به یکی از زیر‌ناحیه‌‌های افراز است و اطلاعات آن زیرناحیه در آن برگ ذخیره می‌شود. می‌توان از یک چاردرخت ناحیه‌ای با ارتفاع n برای نمایش یک تصویر با ابعاد 2n × 2n پیکسل (که مقدار هر پیکسل ۰ یا ۱ است) استفاده کرد. هر ناحیه‌ای که مقدار همۀ پیکسل‌هایش با هم برابر نیست، به ۴ زیرناحیه تقسیم می‌شود. در نهایت هر برگ از درخت، مجموعه‌ای مربع‌شکل از تعدادی پیکسل را نشان می‌دهد که همگی ۰ یا همگی ۱ هستند. | ## بخش 2: چاردرخت | اگر چاردرخت ناحیه‌ای برای نمایش مجموعه‌ای از نقاط (مثلاً تعدادی شهر که با طول و عرض جغرافیایی مشخص شده‌اند) استفاده شود، ناحیه‌ها تا جایی تقسیم می‌شوند که هر زیرناحیه حداکثر یک نقطه را شامل شود. ولی از چاردرخت نقطه‌ای می‌توان برای ذخیره تعدادی نقطه (دوتایی مرتب) از فضای دوبعدی استفاده کرد. یعنی گره‌های درخت، خود نقاطی هستند که می‌خواهیم نمایش دهیم (برخلاف چاردرخت ناحیه‌ای، وقتی که برای نمایش تعدادی نقطه مورد استفاده قرار بگیرد). شکل ناحیه‌های ایجاد شده به ترتیب اضافه کردن نقاط بستگی دارد (درست مثل درخت دودویی جستجو). چاردرخت نقطه‌ای، معمولاً برای مقایسه بین مجموعه‌ای از نقاط در صفحۀ دوبعدی بسیار بهینه (معمولاً از O(log n عمل می‌کند. ساختار گره‌ها در یک چاردرخت نقطه‌ای در یک چاردرخت نقطه‌ای، گره‌ها مشابه گره‌های درخت دودویی هستند. با این تفاوت که در این‌جا هر گره به جای دو اشاره‌گر «راست» و «چپ» درخت دودویی، چهار اشاره‌گر دارد (به ازای هر زیرناحیه یک اشاره‌گر). همچنین کلید عناصر ذخیره‌شده به دو قسمت تقسیم می‌شود (نشان‌دهنده طول و عرض نقاط). | ## بخش 3: چاردرخت | با این توضیحات، در هر گره از درخت این اطلاعات وجود دارد: چهار اشاره‌گر: به ترتیب چارک NW، چارک NE، چارک SW و چارک SE نقطه. که شامل کلید و مقدار می‌شود: کلید: معمولاً با دو مختصه x و y نمایش داده می‌شود مقدار: مثلاً یک نام چاردرخت یالی این چاردرخت برای ذخیرۀ خط و منحنی (به جای نقطه) استفاده می‌شود. این کار ممکن است باعث شود که یک درخت بسیار نامتوازن ایجاد شود که با هدف کاراتر شدن دسترسی‌ها تناقض دارد. چاردرخت PM2 همانند PM3 است با این تفاوت که همه ضلع‌ها باید نقطۀ پایانی یکسان داشته باشند. ولی گره‌های سیاه می‌توانند یک نقطه و ضلع‌های متصل به آن یا فقط تعدادی ضلع که در یک نقطه مشترک هستند را در خود ذخیره کنند، ولی نمی‌توان یک نقطه و تعدادی ضلع که در آن نقطه مشترک نیستند را در گره ذخیره کرد. کاربردهای دیگر ذخیره‌سازی تصویر380px|یک تصویر بیت‌مپ و نمایش چاردرختی فشرده متناظر آن نمایه‌سازی فضایی تشخیص بهینۀ برخورد اشیا در دو بعد ذخیرۀ داده‌های تنک (مثل اطلاعات قالب‌بندی یک صفحه‌گسترده، یا مثل محاسبات ماتریسی) حل میدان های چندبعدی (دینامیک سیالات محاسباتی، الکترومغناطیس) برنامۀ شبیه‌ساز بازی زندگی کانوی تخمین وضعیت تحلیل تصاویر برخالی چاردرخت، معادل دوبعدی هشت‌درخت است. | ## جمع‌بندی | شبه کد این شبه کد، روشی برای پیاده‌سازی یک چاردرخت است که فقط نقاط را ذخیره می‌کند.