• صفحه اصلی
  • الگوریتم¬های ابتکاری برای شبه مثلث¬بندی مجموعه نقاط تصادفی در صفحه

اشتراک گذاری

آدرس مقاله


کد مقاله : 202005066584 بازدید : 14153 صفحه: 49 - 58

نوع مقاله: پژوهشی

الگوریتم¬های ابتکاری برای شبه مثلث¬بندی مجموعه نقاط تصادفی در صفحه

محورهای موضوعی :

منا نقده فروشها 1 * , فهیمه طاهرخانی 2 , علی نوراله 3

1 - دانشگاه آزاد اسلامی
2 - دانشگاه آزاد اسلامی
3 - دانشگاه آزاد اسلامی

تاریخ دریافت : 1399/02/17 تاریخ پذیرش : 1403/03/13 تاریخ انتشار : 1398/08/08

کلید واژه: شبه مثلث¬بندی, پوسته محدب, زنجیره محدب و مقعر, قابلیت رویت, چندضلعی ساده,

چکیده مقاله :

يافتن الگوريتم هايي براي مسائل متنوع مطرح شده در هندسه محاسباتی از جمله مسئله شبه مثلث بندي مجموعه نقاط در صفحه جزو موضوعات علمی است كه تاكنون زمينه فكري دانشمندان علم كامپيوتر را به خود اختصاص داده است. شبه مثلث بندي S که مجموعه-ای از n نقطه در صفحه است، افراز پوسته ي محدب اين مجموعه نقاط از طريق اتصال چندين يال به تعدادي شبه مثلث مي باشد كه همه نقاط را در بر مي گيرد. براي شبه مثلث بندي معيارهاي بهينگي گوناگوني بررسي شده است كه اغلب براساس وزن يال ها و گوشه ها بوده كه در آن شبه مثلث بندي مجموعه نقاط با كمترين وزن يال ها جزو مسائل باز مي باشد. به طور كلي شبه مثلث بندي كمينه به شبه مثلث بندي اطلاق مي شود كه تعداد شبه مثلث هاي ايجاد شده در آن دقيقاً n-2 شبه-مثلث و تعداد كمترين يال هاي مورد نياز در آن 2n-3 يال باشد، همچنين تمامي رئوس يك شبه مثلث بندي كمينه نوك دار مي باشند؛ به اين معني كه در بین تمام زوایای وابسته به آن رئوس، یک زاویه ی بزرگ‌تر از π وجود داشته باشد. هدف اين مقاله ارائه روش‌هایی جديد براي شبه مثلث بندي مجموعه نقاط S در صفحه است تا بتواند تفكرات الگوريتمي جديدي را در اين زمينه باز كند. اين مقاله نشان مي دهد كه ايجاد لايه هايي از پوسته محدب براي مجموعه نقاط و شبه مثلث بندي آن‌ها با دو الگوريتم خاص منجر به توليد شبه مثلث بندي كمينه خواهد شد. همچنين الگوريتمي جديد براي ايجاد يك چندضلعي ساده حلزوني شبه مثلث بندی شده ارائه مي دهد كه توليد چندضلعي هاي ساده تصادفي در دو زمينه مهم كاربردي، شامل بررسي عملكرد الگوريتم ها و ارزيابي زمان پردازنده مورد نياز الگوريتم ها، حائز اهميت مي باشد.

چکیده انگلیسی:

Finding algorithms for the diverse issues proposed in Computational Geometry including pseudo-triangulation of point set is among the scientific subjects, which has already attracted the attention of computer scientists'. A pseudo-triangle is a simple polygon in the plane with exactly three convex vertices, called corners. Three reflex chains of edges join the corners. A pseudo-triangulation for point set is a partition of the convex hull of point set into pseudo-triangles whose vertex set is point set. Many possible optimality criteria have been investigated for pseudo-triangulations which are often based on edge weights or angles in which computing a minimum weight pseudo-triangulation for a point set is among the open problems. A pseudo-triangulation is called minimum if it consists of exactly n-2 pseudo-triangles and the minimum number of edges needed for it is 2n-3. Every vertex of a minimum pseudo-triangulation is pointed. A vertex is pointed if it has an incident angle greater than π. With respect to the proposed cases, the aim of this thesis is to present new methods for pseudo-triangulation of point set in the plane, so that it can open new algorithmic reflections in this field. This research shows that the generation of convex hull layers for point set and their pseudo-triangulation, using two new algorithms which have been considered in this research, minimizes pseudo-triangulation. Also a new algorithm has been considered to generate spiral simple polygon such that the generation of random simple polygons has two main areas of application: testing the correctness and evaluating the CPU-time consumption of algorithms that operate on polygons

منابع و مأخذ:

