گراف پدیداری

در هندسهٔ محاسباتی و ناوبری روبات‌ها، گراف پدیداری  گرافی است شامل نقاطی که از ناحیهٔ منطقهٔ مورد نظر قابل دید است. در واقع هر گره نمایش دهندهٔ مکانی در محیط است و لبهٔ گراف بین دو نقطهٔ مورد نظر، نشان دهندهٔ ارتباط بین آن دو نقطه، یا دیده شدن یکی از نقاط با قرار گرفتن در نقطهٔ دیگر است و هیج مانعی سد راه دیده شدن این دو نقطه از همدیگر نمی‌شود.

 کاربردها 
با استفاده از گراف‌های پدیداری می‌توان کمینه فاصله اقلیدسی بین دو نقطهٔ مورد نظر در فضایی شامل موانع چند ضلعی را پیدا کرد. همیشه کمترین فاصله بین دو نقطه خط راست بین آن دو نقطه هست، مگر آنکه مانعی در میان مسیر مورد نظر باشد. در اینصورت گوشهٔ چند ضلعی مورد نظر باید به عنوان یکی از نقاط میانی(راس‌های گراف پدیداری) انتخاب کرد. به اینصورت می‌توان مسئلهٔ مسیر بهینه در فضای اقلیدسی را به مسئلهٔ کوتاه‌ترین مسیر در یک گراف تبدیل کرد.
اکنون در اینجا می‌توان مسئله را به قسمت تقسیم کرد: (۱)ساختن گراف پدیداری از روی مسئلهٔ کوتاه‌ترین مسیر در فضای اقلیدسی (۲) حل مسئلهٔ کوتاه‌ترین مسیر مانند الگوریتم دایکسترا در یک گراف.
برای مسیر یابی روباتی که دارای اندازه‌ای قابل توجه است، می‌توان مسئله را تعمیم داد. در واقع در این حالت مسیر بهینه نمی‌تواند کاملاً در لبهٔ موانع عبور کند. چون اگر اینطور باشد، روبات با شعاع غیر جزئی با موانع برخورد می‌کند. مسئله را می‌توان به اینصورت حل کرد که موانع را کمی بزرگتر از آنچه هستند در نظر گرفت و سپس مراحل فوق را در این حالت انجام داد.
یکی دیگر از کاربردهای گراف پدیداری در بدست آوردن مکان بهینه برای قرار دادن آنتن‌های رادیویی است.

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

 مسئله‌های مرتبط 
در مسئلهٔ نگارخانه هنری (هندسه) هدف پیدا کردن مجموعه از نقاط در محیط است، بطوریکه بتوان تمام نقاط در محیط را از روی آن نقاط به‌طور کامل مشاهده کرد. برخی از حالت‌های مسئلهٔ نگارخانه هنری را می‌توان به صورتی معادل از طریق پیدا کردن زیر مجموعهٔ غالب در یک گراف حل کرد.
خطوط bitanget مجموعه‌ای از اشکال عبارت است از کلیهٔ خطوطی که حداقل بر دو نقطه از شکل مماس باشند. مجموعهٔ bitangetهای یک مجموعه چند ضلعی، یک گراف پدیداری تشکیل می‌دهند که راس‌های آن شامل گوشه‌های چندضلعی‌ها هستند و داخل چند ضلعی‌ها به عنوان موانع محیط محسوب می‌شوند. یکی از ایده‌ها برای بهینه تر کردن عملکرد گراف‌های پدیداری استفاده از bianget در ساختن آنهاست.

 منابع 

 .
 .

 پیوند به بیرون 
 VisiLibity: A free open source C++ library of floating-point visibility algorithms and supporting data types. This software can be used for calculating visibility graphs of polygonal environments with polygonal holes. A Matlab interface is also included.

 جستارهای وابسته 
 آنالیز گراف پدیداری

رده:کنترل ربات
رده:گراف‌های هندسی
رده:هندسه محاسباتی