درخت هشت تایی ( به انگلیسی: Octree ) یک داده ساختار درخت است که در آن هر گره داخلی دقیقاً هشت فرزند دارد. درخت های هشت تایی اغلب برای افراز کردن یک فضای سه بعدی از طریق تقسیم بازگشتی آن فضا به هشت قسمت مساوی استفاده می شوند. درخت های هشت تایی در واقع معادل چاردرخت در حالت سه بعدی اند. اسم این درخت از دو کلمه انگلیسی oct و tree تشکیل شده است، اما توجه کنید که این کلمه معمولاً به صورت octree فقط با یک حرف t نوشته می شود. درخت های هشت تایی غالباً در گرافیک سه بعدی رایانه ای و موتورهای بازی سه بعدی استفاده می شوند.
هر گره در یک درخت هشت تایی فضا را به هشت اکتان تقسیم می کند. در یک درخت هشت تایی نقطه ای ناحیه ای، هر گره در واقع یک نقطه سه بعدی را نگه می دارد که مرکز قسمتی است که مربوط به آن گره است؛ این نقطه گوشه مشترک هر هشت فرزند گره است. در یک درخت هشت تایی نقطه ای که حول آن فضا تقسیم می شود به طور ضمنی مرکز قسمتی است که گره نمایش می دهد. گره ریشه از یک درخت هشت تایی PR می تواند فضای نامحدود را نشان دهد؛ در حالی که گره ریشه از یک درخت هشت تایی MX باید یک فضای محدود را نشان دهد که مرکزهای هر قسمت قابل تعریف باشند. توجه داشته باشید که درخت هشت تایی با درخت کی دی متفاوت است. درخت های کی دی در راستای یک بعد تقسیم بندی انجام می دهند اما درخت های هشت تایی پیرامون یک نقطه ( در راستای سه بعد ) تقسیم بندی انجام می دهند. همچنین درخت های کی دی همواره دودویی اند که در مورد درخت های هشت تایی این گونه نیست. با به کارگیری جستجوی عمق اول ( dfs ) باید گره ها پیمایش شوند اما فقط سطوح مورد نیاز در نظر گرفته شوند.
درخت هشت تایی برای گرافیک سه بعدی رایانه ای اولین بار توسط دونالر میقر در مؤسسه پلی تکنیک رنسلیر استفاده شد، که در گزارش سال ۱۹۸۰ با عنوان "رمزگذاری درخت های هشت تایی: یک راه جدید برای نمایش دوباره، دست کاری و نمایش دلخواه اشیاء سه بعدی به وسیلهٔ کامپیوتر"[ ۱] آن را شرح داد. او صاحب ثبت اختراع ۱۹۹۵ ( با تاریخ اولویت ۱۹۸۴ ) با عنوان "تولید سریع عکس از اشیاء جامد پیچیده به وسیلهٔ رمزگذاری درخت هشت تایی"[ ۲] نیز بود.
• گرافیک سه بعدی رایانه ای
• نمایه سازی فضایی
• جستجوی نزدیکترین همسایه
• تشخیص برخورد کارآمد در فضای سه بعدی
• نمایش سطوح پنهان
• روش سریع چند قطبی
• شبکه های بدون ساختار
• تحلیل اجزاء محدود
• درخت هشت تایی پراکنده واکسل
• تخمین حالت [ ۳]
• تخمین مجموعه [ ۴]
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفهر گره در یک درخت هشت تایی فضا را به هشت اکتان تقسیم می کند. در یک درخت هشت تایی نقطه ای ناحیه ای، هر گره در واقع یک نقطه سه بعدی را نگه می دارد که مرکز قسمتی است که مربوط به آن گره است؛ این نقطه گوشه مشترک هر هشت فرزند گره است. در یک درخت هشت تایی نقطه ای که حول آن فضا تقسیم می شود به طور ضمنی مرکز قسمتی است که گره نمایش می دهد. گره ریشه از یک درخت هشت تایی PR می تواند فضای نامحدود را نشان دهد؛ در حالی که گره ریشه از یک درخت هشت تایی MX باید یک فضای محدود را نشان دهد که مرکزهای هر قسمت قابل تعریف باشند. توجه داشته باشید که درخت هشت تایی با درخت کی دی متفاوت است. درخت های کی دی در راستای یک بعد تقسیم بندی انجام می دهند اما درخت های هشت تایی پیرامون یک نقطه ( در راستای سه بعد ) تقسیم بندی انجام می دهند. همچنین درخت های کی دی همواره دودویی اند که در مورد درخت های هشت تایی این گونه نیست. با به کارگیری جستجوی عمق اول ( dfs ) باید گره ها پیمایش شوند اما فقط سطوح مورد نیاز در نظر گرفته شوند.
درخت هشت تایی برای گرافیک سه بعدی رایانه ای اولین بار توسط دونالر میقر در مؤسسه پلی تکنیک رنسلیر استفاده شد، که در گزارش سال ۱۹۸۰ با عنوان "رمزگذاری درخت های هشت تایی: یک راه جدید برای نمایش دوباره، دست کاری و نمایش دلخواه اشیاء سه بعدی به وسیلهٔ کامپیوتر"[ ۱] آن را شرح داد. او صاحب ثبت اختراع ۱۹۹۵ ( با تاریخ اولویت ۱۹۸۴ ) با عنوان "تولید سریع عکس از اشیاء جامد پیچیده به وسیلهٔ رمزگذاری درخت هشت تایی"[ ۲] نیز بود.
• گرافیک سه بعدی رایانه ای
• نمایه سازی فضایی
• جستجوی نزدیکترین همسایه
• تشخیص برخورد کارآمد در فضای سه بعدی
• نمایش سطوح پنهان
• روش سریع چند قطبی
• شبکه های بدون ساختار
• تحلیل اجزاء محدود
• درخت هشت تایی پراکنده واکسل
• تخمین حالت [ ۳]
• تخمین مجموعه [ ۴]
wiki: درخت هشت تایی