[1]. G. Rote, F. Santos, and I. Streinu, “Pseudo-Triangulation – a Survey,” Contemporary Mathematics, 453: 343-410, American Mathematical Society, 2008.
[2]. O. Aichholzer, F. Aurenhammer, H. Krasser, and B. Speckmann, “Convexity minimizes pseudo-triangulations,” Computational Geometry 28, pp.3-10, 2004.
[3]. I. Streinu, “A combinatorial approach to planar non-colliding robot arm motion planning,” In : Proc. 41st Annu.IEEE Sympos. Foundat. Comput.Sci. (FOCS'00), , pp.443-453, 2000.
[4]. S. Gerdjikov, and A. Wolff, “Decomposing a simple polygon into pseudo-triangles and convex polygons,” Computational Geometry 41, pp.21-30, 2008.
[5]. M. Ben-Ner, A. Schulz, and A. Sheffer, “On numbers of pseudo-triangulations,” arXiv: 1210. 7126v1 [cs.CG] 26 oct 2012.
[6]. O. Aichholzer, T. Hackl, and B. Vogtenhuber, “Compatible pointed pseudo-triangulations,” 22nd Canadian Conference on Computational Geometry, 2010.
[7]. M. Pocchiola, and G. Vegter, “Topologically sweeping visibility complexes via pseudo-triangulations,” Discrete Compute.Geom. 16, pp.419-453, 1996.
[8]. M.T. Goodrich, and R. Tamassia, “Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations,” J. Algorithms 23 (1), pp.51-73, 1997.
[9]. D.G. Kirkpatrick, J. Snoeyink, and B. Speckmann, “kinetic collision detection for simple polygons,” Internat. J. Comput. Geom. Appl. 12(1-2), pp. 3-27, 2002.
[10]. B. Speckmann, and C.D. Tόth, “Allocating vertex π-guard in simple polygons via pseudo-triangulations,” Discrete Comput. Geom. 33 (2), pp.345-364, 2005.
[11]. T. Aure, and M. Held, “Heuristic for generation of random polygons,” 8th Canadian Conference On Computational Geometry (CCCG),Ottawa, Canada, pp.38-44,1996.
[12]. D. Dailey, and D. Whitfield, “Constructing random polygons,” SIGITE'08, USA, pp.119-124, 2008.
[13]. M. D. Berg, Computational Geometry: Algorithms and Applications, 3rd edition, published by Springer-Verlag, 2008.
[14]. B. Chazelle, “On the convex layers of a planar Set,” IEEE Tran. Information Theory, Vol. IT-31, No. 4, pp. 509-517, 1985.
متن کامل:


49

 

 

فصلنامه علمي- پژوهشي

فناوري اطلاعات و ارتباطات ایران

سال پنجم، شماره‌هاي 15 و 16، بهار و تابستان 1392

 صص: 49- 58

E:\E Drive\logo\iicta Logo0.JPG 

 

الگوریتم­های ابتکاری برای شبه مثلث­بندی مجموعه نقاط تصادفی در صفحه

فهیمه طاهرخانی*                منا نقده فروشها*1                علی نوراله**

* کارشناسی ارشد، دانشکده مهندسی کامپیوتر، دانشگاه آزاد اسلامی، تاکستان

** استاديار، دانشکده مهندسی برق و کامپیوتر،دانشگاه آزاد اسلامی،قزوين

 

تاريخ دريافت: 31/03/1392                        تاريخ پذيرش: 20/06/1392

 

چکيده

يافتن الگوريتم­هايي براي مسائل متنوع مطرح شده در هندسه محاسباتی از جمله مسئله شبه مثلث­بندي مجموعه نقاط در صفحه جزو موضوعات علمی است كه تاكنون زمينه فكري دانشمندان علم كامپيوتر را به خود اختصاص داده است. شبه مثلث­بندي S که مجموعه­ای از n نقطه در صفحه است، افراز پوسته­ي محدب اين مجموعه نقاط از طريق اتصال چندين يال به تعدادي شبه­مثلث مي­باشد كه همه نقاط را در بر مي­گيرد. براي شبه مثلث­بندي معيارهاي بهينگي گوناگوني بررسي شده است كه اغلب براساس وزن يال­ها و گوشه­ها بوده كه در آن شبه مثلث­بندي مجموعه نقاط با كمترين وزن يال­ها جزو مسائل باز مي­باشد. به­طور كلي شبه مثلث­بندي كمينه به شبه مثلث­بندي اطلاق مي­شود كه تعداد شبه­مثلث­هاي ايجاد شده در آن دقيقاً n-2 شبه-مثلث و تعداد كمترين يال­هاي مورد نياز در آن 2n-3 يال باشد، همچنين تمامي رئوس يك شبه مثلث­بندي كمينه نوك­دار مي­باشند؛ به اين معني كه در بین تمام زوایای وابسته به آن رئوس، یک زاویه­ی بزرگ‌تر از π وجود داشته باشد.

هدف اين مقاله ارائه روش‌هایی جديد براي شبه مثلث­بندي مجموعه نقاط S در صفحه است تا بتواند تفكرات الگوريتمي جديدي را در اين زمينه باز كند. اين مقاله نشان مي­دهد كه ايجاد لايه­هايي از پوسته محدب براي مجموعه نقاط و شبه مثلث­بندي آن‌ها با دو الگوريتم خاص منجر به توليد شبه مثلث­بندي كمينه خواهد شد. همچنين الگوريتمي جديد براي ايجاد يك چندضلعي ساده حلزوني شبه مثلث­بندی شده ارائه مي­دهد كه توليد چندضلعي­هاي ساده تصادفي در دو زمينه مهم كاربردي، شامل بررسي عملكرد الگوريتم­ها و ارزيابي زمان پردازنده مورد نياز الگوريتم­ها، حائز اهميت مي­باشد.

كليد واژگان: شبه مثلث­بندی، پوسته محدب، زنجیره محدب و مقعر، قابلیت رویت، چندضلعی ساده.

1.       مقدمه

عناوین شبه­مثلث و شبه­مثلث­بندی در سال 1993 توسط Pocchiola و Vegter مطرح شده­اند. در اوایل سال 1990 شبه­مثلث­بندی چندضلعی­ها در هندسه محاسباتی تحت نام مثلث­بندی­های ژئودزیک بیان شده است[1]. مسیر ژئودزیک کوتاهترین مسیر بین دو نقطه در یک چندضلعی بوده که هیچ یک از اضلاع چندضلعی را قطع نمی­کند. یک شبه­مثلث، یک چندضلعی ساده در صفحه دقیقاً با سه رأس محدب می­باشد که آن‌ها را گوشه می­نامند و سه زنجیره مقعر از یال­ها، گوشه­ها را به هم متصل می­کند. فرض کنید  مجموعه­ای از  نقطه در صفحه است شبه­مثلث­بندی  یک تقسیم­بندی از پوسته­ی محدب  به شبه­مثلث­هایی است که مجموعه رئوس آن  باشد[2].

در سال 2000، Streinu [3] نشان داده که بین استحکام گراف‌ها و شبه­مثلث­بندی­های کمینه ارتباط قوی وجود دارد علاوه بر این او ثابت کرد که تعداد کمینه یال‌های مورد نیاز در یک شبه­مثلث­بندی نوک­دار یال است. همچنین با استفاده از تئوری چند وجهی اویلر، تعداد شبه­مثلث­ها در یک شبه­مثلث­بندی کمینه نوک­دار  است که به هیچ ساختاری از مجموعه نقاط بجز تعداد آن بستگی ندارد[4]. در یک شبه مثلث­بندی، رأسی که در بین تمام زوایای آن یک زاویه بزرگ‌تر از  وجود داشته باشد نوک­دار نامیده می­شود. تمامی رئوس یک شبه مثلث­بندی کمینه نوک­دار می­باشند [6-5].

شبه­مثلث­بندی­ها به طور قابل ملاحظه­ای در هندسه محاسباتی مورد توجه قرار گرفته­اند که عمدتاً ناشی از کاربردشان در تئوری استحکام، برنامه­ریزی حرکت بازوی روبات‌ها، مجموعه­های قابل رویت، شعاع پرتاب، ردیابی تصادم جنبشی و نگهبانی کردن از چندضلعی­ها می­باشد[10-7]. با توجه به اینکه برخی از خواص ترکیبی و هندسی جالب شبه­مثلث­بندی­ها اخیراً کشف شده اما هنوز بسیاری از پرسش­های اصلی باز در مورد آن‌ها باقی مانده است [2].

در این مقاله به مسئله­ی شبه­مثلث­بندی مجموعه  با  نقطه تصادفی در صفحه با استفاده از پوسته­های محدب لایه­ای پرداخته و در آن دو روش جدید شبه­مثلث­بندی مطرح می­شود که منجر به تولید شبه­مثلث­بندی کمینه خواهد شد. همچنین الگوریتمی جدید برای ایجاد یک چندضلعی ساده حلزونی ارائه شده است که به طور همزمان نیز شبه­مثلث­بندی روی آن انجام می­شود. بطورکلی تولید چندضلعی­های ساده تصادفی در دو زمینه­ي مهم کاربردی حائز اهمیت است:

·       بررسی عملکرد الگوریتم­ها

·       ارزیابی زمان پردازنده مورد نیاز الگوریتم­ها.

تولید اشیاء هندسی تصادفی مورد توجه خاص محققان قرار گرفته است. به عنوان مثال Epstein تولید مثلث­بندی تصادفی یکنواخت را مورد مطالعه قرار داده است[11].

مجموعه  شامل  نقطه تصادفی   در صفحه مفروض است. هدف ایجاد یک چندضلعی ساده­ی تصادفی با توزیع یکنواخت است (اگر  چندضلعی ساده روی  وجود داشته باشد احتمال تولید همه این چندضلعی­ها با یکدیگر یکسان بوده و برابر   است) [12-11]، به گونه­ای که مجموعه رئوس چندضلعی ایجاد شده شامل همه مجموعه نقاط  باشد که به طور همزمان نیز شبه­مثلث­بندی می­شود.

دو روش جدید دیگری از شبه­مثلث­بندی را نیز ارائه می­دهیم که نسبت به سه روش دیگر ویژگی خاصی نداشته و فقط به عنوان الگوریتمی جدید برای شبه­مثلث­بندی مجموعه نقاط تصادفی در صفحه مطرح شده­اند.

ادامه مقاله به این شکل سازماندهی شده است که در بخش 2 تعاریف اولیه ارائه می­گردد. در بخش 3 نحوه­ی ایجاد پوسته­های محدب لایه­ای بیان می­شود. در بخش 4 الگوریتم­های پیشنهادی جهت شبه­مثلث­بندی مجموعه نقاط تصادفی در صفحه مطرح می­شوند. در بخش 5 تحلیل الگوریتم­های پیشنهادی و نهایتاً در بخش 6 نتیجه­گیری ارائه خواهد شد.

2.       تعاریف اولیه

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

به چندضلعی ساده­ای که تمام زوایای داخلی بین رئوس آن چندضلعی از  کمتر باشد، چندضلعی محدب می­گویند. بنا بر تعریف، مجموعه  از نقاط در صفحه محدب نامیده می­شود اگر و فقط اگر به ازای هر دو نقطه ، پاره خط واصل  کاملاً درون  واقع شود . پس می­توان نتیجه گرفت که یک چندضلعی با هر نوع فرورفتگی نمی­تواند محدب باشد.

پرکاربردترین ساختار در هندسه رباتیک پوسته محدب می­باشد. پوسته محدب مجموعه نقاط  در صفحه ، کوچک‌ترین چندضلعی محدب  است که  را محصور می­کند (شکل 2- ب). اگر  تعداد لایه­های پوسته محدب مجموعه نقاط  باشد هر لایه با  معرفی می­شود . در یک مجموعه از نقاط ، نقاطی از پوسته محدب که در آن‌ها زاویه داخلی اکیداً کوچک‌تر از  باشد را نقاط رأسی می­نامند.

سه نقطه ،  و  مفروض هستند. ماتریس  این‌گونه تعریف می­شود:

                                            (1)

در صورتی که  (دترمینان ماتریس ) باشد بین سه نقطه  رابطه پاد­ساعتگردی وجود دارد و اگر  باشد بین این سه نقطه رابطه ساعتگردی وجود دارد و  به این معنی است که سه نقطه در یک خط واقع شده­اند.

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

فرض کنید  رئوس یک چندضلعی ساده  می­باشند که این رئوس در خلاف جهت حرکت عقربه­های ساعت قرار گرفته­اند (شکل 1).  را کوتاهترین مسیر بین دو رأس  و   از رئوس  می­نامیم. مسیر  را زنجیره محدب گویند اگر از رأس  به رأس  روی مسیر آن حرکت کنیم مسیر راست­گرد باشد در غیر این صورت مسیر  را زنجیره مقعر می­نامند.

Description: Description: 02-0002.jpg 

شکل 1- زنجیره­ی محدب و مقعر

3.       ایجاد پوسته­های محدب لایه­ای

در این بخش به بررسی الگوریتم ایجاد پوسته محدب خواهیم پرداخت. جهت ایجاد پوسته محدب مختصات رئوس و ترتیب اتصال آن‌ها به یکدیگر مورد نیاز است. برای ایجاد پوسته محدب الگوریتم­های متفاوتی وجود دارد که در این مقاله از الگوریتم گراهام نسخه استفاده شده است. جهت محاسبه پوسته محدب ابتدا باید نقاط کرانی را پیدا کرد که در این الگوریتم پایین­ترین نقطه سمت راست یک نقطه کرانی می­باشد. مجموعه  با  نقطه در صفحه مفروض است. بر اساس الگوریتم اسکن گراهام نسخه ، مراحل زیر طی می­شود:

مرحله اول: پایین­ترین نقطه سمت راست را پیدا کرده و این نقطه را  می­نامیم.

مرحله دوم: مابقی نقاط بر اساس زاویه حول نقطه  مرتب می­شوند. در صورتی که دو نقطه زاویه یکسانی با  داشته باشند، یعنی در یک راستا باشند نقطه­ای در نظر گرفته می­شود که فاصله بیشتری با نقطه دارد. سپس این نقاط را از­ نام‌گذاری کرده و با اتصال این نقاط به یکدیگر یک چندضلعی ستاره­ای شکل ایجاد خواهد شد (شکل 2- الف).

مرحله سوم: پایین­ترین نقطه (رأس ) و نقطه بعد از آن (رأس ) که کمترین زاویه را نسبت به  دارد، قطعاً بر روی پوسته محدب واقع شده­اند پس این دو رأس در پشته درج می­شوند بطوریکه  در بالای پشته قرار گیرد. سپس دو رأس سر پشته به همراه رأس بعدی (رأس ، واقع شده بر روی مرز چندضلعی ستاره­ای شکل) بررسی شده و پادساعتگردی یا ساعتگردی این سه رأس متوالی تعیین می­شود. اگر زاویه پادساعتگرد بود رأس مورد نظر را در پشته درج می­کند در غیر این صورت عنصر سر پشته حذف می­شود و به همین ترتیب الگوریتم تکرار می­گردد. در نهایت تمام رئوسی که در پشته قرار دارند همان رئوس واقع شده بر روی پوسته محدب می­باشند (شکل 2- ب).

Description: Description: Untitled-nb1.tif 

(الف)

Description: Description: Untitled-nb2.tif 

(ب)

شکل 2- الف- چندضلعی ستاره­ای شکل. ب- پوسته محدب

اکنون نقاط روی این پوسته محدب را از مجموعه نقاط خارج می­کنیم و برای نقاط باقی مانده با انجام مراحل قبل، مجدداً پوسته محدب ایجاد می­شود و این کار تا زمانی ادامه پیدا می­کند که به کمتر از سه نقطه برسد به این معنی که یا یک نقطه و یا دو نقطه باقی مانده باشد. بدین ترتیب پوسته­های محدب لایه­ای ایجاد می­شوند.

4.       الگوریتم­های پیشنهادی شبه­مثلث­بندی مجموعه نقاط تصادفی در صفحه

فرض کنید تعداد لایه­ها­ی محدب ایجاد شده در بخش قبلی،  باشد  یعنی لایه­ی ام که   است و  رأس ام در لایه ام می­باشد.

 

4.1. الگوریتم پیشنهادی بیشترین نقاط قابل رویت

در اين الگوريتم هر رأس  رأسي است كه بيشترين نقاط قابل رويت از لايه­ي  را دارا باشد. هر رأس  تعدادي از رئوس لايه­ي  را رويت مي­كند. براساس اين الگوريتم رأسي كه بيشترين نقاط قابل رويت از لايه­ي  را داشته باشد؛ به عنوان يك گوشه از شبه­مثلث انتخاب شده و دو رأس قابل رويتي كه كمترين و بيشترين زاويه قطبي را نسبت به اين رأس دارند را به عنوان دو گوشه ديگر شبه­مثلث درنظر مي­گيريم و يال­هاي مربوطه به عنوان دو ضلع شبه­مثلث از رأس  به دو رأس مورد نظر رسم مي­شوند.

زنجيره­ي مقعري كه بر روي لايه­ي محدب  اين دو رأس قابل رويت را به يكديگر وصل مي­كند؛ به عنوان ضلع سوم شبه­مثلث محسوب مي­شود. اين الگوريتم را براي ديگر رئوس باقي­مانده از لايه­ي   تكرار مي­كنيم با اين شرط كه نقاط بين دو گوشه­ي انتهايي ضلع مقعرِ شبه­مثلث بدست آمده در مرحله قبل به عنوان نقاط قابل رويت مرحله بعد درنظر گرفته نشوند.

همان‌طورر كه در شكل (3- الف) مشاهده مي­شود رئوسي كه بيش از دو رأس قابل رويت دارند (رئوس قابل رويت بين دو رأسي كه كمترين و بيشترين زاويه قطبي را داشته)؛ با استفاده از خط­چين نمايان شده­اند. از بين تمامي رئوس لايه­ي  رأس  بیشترین نقاط قابل رويت را دارد (چهار نقطه قابل رويت)؛ بنابراين در اين مرحله دو رأس قابل رويت  كه كمترين و بيشترين زاويه قطبي را دارند ثابت شده (شکل 3- ب) و مجدداً الگوريتم براي ديگر رئوس تكرار مي­شود. در نهايت خروجي الگوريتم مطابق با شكل (4) خواهد بود. با اعمال اين الگوريتم بر روي تمامي لايه­ها شبه­مثلث­بندي مجموعه نقاط داده شده در صفحه ايجاد مي­شود.

4.2. الگوریتم پیشنهادی کوتاهترین طول

براساس اين الگوريتم براي تمامي رئوس  از لايه­ي  بطور جداگانه رئوس قابل رويت­شان از لايه­ي  تعيين مي­شود. سپس دو رأس قابل رويتي كه كمترين و بيشترين زاويه قطبي را نسبت به رئوس   دارند درنظر گرفته شده و مجموع فاصله اقليدوسي بين تك­تك رئوس  و دو رأس قابل رويت­شان محاسبه مي­شود (شكل 5-الف). از بين تمامي رئوس  از لايه­ي ، رأسي كه كوتاهترين طول را داشته باشد به عنوان گوشه­اي از شبه­مثلث انتخاب شده و دو رأس قابل رويتي كه كمترين و بيشترين زاويه قطبي را نسبت به اين رأس دارند را به عنوان دو گوشه ديگر شبه­مثلث درنظر مي­گيريم و يال­هاي مربوطه به عنوان دو ضلع شبه­مثلث از رأس  به دو رأس مورد نظر رسم مي­شوند.

Description: Description: morevisible1.tif 

            (الف)

Description: Description: morevisible3.tif 

              (ب)

شکل 3- الف- تعيين نقاط قابل رويت براي هر رأس از لايه  در مرحله اول،

ب- ثابت شدن دو رأس قابل رويت  و تعيين مجدد نقاط قابل رويت ديگر رئوس از لايه

Description: Description: morevisible4.tif 

شکل 4- خروجي نهايي الگوريتم بيشترين نقاط قابل رويت

براساس شكل (5-الف) مجموع فاصله اقليدوسي دو دورترين رأس قابل رويت نسبت به رأس  از لايه­ي  كمترين مقدار را داشته، بنابراين در اين مرحله رئوس قابل رويت رأس  ثابت شده (مطابق با شكل 5-ب) و مجدداً الگوريتم براي ديگر رئوس تكرار مي­شود. در نهايت خروجي الگوريتم مطابق با شكل (6) خواهد بود:

Description: Description: visible1.tif 

           (الف)

Description: Description: visible2.tif 

            (ب)

شکل 5- الف- تعيين نقاط قابل رويت براي هر رأس از لايه  در مرحله اول بر اساس فاصله اقليدوسي، ب- ثابت شدن دو رأس قابل رويت  و تعيين مجدد نقاط قابل رويت ديگر رئوس از لايه

Description: Description: morevisible4.tif 

شکل 6- خروجي نهايي الگوريتم کوتاهترین طول

در اين الگوريتم نيز همانند الگوريتم قبلي زنجيره­ي مقعري كه بر روي لايه­ي محدب  اين دو رأس قابل رويت را به يكديگر وصل مي­كند؛ به عنوان ضلع سوم شبه­مثلث محسوب مي­شود. اين الگوريتم را مجدداً براي ديگر رئوس باقي­مانده از لايه­ي   تكرار مي­كنيم با اين شرط كه نقاط بين دو گوشه­ي انتهايي ضلع مقعرِ شبه­مثلث بدست آمده در مرحله قبل به عنوان نقاط قابل رويت مرحله بعد درنظر گرفته نشوند. با اعمال اين الگوريتم بر روي تمامي لايه­ها شبه­مثلث­بندي مجموعه نقاط داده شده در صفحه ايجاد مي­شود. با توجه به اینکه اين الگوريتم براساس كوتاهترين طول عمل مي­كند جزو الگوريتم­هاي شبه­مثلث­بندي مجموعه نقاط با كمترين هزينه درنظر گرفته مي­شود.

4.3. الگوریتم­های پیشنهادی شبه­مثلث­بندی کمینه نوک­دار 

برای انجام الگوریتم ابتدا از بین تمام رئوس قابل رویت هر رأس ، دو رأس قابل رویتی که کمترین و بیشترین زاویه قطبي را نسبت به این رأس دارند به عنوان دو دورترین رأس قابل رویت منظور می­گردند. بدین ترتیب برای تمامی رئوس لایه  نسبت به لایه  ، دو رأس قابل رویت وجود خواهد داشت. به عنوان مثال همان‌طوهمان‌طور شکل (7-الف) نشان داده شده است رأس  از لايه محدب ، چهار رأس  و  را از لايه محدب  رویت می­کند که  و  به عنوان دو دورترین رأس قابل رویت انتخاب می­شوند (شکل7-ب).

Description: Description: Untitled-nb4.tif 

(الف)

Description: Description: Untitled-nb5.tif 

(ب)

شکل 7- الف- رئوس قابل رویت رأس  از لايه  . ب- دو دورترین رأس قابل رویت رأس  

همان‌طور که بیان شد، تمامی رئوس در پوسته­های محدب لایه­ای نسبت به لایه بعدی خود دو دورترین رأس قابل رویت دارند. در این بخش برای ایجاد شبه­مثلث­بندی باید یکی از این دو رأس انتخاب شوند که در ادامه دو روش جدید برای انتخاب یکی از دو رأس قابل رویت جهت شبه­مثلث­بندی مطرح می­شود.

4.3.1. الگوریتم­ انتخاب رئوس قابل رویت ساعت­گرد

در روش انتخاب رئوس قابل رویت ساعت­گرد، از بین دو دورترین رأس قابل رویت تعیین شده، رأسی انتخاب می­شود که بین رأس مورد نظر از لايه  و دو رأس قابل رویت آن رابطه ساعتگردی برقرار باشد. بنابراین رأس مورد نظر در لایه  ام را  در نظر گرفته و دو رأس قابل رویت را  (اندیس نزدیک‌ترین رأس قابل رویت) و  (اندیس دورترین رأس قابل رویت) می­نامیم. چرخش از رأس مورد نظر به دو رأس قابل رویت را بررسی کرده اگر ) ساعت­گرد باشد پاره­خط بین  و  متصل می­شود در صورتی که )ساعت­گرد باشد پاره­خط بین  و   متصل می­شود. با اتصال این خطوط در هر لایه رئوس قابل رویت ساعت­گرد تولید می­شوند (شکل8-الف)

