رسم بياني للرؤية

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة
مثال على رسم بياني للرؤية

في الهندسة الحسابية وتخطيط حركة الروبوتات ، [ 1 ] يُعدّ مخطط الرؤية رسمًا بيانيًا للمواقع المرئية المتبادلة، وعادةً ما يكون ذلك لمجموعة من النقاط والعوائق في المستوى الإقليدي . يُمثّل كل عقدة في المخطط موقعًا نقطيًا، ويمثّل كل ضلع اتصالًا مرئيًا بينهما. أي، إذا لم يمرّ الخط الواصل بين موقعين بأي عائق، يُرسم ضلع بينهما في المخطط. عندما تقع مجموعة المواقع على خط مستقيم، يُمكن فهم ذلك على أنه سلسلة مُرتبة. ولذلك، تم توسيع نطاق استخدام مخططات الرؤية ليشمل تحليل السلاسل الزمنية .

التطبيقات

يمكن استخدام مخططات الرؤية لإيجاد أقصر المسارات الإقليدية بين مجموعة من العوائق المضلعة في المستوى: أقصر مسار بين عائقين يتبع قطعًا مستقيمة باستثناء رؤوس العوائق ، حيث قد ينعطف. لذا، فإن أقصر مسار إقليدي هو أقصر مسار في مخطط رؤية تكون عقده هي نقاط البداية والنهاية ورؤوس العوائق . [ 2 ] بالتالي، يمكن تقسيم مسألة أقصر مسار إقليدي إلى مسألتين فرعيتين أبسط: إنشاء مخطط الرؤية، وتطبيق خوارزمية أقصر مسار، مثل خوارزمية ديكسترا، على المخطط. ولتخطيط حركة روبوت ذي حجم غير مهمل مقارنةً بالعوائق، يمكن استخدام نهج مماثل بعد توسيع العوائق لتعويض حجم الروبوت. [ 2 ] ينسب لوزانو-بيريز وويسلي (1979) طريقة الرسم البياني للرؤية لأقصر المسارات الإقليدية إلى بحث أجراه نيلز نيلسون في عام 1969 حول تخطيط الحركة للروبوت شيكي ، ويستشهدون أيضًا بوصف لهذه الطريقة في عام 1973 من قبل علماء الرياضيات الروس إم بي إغناتييف وإف إم كولاكوف وإيه إم بوكروفسكي.

يمكن أيضًا استخدام مخططات الرؤية لحساب موضع هوائيات الراديو ، أو كأداة تستخدم في الهندسة المعمارية والتخطيط الحضري من خلال تحليل مخططات الرؤية .

يمكن تفسير مخطط الرؤية لمجموعة من المواقع الواقعة على خط مستقيم كتمثيل نظري للمخططات لسلسلة زمنية. [ 3 ] هذه الحالة تحديدًا تُشكل جسرًا بين السلاسل الزمنية والأنظمة الديناميكية ونظرية المخططات .

توصيف

يُمثل مخطط رؤية المضلع البسيط رؤوس المضلع كنقاط مرجعية، بينما يُمثل محيط المضلع العائق الوحيد. يجب أن تكون مخططات رؤية المضلعات البسيطة مخططات هاميلتونية : إذ يُشكل محيط المضلع دورة هاميلتونية في مخطط الرؤية. من المعروف أن ليس كل مخطط رؤية يُنتج مضلعًا بسيطًا. مع ذلك، لا يزال التوصيف الخوارزمي الفعال لمخططات رؤية المضلعات البسيطة غير معروف. لا تندرج هذه المخططات ضمن العديد من عائلات المخططات المعروفة جيدة البنية: فقد لا تكون مخططات مثالية ، أو مخططات دائرية ، أو مخططات وترية . [ 4 ] ويُستثنى من هذه الظاهرة أن مخططات رؤية المضلعات البسيطة هي مخططات "السيطرة والفوز" . [ 5 ]

إن التعرف على الرسم البياني للرؤية لمجموعة محدودة من النقاط في المستوى الإقليدي هو أمر كامل بالنسبة للنظرية الوجودية للأعداد الحقيقية . [ 6 ]

