غلاف محدب: تفاوت میان نسخه‌ها

پوش محدب {{انگلیسی|convex hull}} یک مجموعه از نقاط صفحه، کوچکترین [[چند ضلعی محدب]]ی است که تمامی نقاط، درون آن یا بر روی محیط آن قرار داشته باشند.

 

== الگوریتم پیمایش گراهام ==

مجموعه نقاط ورودی را Q در نظر بگیرید.الگوریتم پیمایش گراهام{{انگلیسی|Grham's Scan}} با در نظر گرفتن یک پشته از نقاط کاندید، پوش محدب را پیدا می‌کند(ما این پشته راs می نامیم).در این روش همه نقاط یک بار در پشته اضافه می‌شوند و نقاطی که بر روی محیط پوش محدب قرار ندارند در نهایت از پشته حذف می‌شوند ودر نتیجه در پایان الگوریتم مجموعه نقاطی که در s قرار دارند همان رئوس پوش محدب است.

 

شبه کد زیر الگوریتم پیمایش گراهام را پیاده سازی می‌کند.

== پیچیدگی الگوریتم پیمایش گراهام ==

در این جا نشان می دهیم که زمان اجرای الگوریتم گراهام از <math>O(nlog n)\,\!</math> است. خط 1 الگوریتم زمان <math>O(n)\,\!</math> را مصرف می‌کند چون یک جستجوی ساده بر روی نقاط است. خط 2 الگوریتم را در صورتی که با الگوریتم [[مرتب‌سازی ادغامی]] پیاده سازی کنیم در زمان <math>O(nlog n)\,\!</math> اجرا شود. در قسمت‌های بعد نیز ما فقط با پشته s کار می کنیم وچون هر نقطه دقیقا یک بار به پشته اضافه می‌شد و حداکثر یک بار از آن حذف می‌شود پس بقیه کد نیز در زمان <math>O(n)\,\!</math> اجرا می‌شود پس در کل الگوریتم پیمایش گراهام در زمان <math>O(nlog n)\,\!</math> اجرا می‌شود.

 

== الگوریتمJarvis's march ==

این الگوریتم به این صورت عمل می‌کند که ابتدا نقاط را بر اساس مختص Yشان مرتب کرده ودر صورتی که Y برابری داشته باشد بر اساس X آنها را مرتب می‌کند و در آرایهٔ P نگه می‌دارد. در این صورت نقطه <math>p[0]</math> حتماً یکی از نقاط پوش محدب است. پس آن را در یک آرایه به نام C وارد می‌کند. حال از بین سایر نقاط نقطه‌ای را پیدا می‌کند که کمترین زاویهٔ قطبی را وابسته به نقطه <math>p[0]</math> دارد و آن را نیز در آرایهٔ C اضافه می‌کند و همین فرآیند را برای نقطه <math>p[1]</math> تکرار می‌کند تا این که به آخرین نقطه آرایهٔ p برسد. به مجموعه کنونی که در C قرار دارد زنجیره راست {{انگلیسی|right chain}} می‌گوییم.

برای ساختن زنجیره چپ {{انگلیسی|left chain}} از <math>p[n]</math> (آخرین نقطهٔ مجموعه P)شروع کردهودوباره نقطه‌ای را انتخاب می‌کنیم که نسبت به <math>p[n]</math> کمترین زاویه قطبی را دارد اما این بار نسبت به قسمت منفی محور X و آن نقطه را نیز به مجموعهٔ C اضافه می‌کنیم و این کار را برای این نقطه تکرار می‌کنیم تا به نقطه <math>p[0]</math> اولیه بر گردیم. در این صورت مجموعه C ساخته شده همان پوش محدب مورد نظر است.

این الگوریتم از <math>O(nh)\,\!</math>است که در آن n تعداد نقاط است و h تعداد رئوس پوش محدب است. زیرا به ازای هر کدام از رئوس پوش محدب یک بار هر یک از نقاط را با عملی از <math>O(1)\,\!</math> چک می‌کنیم.

 

{{چپ‌چین}}

* {{یادکرد|فصل= |کتاب=[[مقدمه‌ای بر الگوریتم‌ها]]|ناشر= |چاپ= |شهر= |کوشش= |ویرایش= |سال= |شابک= |نویسنده= [[UDI MANBER]], [[دانشگاه آریزونا]]|نویسندگان سایر بخش‌ها=|ترجمه=|صفحه= |زبان=en |مقاله= |ژورنال= |نشریه= |تاریخ= |دوره= |شماره= |شاپا=}}

* {{یادکرد|فصل= |کتاب=[[مقدمه‌ای بر الگوریتم‌ها]]|ناشر= MIT Press and McGraw-Hill|چاپ= |شهر= |کوشش= |ویرایش= second |سال= 2001 |شابک=ISBN 0-262-53196-8 |نویسنده= [[توماس اچ کورمن]], [[Charles E. Leiserson]], [[Ronald L. Rivest]] and [[کلیفورد استین]]|نویسندگان سایر بخش‌ها=|ترجمه=|صفحه= |زبان=en |مقاله= |ژورنال= |نشریه= |تاریخ= |دوره= |شماره= |شاپا=}}

{{پایان چپ‌چین}}

 

[[رده:هندسه محدب]]