Description: Description: Untitled-nb6.tif 

(الف)

Description: Description: Untitled-nb7.tif 

                               (ب)

شکل 8- الف- انتخاب رأس قابل رويت ساعت­گرد براي رأس  . ب- انتخاب رأس قابل رويت پادساعت­گرد براي رأس 

4.3.2. الگوریتم­ انتخاب رئوس قابل رویت پادساعت­گرد

در روش انتخاب رئوس قابل رویت پادساعت­گرد، از بین دو دورترین رأس قابل رویت تعیین شده، رأسی انتخاب می­شود که بین رأس مورد نظر از لايه  و دو رأس قابل رویت آن رابطه پادساعت­گردی برقرار باشد. بدین ترتیب که، رأس مورد نظر در لایه  ام را  درنظر گرفته و دو رأس قابل رویت را   و  می­نامیم. چرخش از رأس مورد نظر به دو رأس قابل رویت را بررسی کرده اگر  پادساعت­گرد باشد پاره­خط بین و  متصل می­شود در صورتی که ) پاد­ساعت­گرد باشد. پاره­خط بین   و  متصل می­شود. با اتصال این خطوط در هر لایه رئوس قابل رویت پادساعت­گرد تولید می­شوند (شکل8-ب).

چنانچه یکی از دو روش مطرح شده و یا ترکیبی از دو روش (بطوریکه برای هر یک از لایه­ها، تنها یکی از دو روش استفاده شود) را بر روی پوسته­های محدب لایه­ای اعمال کنیم لایه­های محدب مطابق شکل 9 شبه­مثلث­بندی می­شوند.

