Visibility graph
کمپیوٹیشنل جیومیٹری اور روبوٹ موشن پلاننگ میں، مرئیت گراف غیر مرئی مقامات کا ایک گراف ہے، عام طور پر یوکلڈین سطح میں پوائنٹس اور رکاوٹوں کے ایک سیٹ کے لیے۔ گراف میں ہر نوڈ ایک نقطہ کے مقام کی نمائندگی کرتا ہے، اور ہر کنارے ان کے درمیان نظر آنے والے تعلق کی نمائندگی کرتا ہے۔ یعنی، اگر دو مقامات کو جوڑنے والی لائن کا حصہ کسی رکاوٹ سے نہیں گزرتا ہے، تو گراف میں ان کے درمیان ایک کنارہ کھینچا جاتا ہے۔ جب مقامات کا مجموعہ ایک لائن میں ہوتا ہے، تو اسے ایک ترتیب شدہ سیریز کے طور پر سمجھا جا سکتا ہے۔ اس لیے مرئیت کے گراف کو ٹائم سیریز تجزیہ کے دائرے تک بڑھا دیا گیا ہے۔ ایپلی کیشنز طیارہ میں کثیر الجہتی رکاوٹوں کے ایک سیٹ کے درمیان یوکلڈین مختصر ترین راستوں کو تلاش کرنے کے لیے ویزیبلٹی گراف کا استعمال کیا جا سکتا ہے: دو رکاوٹوں کے درمیان مختصر ترین راستہ سیدھی لکیر کے حصوں کی پیروی کرتا ہے سوائے رکاوٹوں کے عمودی حصوں کے، جہاں یہ مڑ سکتا ہے، لہذا یوکلڈین مختصر ترین راستہ مرئیت کے گراف میں مختصر ترین راستہ ہے جس میں اس کے نوڈس کے طور پر آغاز اور منزل کے نکات اور رکاوٹوں کے عمودی حصے ہوتے ہیں۔ لہذا، یوکلڈین کے مختصر ترین راستے کے مسئلے کو دو آسان ذیلی مسائل میں تقسیم کیا جا سکتا ہے: مرئیت گراف کی تعمیر، اور گراف پر ڈیجسٹرا کے الگورتھم جیسے مختصر ترین راستے کے الگورتھم کا اطلاق۔ رکاوٹوں کے مقابلے میں غیر معمولی سائز والے روبوٹ کی حرکت کی منصوبہ بندی کے لیے، روبوٹ کے سائز کی تلافی کے لیے رکاوٹوں کو بڑھانے کے بعد اسی طرح کا نقطہ نظر استعمال کیا جا سکتا ہے۔ 1969 میں نیلز نیلسن کی طرف سے شیکی روبوٹ کے لیے موشن پلاننگ پر تحقیق کے لیے یوکلیڈین کے مختصر ترین راستوں کے لیے مرئیت گراف کے طریقہ کار کو منسوب کریں، اور روسی ریاضی دانوں ایم۔ بی۔ اگناٹیوف، ایف۔ ایم۔ کولاکوف، اور اے۔ ایم۔ پوکرووسکی کی طرف سے اس طریقہ کار کی 1973 کی تفصیل کا بھی حوالہ دیں۔ وزیبلٹی گراف کا استعمال ریڈیو اینٹینا کی جگہ کا حساب لگانے کے لیے بھی کیا جا سکتا ہے، یا وزیبلٹی گراف تجزیہ کے ذریعے فن تعمیر اور شہری منصوبہ بندی کے اندر استعمال ہونے والے آلے کے طور پر بھی کیا جا سکتا ہے۔ ایک لائن میں موجود مقامات کے سیٹ کے مرئیت گراف کی تشریح ٹائم سیریز کے گراف نظریاتی نمائندگی کے طور پر کی جا سکتی ہے۔ یہ خاص معاملہ ٹائم سیریز، متحرک نظام اور گراف تھیوری کے درمیان ایک پل بناتا ہے۔ خصوصیت ایک سادہ کثیر الاضحی کی مرئیت کے گراف میں کثیر الاضحی کے عمودی حصے اس کے نقطہ مقامات کے طور پر ہوتے ہیں، اور کثیر الاضحی کا بیرونی حصہ واحد رکاوٹ ہوتا ہے۔ سادہ کثیر الاضحی کے مرئی گراف ہیملٹنین گراف ہونے چاہئیں: کثیر الاضحی کی حد مرئی گراف میں ہیملٹنین سائیکل بناتی ہے۔ یہ معلوم ہے کہ تمام مرئیت والے گراف ایک سادہ کثیر الاضحی کو متاثر نہیں کرتے۔ تاہم، سادہ کثیر الاضلاعات کی مرئیت کے گراف کی ایک موثر الگورتھمک خصوصیت نامعلوم ہے۔ یہ گراف اچھی طرح سے تشکیل شدہ گراف کے بہت سے معروف خاندانوں میں نہیں آتے ہیں: وہ کامل گراف، سرکل گراف، یا کورڈل گراف نہیں ہو سکتے ہیں۔ اس رجحان کی ایک رعایت یہ ہے کہ سادہ کثیر الاضحی کی مرئیت کے گراف کاپی-ون گراف ہوتے ہیں۔ متعلقہ مسائل آرٹ گیلری کا مسئلہ پوائنٹس کے ایک چھوٹے سے سیٹ کو تلاش کرنے کا مسئلہ ہے جیسے کہ اس سیٹ سے دیگر تمام غیر رکاوٹ والے پوائنٹس نظر آتے ہیں۔ آرٹ گیلری کے مسئلے کی کچھ شکلوں کی تشریح مرئیت کے گراف میں غالب سیٹ تلاش کرنے کے طور پر کی جا سکتی ہے۔ کثیر الاضحی یا منحنی خطوط کے نظام کے بٹینجینٹ وہ لکیریں ہیں جو ان میں سے دو کو ان کے رابطے کے مقامات پر داخل کیے بغیر چھوتی ہیں۔ کثیر الاضحی کے ایک سیٹ کے بٹینجینٹ مرئیت کے گراف کا ایک ذیلی سیٹ بناتے ہیں جس میں کثیر الاضحی کے عمودی نوڈس ہوتے ہیں اور کثیر الاضحی خود رکاوٹوں کے طور پر ہوتے ہیں۔ یوکلڈین کے مختصر ترین راستے کے مسئلے کے لیے مرئیت گراف کے نقطہ نظر کو تمام مرئیت کے کناروں کو استعمال کرنے کے بجائے بٹینجینٹس سے گراف بنا کر تیز کیا جا سکتا ہے، کیونکہ یوکلڈین کا مختصر ترین راستہ صرف بٹینجینٹ کے ساتھ کسی رکاوٹ کی حد میں داخل ہو سکتا ہے یا چھوڑ سکتا ہے۔ ویزیبلٹی گراف تجزیہ فجی آرکیٹیکچرل اسپاٹیل تجزیہ اسپیس نحو نوٹس حوالہ جات بھی دیکھیں۔ ۔ بیرونی لنکس ویزلیبیٹی: فلوٹنگ پوائنٹ ویزیبلٹی الگورتھم اور معاون ڈیٹا ٹائپز کی ایک مفت اوپن سورس C + + لائبریری۔ اس سافٹ ویئر کو کثیر الاضحی سوراخوں کے ساتھ کثیر الاضحی ماحول کے مرئیت گراف کا حساب لگانے کے لیے استعمال کیا جا سکتا ہے۔ ایک میٹ لیب انٹرفیس بھی شامل ہے۔ روبوٹ جیومیٹرک گراف کو کنٹرول کرتا ہے کمپیوٹیشنل جیومیٹری