|
تضامنًا مع حق الشعب الفلسطيني |
الرسم البياني المرئي
رسم البياني المرئي في الهندسة الحسابية وتخطيط حركة الروبوت،[1] الرسم البياني المرئي هو رسم بياني للمواقع المرئية، عادةً لمجموعة من النقاط والعقبات في المستوى الإقليدي. تمثل كل عقدة في الرسم البياني موقعًا نقطيًا، وتمثل كل حافة اتصالًا مرئيًا بينها. أي، إذا كان المقطع الخطي الذي يربط بين موقعين لا يمر عبر أي عائق، يتم رسم حافة بينهما في الرسم البياني. عندما تقع مجموعة المواقع في سطر، يمكن فهم ذلك على أنه سلسلة مرتبة. لذلك تم تمديد الرسوم البيانية للرؤية لتشمل مجال تحليل السلاسل الزمنية.
التطبيقات
يمكن استخدام الرسم البياني المرئي للعثور على أقصر المسارات الإقليدية بين مجموعة من العوائق متعددة الأضلاع في المستوى: المسار الأقصر بين عائقين يتبع مقاطع الخط المستقيم باستثناء رؤوس العوائق، حيث قد ينعطف، لذا فإن أقصر مسار إقليدي هو أقصر مسار في رسم بياني للرؤية يحتوي على نقاط البداية والوجهة ورؤوس العوائق كعقدة.[2] لذلك، قد تتحلل مشكلة أقصر مسار إقليدي إلى مشكلتين فرعيتين أبسط: إنشاء الرسم البياني للرؤية، وتطبيق خوارزمية المسار الأقصر مثل خوارزمية ديكسترا على الرسم البياني. للتخطيط لحركة الروبوت الذي له حجم غير مهم مقارنة بالعقبات، يمكن استخدام نهج مماثل بعد توسيع العوائق للتعويض عن حجم الروبوت.[2] ينسب Lozano-Pérez & Wesley (1979) طريقة الرسم البياني للرؤية لأقصر المسارات الإقليدية للبحث في عام 1969 بواسطة نيلز نيلسون حول تخطيط الحركة للروبوت Shakey، واستشهد أيضًا بوصف عام 1973 لهذه الطريقة من قبل علماء الرياضيات الروس MB Ignat'yev FM كولاكوف، وعموم بوكروفسكي.
يمكن أيضًا استخدام الرسوم البيانية للرؤية لحساب موضع الهوائيات الراديوية، أو كأداة مستخدمة في الهندسة المعمارية والتخطيط الحضري من خلال تحليل الرسم البياني للرؤية.
يمكن تفسير الرسم البياني المرئي لمجموعة من المواقع التي تقع في خط ما على أنه تمثيل بياني نظري لسلسلة زمنية.[3] تبني هذه الحالة الخاصة جسرًا بين السلاسل الزمنية والأنظمة الديناميكية ونظرية الرسم البياني.
التوصيف
الرسم البياني المرئي لمضلع بسيط يحتوي على رؤوس المضلع كمواقع نقطية، والجزء الخارجي من المضلع هو العائق الوحيد. يجب أن تكون الرسوم البيانية المرئي للمضلعات البسيطة رسوم بيانية هاميلتونية: تشكل حدود المضلع دورة هاميلتونية في الرسم البياني المرئي . من المعروف أنه ليست كل الرسوم البيانية المرئي تستحث مضلعًا بسيطًا. في الواقع، لا تمتلك الرسوم البيانية المرئي للمضلعات البسيطة خصائص بعض الفئات الخاصة من الرسوم البيانية.[4]
المشاكل ذات الصلة
مشكلة المعرض الفني هي مشكلة العثور على مجموعة صغيرة من النقاط بحيث تكون جميع النقاط الأخرى غير العوائق مرئية من هذه المجموعة. يمكن تفسير أشكال معينة من مشكلة المعرض الفني على أنها إيجاد مجموعة مهيمنة في رسم بياني للرؤية.
إن bitangents لنظام من المضلعات أو المنحنيات هي خطوط تلامس اثنين منهم دون أن تخترقهما في نقاط التلامس بينهما. تُشكل bitangents لمجموعة من المضلعات مجموعة فرعية من الرسم البياني للرؤية التي تحتوي على رؤوس المضلع كعقد لها والمضلعات نفسها كعقبات. قد يتم تسريع نهج الرسم البياني للرؤية لمشكلة أقصر مسار إقليدي عن طريق تشكيل رسم بياني من bitangents بدلاً من استخدام جميع حواف الرؤية، نظرًا لأن أقصر مسار إقليدي قد يدخل أو يغادر فقط حدود عقبة على طول bitangent.[5]
انظر أيضًا
المراجع
- ^ Niu، Hanlin؛ Savvaris، Al؛ Tsourdos، Antonios؛ Ji، Ze (2019). "Voronoi-Visibility Roadmap-based Path Planning Algorithm for Unmanned Surface Vehicles". Journal of Navigation. ج. 72 ع. 04: 850–874. DOI:10.1017/S0373463318001005. ISSN:0373-4633. مؤرشف من الأصل في 2021-10-31.
- ^ أ ب de Berg et al. (2000), sections 5.1 and 5.3; Lozano-Pérez & Wesley (1979).
- ^ Lacasa، Lucas؛ Luque، Bartolo؛ Ballesteros، Fernando؛ Luque، Jordi؛ Nuño، Juan Carlos (2008). "From time series to complex networks: The visibility graph". Proceedings of the National Academy of Sciences. ج. 105 ع. 13: 4972–4975. arXiv:0810.0920. DOI:10.1073/pnas.0709247105. PMC:2278201. PMID:18362361.
- ^ Ghosh، S. K. (1 مارس 1997). "On recognizing and characterizing visibility graphs of simple polygons". Discrete & Computational Geometry. ج. 17 ع. 2: 143–162. DOI:10.1007/BF02770871. ISSN:0179-5376.
- ^ de Berg et al. (2000), p. 316.
استشهاد عام
- Niu, Hanlin; Savvaris, Al; Tsourdos, Antonios; Ji, Ze (2019). "Voronoi-Visibility Roadmap-based Path Planning Algorithm for Unmanned Surface Vehicles". Journal of Navigation. 72 (04): 850–874. doi:10.1017/S0373463318001005. ISSN 0373-4633.
- de Berg et al. (2000), sections 5.1 and 5.3; Lozano-Pérez & Wesley (1979).
- Lacasa, Lucas; Luque, Bartolo; Ballesteros, Fernando; Luque, Jordi; Nuño, Juan Carlos (2008). "From time series to complex networks: The visibility graph". Proceedings of the National Academy of Sciences. 105 (13): 4972–4975. arXiv:0810.0920. doi:10.1073/pnas.0709247105. PMC 2278201. PMID 18362361.
- Ghosh, S. K. (1997-03-01). "On recognizing and characterizing visibility graphs of simple polygons". Discrete & Computational Geometry. 17 (2): 143–162. doi:10.1007/BF02770871. ISSN 0179-5376.