Description: Description: Untitled-n13.tif 

شکل 9- خروجي الگوريتم به روش پادساعت­گرد

4.4. الگوریتم­ ایجاد چندضلعی ساده حلزونی شبه­مثلث­بندی شده

الگوریتم پیشنهادی شامل دو مرحله است که با اعمال این دو مرحله بر روی لایه­های محدب، با ایجاد شبه­مثلث­ها­ی پی­درپی در نهایت چندضلعی حلزونی شکل شبه­مثلث­بندی شده حاصل می­شود.

مرحله اول الگوریتم:

گام اول-  را در نظر گرفته و روی  ( بیرونی­ترین لایه­ی محدب) یک نقطه را به عنوان نقطه شروع انتخاب نموده و آن را  می­نامیم.

گام دوم- در جهت پادساعت­گرد دو نقطه دیگر را به ترتیب انتخاب و آن‌ها را  و  نام‌گذاری می­نماییم. این سه نقطه را به عنوان رئوس شبه­مثلث درنظر گرفته و پاره­خط­های  و  را ایجاد می­کنیم.

گام سوم- در این گام جهت ایجاد پاره­خط واصل بین دو رأس  و  ، در صورت عدم وجود تقاطع با لایه­ی  ، پاره­خط مذکور رسم می­شود (شکل 10-الف)، در غیر اینصورت باید از رأس  به رأس  ، نقاطی از لایه­ی  که با این دو رأس زنجیره مقعر می­سازند انتخاب و رسم شوند. در این مرحله از الگوریتم یک شبه­مثلث ایجاد شده است (شكل10-ب).

