Manuscript ID : 202005066584 Visit : 14464 Page: 49 - 58

Article Type: Original Research

Heuristic algorithms for pseudo-triangulation random point set in the plane

Subject Areas :

mona naghdeforoshhs ^{1
*} , fahime taherkhani ² , ali norollah ³

1 -
2 -
3 -

Received: 2020-05-06 Accepted : 2024-06-02 Published : 2019-10-30

Keywords: Pseudo-Triangulation, Convex hull, Convex and concave chain, Visibility, Simple polygon,

Abstract :

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

References:

[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.

Full-Text:

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

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

سال پنجم، شماره‌هاي 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). را کوتاهترین مسیر بین دو رأس و از رئوس مینامیم. مسیر را زنجیره محدب گویند اگر از رأس به رأس روی مسیر آن حرکت کنیم مسیر راستگرد باشد در غیر این صورت مسیر را زنجیره مقعر مینامند.

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

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

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

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

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

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

(الف)

(ب)

شکل 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. الگوریتم ابتکاری ارائه شده دو برابر تعداد نقاط موجود بر روی بیرونیترین لایهی محدب، چندضلعی ساده تصادفی تولید میکند.

اثبات.

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

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

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

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

لم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.

Share To

Article Url

Heuristic algorithms for pseudo-triangulation random point set in the plane