۱۱۱۲۱پ
per
ارائه یک الگوریتم جهت تجزیه یکنواخت چندضلعی های ساده در فضای دوبعدی
/احمد تاجدینی
: دانشکده ریاضی
۶۵ص
چاپی
کارشناسی ارشد
در رشته علوم کامپیوتر
۱۳۹۲/۰۶/۲۰
دانشگاه تبریز
به افراز یک چندضلعی به مجموعه‌صای از چندضلعی‌صهای کوچکتر، تجزیه چندضلعی گفته می‌صشود .یک چندضلعی را می‌صتوان به روش‌صهای مختلفی تجزیه کرد .از میان این روش‌صها، تجزیه محدب، یکنواخت و ذوزنقه‌صای بیشترین کاربردها را در حوزه هندسه محاسباتی دارند .در برخی مواقع، لازم و یا مطلوب است تجزیه به گونه‌صای انجام شود که با حفظ قیدهای‌ص مسئله، تعداد چندضلعی‌صهای تولیدصص شده کمینه باشد .تجزیه چندضلعی‌صها در حوزه‌صهای مختلفی مانند گرافیک برداری، تشخیص الگو، تشخیص متن، محاسبه جمع‌صهای مینکوفسکی و طرح‌صریزی حرکت ربات کاربرد دارد .در این پایان‌صنامه به ارائه یک الگوریتم حریصانه جهت تجزیه یکنواخت چندضلعی‌صهای ساده و حفره‌صدار پرداخته می‌صشود .این الگوریتم بدون استفاده از نقاط کمکی، یک چندضلعی را به صورت یکنواخت تجزیه می‌صکند .هدف اصلی از ارائه این الگوریتم، دستیابی به تجزیه‌صای ص‌تقریبا کمینه در یک زمان قابل قبول است .از آنجا که تجزیه کمینه یکنواخت یک چندضلعی حفره‌صدار، در حالتی که استفاده از نقاط کمکی مجاز نیست، یک مسئلهNP -سخت است، استفاده از الگوریتم‌صهایی که منجر به تجزیه تقریبا کمینه می‌صشوند، یکی از راهکارهای عملی است .در طراحی الگوریتم پیشنهادی، دو مقوله مورد توجه قرار گرفته است .مقوله اول کمینگی تجزیه است .این الگوریتم تلاش می‌صکند عمل تجزیه را به صورت کمینه انجام دهد .با وجود اینکه تضمینی در مورد بدست آمدن جواب کمینه وجود ندارد، اما نتایج پیاده‌صسازی این الگوریتم و مقایسه عملی آن با برخی از الگوریتم‌صهای موجود، موثر بودن این راهکار را نشان می‌صدهد .دومین مقوله که در طراحی این الگوریتم مورد توجه قرار گرفته است، زمان اجرای آن است .بخشی از زمان اجرای این الگوریتم با استفاده از پارامتری به نام ص‌حداکثر عمق جستجو کنترل می-شود .هر چه مقدار این پارامتر کوچکتر باشد، احتمال یافتن تجزیه‌صای کمینه یا تقریبا کمینه کمتر می‌صشود اما زمان اجرای الگوریتم نیز به همان نسبت کاهش می‌صیابد .با انتساب مقادیر بزرگتر به این پارامتر، می‌صتوان جواب‌صهای بهتری تولید کرد اما زمان اجرای الگوریتم نیز افزایش می‌صیابد .با تنظیم مقدار این پارامتر و با توجه به کاربرد مسئله، می‌صتوان از بین زمان اجرا و کمینه‌ص بودن تجزیه یکی را ترجیح داد و یا اینکه تعادلی بین آنها بوجود آورد
Hard problem, near optimum solutions are the only available practical options for large instances of the problem. In developing this algorithm, two issues have been considered. First subject is about minimality of decomposition. However there is no guarantee about getting the minimum deal, the results of practical implementations demonstrate the effectiveness of this approach. The second issue which is considered in designing of this algorithm is the run time matter. A part of this algorithm is controlled by using a parameter which called Maximum Search Depth. As the value of this parameter is smaller, the probability of finding near minimum results will be decreased, and in the same, the run time of the algorithm will be decreased. By assigning larger values to this parameter, we can produce better answers but the algorithm's run time will be increased too. By setting this parameter according to the application of this algorithm, we can switch and select between the minimality of analysis or run time performance, or create a balance between them -Partitioning a polygon into a set of smaller polygons is called polygon decomposition. There are several methods to decompose a polygon: convex decomposition, monotone decomposition and trapezoidal decomposition, which all of them commonly used in computational geometry. In some cases, it is necessary or desirable to generate minimum number of sub polygons. In this desertation, we propose a greedy algorithm to monotone decomposition of polygons with holes. This algorithm doesn't use Steiner points. The main goal of developing this algorithm is achieving a near minimum decomposition at an acceptable time. Since minimum decomposition of a polygon with holes when Steiner points are not allowed, is a NP
تاجدینی، احمد
کریم پور، جابر، استاد راهنما
لطفی، شهریار، استاد مشاور
سیاه و سفید
نمایه‌سازی قبلی