Description: Description: Untitled-41 

(الف)

Description: Description: Untitled-n10.tif 

(ب)

شکل 10- الف- عدم تقاطع با لايه  . ب- تقاطع با لايه

گام چهارم- برای ایجاد شبه­مثلث­ بعدی باید موقعیت مکانی رئوس ،  و   با درنظر گرفتن شرایط زیر تغییر یابند:

الف) موقعیت مکانی نقطه  در صورت تقاطع پاره­خط  با لایه­ی  تغییر کرده و به نقطه مجاور رأس  روی زنجیره­ی مقعر تغییر مکان می­یابد (شكل 11-الف).

ب) رأس   به موقعیت مکانی رأس   فعلی منتقل شده و نقطه مجاور آن در جهت پادساعت­گرد روی لایه­ی   را رأس   نامیده و پاره­خط  را ایجاد می­کنیم (شکل 11-الف و 11-ب).

 

Description: Description: 02-07.jpg 

(الف)

Description: Description: 02-04.jpg 

(ب)

شکل 11- الف- تغيير موقعيت مكاني رئوس مثلث در صورت وجود تقاطع با لايه . ب- تغيير موقعيت مكاني رئوس مثلث در صورت عدم تقاطع با لايه

مرحله دوم الگوریتم:

با ملاقات آخرین نقطه روی لایه­ی ، در این مرحله از بین نقاط باقی­مانده روی لایه­ی  که در ایجاد زنجیره مقعر در مرحله اول الگوریتم استفاده نشده­اند، دورترین نقطه قابل رویت نسبت به آخرین نقطه روی لایه­ی  یعنی رأس  را پیدا کرده آن را  می­نامیم و پاره­خط واصل بین آن دو را رسم می­کنیم. همچنین از رأس   به نقطه قابل رویت روی لایه­ی  حرکت کرده و به ترتیب پاره­خط­های واصل بین نقاط موجود در این مسیر را رسم می­نماییم.

