الگوریتم andrew، محاسبه Convex Hull

اگر S  را یک مجموعه متنهایی از  نقاط در نظر بگیریم ، به کوچکترین چند ضلعی محدب که تمام این نقاط را در بر بگیرد ،  پوش محدب یا ((Convex Hull  می گوییم که معمولا" با CH(S)  نمایش می دهیم، مثالی که ممکن است تعریف را روشن تر سازد این است : یک صفحه چوبی را در نظر بگیرید که به طور تصادفی و نامنظم یک سری میخ تا میانه در آن کوبیده شده، اگر ما یک کش حلقه ای داشته باشیم و آن را دور این میخ ها بکشیم شکل بوجود آمده  دقیقا پوش محدب مجموعه میخ هاست.

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

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

تصویر بالا را در نظر بگیرید، ابتدا دو نقطه A و B را در نظر گرفته ایم، وقتی نقطه C وارد می شود در مرحله تست می بینیم که نقطه در سمت چپ  AB قرار دارد، بنا بر این آخرین نقطه یعنی B حذف می کنیم و C را اضافه می کنیم. اکنون ما  AC را داریم، نقطه بعدی D می باشد که سمت راست ضلع AC قرار دارد بنابر این آن را اضافه می کنیم، نقطه بعدی E  است که درسمت راستCD قرار دارد بنابر این اضافه می شود، همین پروسه برای نقطه بعدی یعنی F نیز تکرار می شود، نقطه بعد آن G می باشد ، G در سمت چپ EF قرار دارد. پس F حذف می شود همین طور این جریان برای DE نیز صادق است، E نیز حذف می گردد تا برسیم به CD  که G در سمت راست آن قرار دارد. این الگوریتم تا آخر مجموعه تکرار می شود، به طور کلی این پروسه دو بار انجام می شود، یک بار از سمت چپ به راست برای محاسبه نیمه بالای (Upper Chain) چند ضلعی و یک بار  برای نیمه پایین (Lower Chain) . در آخر شکل مورد نظر حاصل می شود، باید توجه داشت که وجود  نقاط تکراری در مجموعه باعث بروز خطا می شود.

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

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