موضوع مقاله: درخت هشت‌تایی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت هشت‌تایی | مقدمه: درخت هشت‌تایی (به انگلیسی: Octree) یک داده‌ساختار درخت است که در آن هر گره داخلی دقیقاً هشت فرزند دارد. | ## بخش 1: درخت هشت‌تایی | درخت‌های هشت‌تایی اغلب برای افراز کردن یک فضای سه‌بعدی از طریق تقسیم بازگشتی آن فضا به هشت قسمت مساوی استفاده می‌شوند. درخت‌های هشت‌تایی غالباً در گرافیک سه‌بعدی رایانه‌ای و موتورهای بازی سه‌بعدی استفاده می‌شوند. درخت‌های هشت‌تایی برای نمایش فضایی هر گره در یک درخت هشت‌تایی فضا را به هشت اکتان تقسیم می‌کند. در یک درخت هشت‌تایی نقطه‌ای ناحیه‌ای، هر گره در واقع یک نقطه سه‌بعدی را نگه می‌دارد که مرکز قسمتی است که مربوط به آن گره است؛ این نقطه گوشه مشترک هر هشت فرزند گره است. در یک درخت هشت‌تایی نقطه‌ای که حول آن فضا تقسیم می‌شود به‌طور ضمنی مرکز قسمتی است که گره نمایش می‌دهد. گره ریشه از یک درخت هشت‌تایی PR می‌تواند فضای نامحدود را نشان دهد؛ در حالی که گره ریشه از یک درخت هشت‌تایی MX باید یک فضای محدود را نشان دهد که مرکزهای هر قسمت قابل تعریف باشند. درخت‌های کی‌دی در راستای یک بعد تقسیم‌بندی انجام می‌دهند اما درخت‌های هشت‌تایی پیرامون یک نقطه (در راستای سه‌بعد) تقسیم‌بندی انجام می‌دهند. همچنین درخت‌های کی‌دی همواره دودویی‌اند که در مورد درخت‌های هشت‌تایی این گونه نیست. | ## بخش 2: درخت هشت‌تایی | با به‌کارگیری جستجوی عمق اول (dfs) باید گره‌ها پیمایش شوند اما فقط سطوح مورد نیاز در نظر گرفته شوند. تاریخچه درخت هشت‌تایی برای گرافیک سه‌بعدی رایانه‌ای اولین بار توسط دونالر میقر در مؤسسه پلی‌تکنیک رنسلیر استفاده شد، که در گزارش سال ۱۹۸۰ با عنوان "رمزگذاری درخت‌های هشت‌تایی: یک راه جدید برای نمایش دوباره، دست‌کاری و نمایش دلخواه اشیاء سه‌بعدی به وسیلهٔ کامپیوتر" آن را شرح داد. او صاحب ثبت اختراع ۱۹۹۵ (با تاریخ اولویت ۱۹۸۴) با عنوان "تولید سریع عکس از اشیاء جامد پیچیده به وسیلهٔ رمزگذاری درخت هشت‌تایی" نیز بود. کاربردهای رایج درخت هشت‌تایی گرافیک سه‌بعدی رایانه‌ای نمایه‌سازی فضایی جستجوی نزدیکترین همسایه تشخیص برخورد کارآمد در فضای سه‌بعدی نمایش سطوح پنهان روش سریع چند قطبی شبکه‌های بدون ساختار تحلیل اجزاء محدود درخت هشت‌تایی پراکنده واکسل تخمین حالت تخمین مجموعه و. زر، "شخصیت تضمین شدهٔ فضای کشف‌شده از روبات‌های موبایل به وسیله‌ی سابپوینگ"، ان‌او‌ال‌سی‌او‌اس ۲۰۱۳. کاربرد در درجه‌بندی رنگ‌ها الگوریتم درجه‌بندی رنگ در درخت هشت‌تایی توسط گرواتز و پورگاتوفر در سال ۱۹۸۸ ابداع شد. این الگوریتم داده‌های مربوط به رنگ یک تصویر را به صورت درخت هشت‌تایی درآورده و درخت را تا عمق ۹ سطح کدگذاری می‌کند. از آنجا که در سیستم رنگی آرجی‌بی سه مؤلفه رنگی وجود دارد و ۸=۳^۲ از درخت هشت‌تایی استفاده می‌شود. | ## بخش 3: درخت هشت‌تایی | شماره مربوط به یک گره در سطح بالا با یک فرمول مشخص می‌شود که از پرارزش‌ترین بیت‌های مؤلفه‌های رنگی قرمز، سبز و آبی استفاده می‌کند، مثلاً 4r + 2g + b. سطح بعدی یا پایین‌تر از بیت‌های پرارزش بعدی استفاده می‌کند و به همین ترتیب جلو می‌رود. این الگوریتم از لحاظ مصرف حافظه بسیار بهینه است چرا که اندازه درخت می‌تواند محدود باشد. سطح پایین یک درخت هشت‌تایی از برگ‌هایی که به داده‌های رنگی مربوطند و در درخت نمایش داده نمی‌شوند، تشکیل می‌گردد. اگر تعداد بیشتری از یک مقدار دلخواه رنگ از پالت‌ها وارد درخت شوند، اندازه درخت می‌تواند به صورت پیوسته کاهش یابد. این کار با دنبال کردن یک گره سطح پایین و افزایش میانگین مقدار بیتی آن تا رسیدن به برگ ادامه می‌یابد. هنگامی که این کار به‌طور کامل انجام شود، با پیمایش همهٔ مسیرهای درخت تا برگ‌ها و در نظر گرفتن بیت‌ها در طول مسیر می‌توان به‌طور تقریبی تعداد رنگ‌های لازم را به دست آورد. آی‌دی تک ۶ یک موتور بازی سه‌بعدی در حال توسعه که واکسل‌هایی را که در درخت هشت‌تایی استفاده می‌شوند به‌کار می‌گیرد. | ## جمع‌بندی | یونیکریشان، ک پلوز جاکوب، ICIP 1997، کتابخانهٔ مجازی مؤسسه مهندسان برق و الکترونیک نسلی از درخت‌های هشت‌تایی از پویش شطرنجی با از دست رفتن اطلاعات کمتر، پ.