درخت هشت‌تایی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
چپ: تقسیم بازگشتی یک مکعب به اکتان. راست: درخت هشت‌تایی معادل.

درخت هشت‌تایی (به انگلیسی: Octree) یک داده‌ساختار درخت است که در آن هر گره داخلی دقیقاً هشت فرزند دارد. درخت‌های هشت‌تایی اغلب برای افراز کردن یک فضای سه‌بعدی از طریق تقسیم بازگشتی آن فضا به هشت قسمت مساوی استفاده می‌شوند. درخت‌های هشت‌تایی در واقع معادل چاردرخت در حالت سه بعدی اند. اسم این درخت از دو کلمه انگلیسی oct و tree تشکیل شده است، اما توجه کنید که این کلمه معمولاً به صورت octree فقط با یک حرف t نوشته می‌شود. درخت‌های هشت‌تایی غالباً در گرافیک سه‌بعدی رایانه‌ای و موتورهای بازی سه‌بعدی استفاده می‌شوند.

درخت‌های هشت‌تایی برای نمایش فضایی[ویرایش]

هر گره در یک درخت هشت‌تایی فضا را به هشت اکتان تقسیم می‌کند. در یک درخت هشت‌تایی نقطه‌ای ناحیه‌ای، هر گره در واقع یک نقطه سه‌بعدی را نگه می‌دارد که مرکز قسمتی است که مربوط به آن گره است؛ این نقطه گوشه مشترک هر هشت فرزند گره است. در یک درخت هشت‌تایی نقطه‌ای که حول آن فضا تقسیم می‌شود به طور ضمنی مرکز قسمتی است که گره نمایش می‌دهد. گره ریشه از یک درخت هشت‌تایی PR می‌تواند فضای نامحدود را نشان دهد؛ در حالی که گره ریشه از یک درخت هشت‌تایی MX باید یک فضای محدود را نشان دهد که مرکزهای هر قسمت قابل تعریف باشند. توجه داشته باشید که درخت‌ هشت‌تایی با درخت کی‌دی متفاوت است. درخت‌های کی‌دی در راستای یک بعد تقسیم‌بندی انجام می‌دهند اما درخت‌های هشت‌تایی پیرامون یک نقطه (در راستای سه‌بعد) تقسیم‌بندی انجام می‌دهند. همچنین درخت‌های کی‌دی همواره دودویی‌اند که در مورد درخت‌های هشت‌تایی این گونه نیست. با به‌کارگیری جستجوی عمق اول (dfs) باید گره‌ها پیمایش شوند اما فقط سطوح مورد نیاز در نظر گرفته شوند.

تاریخچه[ویرایش]

درخت هشت‌تایی برای گرافیک سه‌بعدی رایانه‌ای اولین بار توسط دونالر میقر در مؤسسه پلی‌تکنیک رنسلیر استفاده شد، که در گزارش سال ۱۹۸۰ با عنوان "رمزگذاری درخت‌های هشت‌تایی: یک راه جدید برای نمایش دوباره، دست‌کاری و نمایش دلخواه اشیاء سه‌بعدی به وسیلهٔ کامپیوتر"[۱] آن را شرح داد. او صاحب ثبت اختراع ۱۹۹۵ (با تاریخ اولویت ۱۹۸۴) با عنوان "تولید سریع عکس از اشیاء جامد پیچیده به وسیلهٔ رمزگذاری درخت هشت‌تایی"[۲] نیز بود.

کاربردهای رایج درخت هشت‌تایی[ویرایش]

کاربرد در درجه‌بندی رنگ‌ها[ویرایش]

الگوریتم درجه‌بندی رنگ در درخت هشت‌تایی توسط گرواتز و پورگاتوفر در سال ۱۹۸۸ ابداع شد. این الگوریتم داده‌های مربوط به رنگ یک تصویر را به صورت درخت هشت‌تایی درآورده و درخت را تا عمق ۹ سطح کدگذاری می‌کند. از آنجا که در سیستم رنگی آرجی‌بی سه مولفه رنگی وجود دارد و ۸=۳^۲ از درخت هشت‌تایی استفاده می‌شود. شماره مربوط به یک گره در سطح بالا با یک فرمول مشخص می‌شود که از پرارزش‌ترین بیت‌های مولفه‌های رنگی قرمز، سبز و آبی استفاده می‌کند، مثلاً 4r + 2g + b. سطح بعدی یا پایین‌تر از بیت‌های پرارزش بعدی استفاده می‌کند و به همین ترتیب جلو می‌رود. گاهی بیت‌های کم ارزش نادیده گرفته می‌شوند تا اندازه درخت کاهش یابد. این الگوریتم از لحاظ مصرف حافظه بسیار بهینه است چرا که اندازه درخت می‌تواند محدود باشد. سطح پایین یک درخت هشت‌تایی از برگ‌هایی که به داده‌های رنگی مربوطند و در درخت نمایش داده نمی‌شوند، تشکیل می‌گردد. این گره‌ها در ابتدا حاوی تک‌بیت‌ها هستند. اگر تعداد بیشتری از یک مقدار دلخواه رنگ از پالت‌ها وارد درخت شوند، اندازه درخت می‌تواند به صورت پیوسته کاهش یابد. این کار با دنبال کردن یک گره سطح پایین و افزایش میانگین مقدار بیتی آن تا رسیدن به برگ ادامه می‌یابد. در واقع به این ترتیب قسمتی از درخت هرس می‌شود. هنگامی که این کار به طور کامل انجام شود، با پیمایش همهٔ مسیرهای درخت تا برگ‌ها و در نظر گرفتن بیت‌ها در طول مسیر می‌توان به طور تقریبی تعداد رنگ‌های لازم را به دست آورد.

جستارهای وابسته[ویرایش]

پانویس[ویرایش]

  1. میقر, دونالد (اکتبر 1980). "درخت‌هشت‌تایی Encoding: یک راه جدید برای نمایش دوباره، دست‌کاری و نمایش دلخواه اشیاء سه‌بعدی به وسیلهٔ کامپیوتر". مؤسسه پلی‌تکنیک رنسلیر (گزارش فنی IPL-TR-80-111). 
  2. میقر, دونالد. "تولید سریع عکس از اشیاء جامد پیچیده به وسیلهٔ رمزگذاری درخت هشت‌تایی". یواس‌پی‌او. Retrieved 20 سپتامبر 2012. 
  3. هنینگ ابرهاردت، وسا کلومپ، یوه د. هانبک، "درخت‌های چگالی برای تخمین وضعیت بهینه غیرخطی"، مجموعه مقالات ۱۳امین کنفرانس بین‌المللی همجوشی اطلاعات، ادینبرگ، انگلیس، جولای، ۲۰۱۰.
  4. و. دروله، ل. جاولین و ب. زر، "شخصیت تضمین شدهٔ فضای کشف‌شده از روبات‌های موبایل به وسیله‌ی سابپوینگ"، ان‌او‌ال‌سی‌او‌اس ۲۰۱۳.

منابع[ویرایش]

مشارکت‌کنندگان ویکی‌پدیا، «Octree»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳۰ اردیبهشت ۱۳۹۳).

پیوند به بیرون[ویرایش]