تُعرف مسألة المعرض الفني بأنها إيجاد مجموعة صغيرة من النقاط بحيث تكون جميع النقاط الأخرى غير المعيقة مرئية من هذه المجموعة. ويمكن تفسير بعض أشكال مسألة المعرض الفني على أنها إيجاد مجموعة مهيمنة في رسم بياني للرؤية.

المماسات الثنائية لنظام من المضلعات أو المنحنيات هي خطوط تلامس اثنين منها دون اختراقهما عند نقاط التماس. تشكل المماسات الثنائية لمجموعة من المضلعات مجموعة فرعية من مخطط الرؤية، حيث تمثل رؤوس المضلع عقدها، والمضلعات نفسها تمثل العوائق. يمكن تسريع طريقة مخطط الرؤية لحل مشكلة أقصر مسار إقليدي عن طريق إنشاء مخطط من المماسات الثنائية بدلاً من استخدام جميع حواف الرؤية، لأن أقصر مسار إقليدي لا يدخل أو يخرج من حدود العائق إلا عبر مماس ثنائي. [ 7 ]

انظر أيضاً

ملحوظات

  1. ↑ نيو، هانلين؛ سافاريس، آل؛ تسوردوس، أنطونيوس؛ جي، زي (2019). "خوارزمية تخطيط المسار القائمة على خريطة طريق رؤية فورونوي للمركبات السطحية غير المأهولة" (ملف PDF) . مجلة الملاحة . 72 (4): 850-874 . doi : 10.1017/S0373463318001005 . ISSN 0373-4633 . S2CID 67908628 .  
  2. 1 2 دي بيرج وآخرون. (2000) ، الأقسام 5.1 و5.3؛ لوزانو بيريز وويسلي (1979) .
  3. ↑ لاكاسا، لوكاس؛ لوكي، بارتولو؛ باليستيروس، فرناندو؛ لوكي، جوردي؛ نونو، خوان كارلوس (2008). " من السلاسل الزمنية إلى الشبكات المعقدة: مخطط الرؤية" . وقائع الأكاديمية الوطنية للعلوم . 105 (13): 4972-4975 . arXiv : 0810.0920 . Bibcode : 2008PNAS..105.4972L . doi : 10.1073/pnas.0709247105 . PMC 2278201. PMID 18362361 .  
  4. ↑ غوش، إس كيه (1997-03-01). "حول التعرف على رسوم بيانية الرؤية للمضلعات البسيطة وتوصيفها" . الهندسة المنفصلة والحسابية . 17 (2): 143-162 . doi : 10.1007/BF02770871 . ISSN 0179-5376 . 
  5. ↑ لوبيو، آنا ؛ سنويينك، جاك؛ فوسوغبور، حميدة (2017). "مخططات الرؤية، وقابلية التفكيك، ولعبة الشرطة واللصوص". الهندسة الحسابية . 66 : 14-27 . arXiv : 1601.01298 . doi : 10.1016/j.comgeo.2017.07.001 . MR 3693353 . 
  6. ↑ كاردينال، جان؛ هوفمان، أودو (2017). "التعرف على رسوم بيانية لرؤية النقاط وتعقيدها". الهندسة المنفصلة والحسابية . 57 (1): 164-178 . arXiv : 1503.07082 . doi : 10.1007/s00454-016-9831-1 . MR 3589061 . 
  7. ^ دي بيرج وآخرون. (2000) ، ص. 316.

مراجع

  • دي بيرج، مارك؛ فان كريفيلد، مارك؛ أوفرمارس, مارك ; Schwarzkopf، Otfried (2000)، “Chapter 15: Visibility Graphs”، الهندسة الحسابية (  الطبعة الثانية)، Springer-Verlag ، الصفحات من 307 إلى 317 ، ISBN  978-3-540-65620-3.
  • لوزانو-بيريز، توماس؛ ويسلي، مايكل أ. (1979)، "خوارزمية لتخطيط مسارات خالية من التصادم بين العوائق متعددة الأوجه"، اتصالات رابطة مكائن ​​الحوسبة ، 22 (10): 560-570 ، doi : 10.1145/359156.359164 ، S2CID 17397594 .