بعد از اتمام این دو مرحله، با در نظر گرفتن  وارد لایه­ی بعدی شده و نقطه مجاور به دورترین نقطه قابل رویت (در مرحله­ی دوم از الگوریتم) در جهت ساعت­گرد را به عنوان نقطه شروع این لایه درنظر می­گیریم و از گام دوم مرحله اول، الگوریتم را با نقاط باقی­مانده (بجز دورترین نقطه قابل رویت) در این لایه، ادامه می­دهیم و مراحل را تا  تکرار می­کنیم (شکل 12-الف). بدین ترتیب با تکرار مراحل الگوریتم پیشنهادی تا   چندضلعی ساده حلزونی شبه­مثلث­بندی شده ایجاد می­گردد (شکل 12-ب).

Description: Description: 02-122.jpg 

(الف)

Description: Description: 999.jpg 

(ب)

شکل 12- الف- ورود به لايه . ب- خروجي الگوريتم ايجاد چندضلعي ساده حلزوني شبه­مثلث­بندي شده

قضیه1. الگوریتم ابتکاری ارائه شده دو برابر تعداد نقاط موجود بر روی بیرونی­ترین لایه­ی محدب، چندضلعی ساده تصادفی تولید می­کند.

اثبات.

از آنجایی که نقطه شروع الگوریتم هر یک از نقاط چندضلعی محدب بیرونی­ترین لایه می­تواند باشد و جهت اجرا نیز ساعتگرد یا پادساعتگرد انتخاب گردد، لذا دو برابر تعداد نقاط موجود بر روی بیرونی­ترین لایه­ی محدب، چندضلعی ساده تصادفی تولید خواهد شد.

شبه کد مربوط به الگوریتم ایجاد چندضلعی ساده حلزونی شبه­مثلث­بندی شده به صورت زیر می­باشد:

img0 

اثبات درستی الگوریتم

در گام اول الگوريتم چون تعداد لايه­هاي محدب براي هر مجموعه از نقاط،  است ( ) لذا وجود نقطه  بديهي است.

لم1. در گام سوم الگوريتم بر روي لايه­ي ، مثلث ∆ مفروض است اگر رأس   از طريق رأس   قابل رويت نباشد نقاطي جهت ايجاد زنجيره مقعر از لايه­ي  وجود دارد.

اثبات. اگر رأس  از رأس  قابل رويت نباشد به اين معني است كه نقاطي از لايه­ي  در ∆ واقع شده است. از بين اين نقاط نقطه­اي كه داراي كمترين زاويه قطبي نسبت به رأس  است را پيدا كرده و آن را  مي­ناميم. بديهي است كه  چپ­گرد است و لذا بر روي زنجيره مقعر قرار خواهد گرفت از اين رو وجود زنجيره مقعر قابل اثبات خواهد بود.

با شروع الگوريتم بر روي لايه­ي  و وقوع اولين تقاطع با لايه­ي  و ايجاد زنجيره مقعر، اولين نقطه در جهت پادساعت­گرد را  و آخرين نقطه را  (با ملاقات آخرين نقطه روي لايه­ي  در مرحله دوم الگوريتم) مي­ناميم. اگر  از طريق لايه­ي  به  متصل باشد به اين معني است كه نقاط لايه­ي  به پايان رسيده­اند (تمامي نقاط در ايجاد زنجيره مقعر استفاده شده­اند) و لذا الگوريتم را بايد از لايه­ي  ادامه دهيم در غیر اينصورت از بين نقاط باقي­مانده بر روي لايه­ي  نقطه با كمترين زاويه قطبي نسبت به آخرين نقطه بر روي لايه­ي  را پيدا كرده و آن را v مي­ناميم. بديهي است كه v از اين نقطه (آخرين نقطه بر روي لايه­ي ) قابل رويت مي­باشد.

 

5.       تحلیل الگوریتم­های پیشنهادی شبه­مثلث­بندی مجموعه نقاط

ایجاد گراف قابل دید دارای مرتبه زمانی  بوده[13] و مرتبه زمانی ایجاد پوسته­های محدب لایه­ای  مي­باشد[14]. در بخش 4 با اجرای هر كدام از الگوریتم­هاي پیشنهادی جهت ایجاد پاره­خط واصل بین دو نقطه، موضوع قابل رویت بودن دو نقطه باید بررسی شود که با ایجاد گراف قابل دید مرتبه زمانی آن  است. با توجه به مسطح بودن گراف شبه­مثلث­بندی برای ایجاد کل شبه­مثلث­ها حداکثر  زمان صرف می­شود، لذا در مجموع مرتبه زمانی این الگوریتم­ها  می­باشد.

6.       نتیجه­گیری

در این مقاله روش‌های جدیدی جهت شبه­مثلث­بندی مجموعه نقاط  در صفحه مطرح شد. روند کار به گونه­ای بود که ابتدا برای مجموعه نقاط  در صفحه پوسته­های محدب لایه­ای ایجاد شده و سپس با اعمال یکی از روش‌ها و یا در مواردی ترکیبی از آن آن‌ها بر روی لایه­ها، شبه­مثلث­بندی انجام گردید. بررسی­ها نشان داد که دو روش از شبه­مثلث­بندیهای انجام شده کمینه بوده، به این معنی که تعداد شبه مثلث­های تولید شده  شبه مثلث و تعداد یال‌های مورد نیاز در آن کمترین مقدار ممکن یعنی  می­باشد. همچنین در این مقاله الگوریتمی جدید برای ایجاد یک چندضلعی ساده حلزونی شکل شبه­مثلث­بندی شده از مجموعه نقاط تصادفی  در صفحه ارائه شد. که با استفاده از این الگوریتم پیشنهادی به ترتیب از بیرونی­ترین لایه محدب تا درونی­ترین لایه با ایجاد شبه­مثلث­های پی­درپی، چندضلعی حلزونی شبه­مثلث­بندی شده ایجاد گردید. ایجاد چندضلعی­های ساده از روی مجموعه نقاط تصادفی دارای کاربردهایی نظیر بررسی الگوریتم­های ابتکاری در مسائلی چون موزه هنری می­باشند و لذا الگوریتم­هایی برای تولید چندضلعی بسیار در این کار مؤثرند.

مراجع

[1]. G. Rote, F. Santos, and I. Streinu, “Pseudo-Triangulation – a Survey,” Contemporary Mathematics, 453: 343-410, American Mathematical Society, 2008.

[2]. O. Aichholzer, F. Aurenhammer, H. Krasser, and B. Speckmann, “Convexity minimizes pseudo-triangulations,” Computational Geometry 28, pp.3-10, 2004.

[3]. I. Streinu, “A combinatorial approach to planar non-colliding robot arm motion planning,” In : Proc. 41st  Annu.IEEE Sympos. Foundat. Comput.Sci. (FOCS'00), , pp.443-453, 2000.

[4]. S. Gerdjikov, and A. Wolff, “Decomposing a simple polygon into pseudo-triangles and convex polygons,” Computational Geometry 41, pp.21-30, 2008.

[5]. M. Ben-Ner, A. Schulz, and A. Sheffer, “On numbers of pseudo-triangulations,” arXiv: 1210. 7126v1 [cs.CG] 26 oct 2012.

[6]. O. Aichholzer, T. Hackl, and B. Vogtenhuber, “Compatible pointed pseudo-triangulations,” 22nd Canadian Conference on Computational Geometry, 2010.

[7]. M. Pocchiola, and G. Vegter, “Topologically sweeping visibility complexes via pseudo-triangulations,” Discrete Compute.Geom. 16, pp.419-453, 1996.

[8]. M.T. Goodrich, and R. Tamassia, “Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations,” J. Algorithms 23 (1), pp.51-73, 1997.

[9]. D.G. Kirkpatrick, J. Snoeyink, and B. Speckmann, “kinetic collision detection for simple polygons,” Internat. J. Comput. Geom. Appl. 12(1-2), pp. 3-27, 2002.

[10]. B. Speckmann, and C.D. Tόth, “Allocating vertex π-guard in simple polygons via pseudo-triangulations,” Discrete Comput. Geom. 33 (2), pp.345-364, 2005.

[11]. T. Aure, and M. Held, “Heuristic for generation of random polygons,” 8th Canadian Conference On Computational Geometry (CCCG),Ottawa, Canada, pp.38-44,1996.

[12]. D. Dailey, and D. Whitfield, “Constructing random polygons,” SIGITE'08, USA, pp.119-124, 2008.

[13]. M. D. Berg, Computational Geometry: Algorithms and Applications, 3rd edition, published by Springer-Verlag, 2008.

[14]. B. Chazelle, “On the convex layers of a planar Set,” IEEE Tran. Information Theory, Vol. IT-31, No. 4, pp. 509-517, 1985.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

49

 


حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1403-1396

صفحه اصلی| عضویت/ ورود| درباره رایمگ| تماس با ما|
[English] [العربية] [en] [ar]