نمودار قطبی نقاط با قطب متحرک
محورهای موضوعی : عمومىبهرام صادقی بی غم 1 , فاطمه ربانی 2
1 - دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه تحصیلات تکمیلی علوم پایه زنجان
2 - دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه تحصیلات تکمیلی علوم پایه زنجان
کلید واژه: نمودار قطبی, نمودار ورونوی, مخابرات, آنتن, زاویه قطبی, رویت پذیری,
چکیده مقاله :
مسئله نمودار قطبی یکی از تعمیم‌های نمودار ورونوی است که در آن به جای متر اقلیدسی از مقدار زاویه برای محاسبه فاصله استفاده می شود.. این مسئله کاربردهای زیادی در پردازش تصویر، مخابرات و مباحث مربوط به آنتن، رؤیت‌پذیری و مسیریابی ربات دارد. در سالهای اخیر دو نوع نمودار قطبی مطرح شده و برای انواع سایتها الگوریتم‌های مناسبی ارائه شده است. همچنین روی همین مسائل با داده‌های جنبشی و حالات پویا الگوریتم‌هایی ارائه شده است. در این مقاله قطب به عنوان ناظرمتحرک در نظر گرفته شده و الگوریتمی ارائه میشود که مسئله بازسازی نمودار قطبی با قطب نزدیک را به صورت کارا و در زمان خطی حل میکند. در این حالت زمان پیش‌پردازش الگوریتم〖O(n^4 log〗_2〖n)〗 و زمان باز رسم نمودار در هر حرکت متوالی قطب برابر با O(logn+k) است که در آنk تعداد سایتهای درون ناحیهT است که احتمال تغییر در آنها وجود دارد.
Polar diagram is a generalization of Voronoi diagram in which the angle is used as the metric. This Problem has many applications in visibility, image Processing, telecommunication, antenna, and Path Planning Problems. In recent years two kinds of Polar diagram have been proposed and appropriate algorithm have been Presented for some types of sites. Also, some algorithms has presented for kinetic data and dynamic states. In this Paper, it is assumed that the Pole is moving and an algorithm is presented that updates near Pole Polar diagram of sites with moving pole efficiently and in a sub linear time. In this approach, the Preprocessing time is 〖O(n^4 log〗_2〖n)〗 and updating time for diagram with each successive movement is 〖 O(log〗_2〖n +k)〗 that k is the number of sites in region T which its site’s regions may be changed
1.Grima, CI, Márquez, A, and Ortega, L. A locus approach to angle Problems in computational geometry. In Proc. of 14th European Workshop in Computational Geometry, Barcelona, 1998.
2.Grima, CI, Márquez, A, and Ortega, L. Polar diagrams of geometric objects. In 15th European Workshop in Computational Geometry, 1999.
3.Grima, C, Márquez, A, and Ortega, L. Motion Planning and visibility Problems using Polar diagrams. In Annual conference of the European association for computer graphics, EG. Citeseer, 2003.
4.Bigham, B Sadeghi and Mohades, Ali. The dual of Polar diagrams and its extraction. In International Conference of Computational Methods in Sciences and Engineering ICCMSE, vol. 7, PP. 451–454, 2006.
5.Ortega, Lidia M, Rueda, Antonio J, and Feito, Francisco R. A solution to the Path Planning Problem using angle Pre-Processing. Robotics and Autonomous Systems, 58(1):27–36, 2010.
6.Ortega, Lidia and Robles-Ortega, M Dolores. Visibility resolution with Polar diagrams. APPl. Math, 7(5):1651–1669, 2013.
7.Bigham, B Sadeghi and Mohades, Ali. Polar diagram with respect to a near Pole. In 23rd European Workshop on Computational Geometry EWCG07, Austria, PP. 206–209. Citeseer, 2007.
8.Bigham, Bahram Sadeghi, Eskandari, Marzieh, and Tahmasbi, Maryam. Near-Pole Polar diagram of objects and duality. Journal of Computational Science, 3(3):127–131, 2012.
9.Sadeghi Bigham, Bahram, Mohades, Ali, and Ortega, Lidia. Dynamic Polar diagram. Information Processing Letters, 109(2):142–146, 2008.
10.Ehsanfar, Ebrahim, Bigham, Bahram Sadeghi, and Madadi, Najmeh. An optimal solution for dynamic Polar diagram. in CCCG, PP. 51–54, 2010.e
11.Beygi, Mojtaba Nouri and Ghodsi, Mohammad. Polar diagram of moving objects. In 20th Annual Canadian Conference on Computational Geometry, P. 51. Citeseer, 2008.
12.بزاز، زینب، کاربرد دیاگرام ورونوی حساس به زاویه در مسایل بینایی، پایان نامه کارشناسی ارشد، دانشگاه صنعتی امیرکبیر، 1389
13.Aronov, Boris, Edelsbrunner, Herbert, Guibas, Leonidas J., and Sharir, Micha. The number of edges of many faces in a line segment arrangement. Combinatorica, 12(3):261–274, 1992.
14.De Berg, Mark, Cheong, Otfried, van Kreveld, Marc, and Overmars, Mark. Computational geometry. SPringer Berlin Heidelberg, Berlin, third ed., 2008.
15.KirkPatrick, David. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28–35, 1983.
16.Chazelle, Bernard and Dobkin, David P. Intersection of convex objects in two and three dimensions. Journal of the ACM (JACM), 34(1):1–27, 1987.
17.ربانی، فاطمه، دیاگرام قطبی با قطب متحرک. پایان نامه کارشناسی ارشد، دانشگاه تحصیلات تکمیلی علوم پایه زنجان، 1391
18.Sun, Qinbo, et al. "Tacking Control of an Autonomous Sailboat Based on Force Polar Diagram." 2018 13th World Congress on Intelligent Control and Automation (WCICA). IEEE, 2018.
19.The magnetotelluric (MT) method is commonly used to estimate the subsurface conductivity structure.
20.Pranata, Erick, Selvi Misnia Irawati, and Sintia Windhi Niasari. "Magnetotelluric Data Analysis using Swift Skew, Bahr Skew, Polar Diagram, and Phase Tensor: a Case Study in Yellowstone, US."
نمودار قطبی نقاط با قطب متحرک
فصلنامه علمي- پژوهشي فناوري اطلاعات و ارتباطات ایران | سال یازدهم، شماره‌هاي41 و 42، پاییز و زمستان 1398 صص: 97-104 |
|
نمودار قطبی نقاط با قطب متحرک
*بهرام صادقی بی غم ** فاطمه ربانی
*دانشیار، دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه تحصیلات تکمیلی علوم پایه زنجان
**کارشناسی ارشد، دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه تحصیلات تکمیلی علوم پایه زنجان
تاریخ دریافت: 10/12/1398 تاریخ پذیرش: 22/06/1399
چكيده
مسئله نمودار قطبی یکی از تعمیم‌های نمودار ورونوی است که در آن به جای متر اقلیدسی از مقدار زاویه برای محاسبه فاصله استفاده می شود.. این مسئله کاربردهای زیادی در پردازش تصویر، مخابرات و مباحث مربوط به آنتن، رؤیت‌پذیری و مسیریابی ربات دارد. در سالهای اخیر دو نوع نمودار قطبی مطرح شده و برای انواع سایتها الگوریتم‌های مناسبی ارائه شده است. همچنین روی همین مسائل با داده‌های جنبشی و حالات پویا الگوریتم‌هایی ارائه شده است. در این مقاله قطب به عنوان ناظرمتحرک در نظر گرفته شده و الگوریتمی ارائه میشود که مسئله بازسازی نمودار قطبی با قطب نزدیک را به صورت کارا و در زمان خطی حل میکند. در این حالت زمان پیش‌پردازش الگوریتم
و زمان باز رسم نمودار در هر حرکت متوالی قطب برابر با 
است که در آن
تعداد سایتهای درون ناحیه
است که احتمال تغییر در آنها وجود دارد.
كلمات كليدی: نمودار قطبی، نمودار ورونوی، مخابرات، آنتن، زاویه قطبی، رویت پذیری
1- مقدمه
یکی از مسائل مهم و پر کاربرد در هندسه محاسباتی مسئله نمودار ورونوی است که ازنظر نوع سایتها، متر، محدودیت‌های صفحه و موانع دارای انواع تعمیم هاست. یکی ازاین تعمیم‌ها حالتی است که معیار فاصله بین نقاط و سایتها زاویه است. این نوع نمودارکاربردهای مهمی در بینایی ماشین و مخابرات دارد. این مسئله در دو نوع کلی نمودار قطبی با قطب دور (کلاسیک) و قطب نزدیک معرفی شده است که در هر مورد به تعمیم‌هایی از آن نیز پرداخته شده است. همچنین به حالاتی از مسئله که سایتها در حالت حذف یا اضافه شدن باشند نیز توجه شده است. این مقاله حالتی از مسئله نمودار قطبی با قطب نزدیک را بررسی میکند که سایتها به صورت نقاطی ثابت در صفحه باشند و قطب بتواند در خارج از پوسته محدب سایتها جابجا شود. هدف اصلی، ارائه روشی سریع و کارا پس از یک پیش پردازش برای بازسازی نمودار است. هنگامی که قطب به عنوان یک ناظر درنظر گرفته شود، این مسئله کاربردهای زیادی در پردازش تصاویر خواهد داشت.
نویسنده عهدهدار مکاتبات : بهرام صادقیبیغم B_sadeghi_b@iasbs.ac.ir
|
همچنین فرض کنید هر نقطه ی دلخواه از صفحه دارای رنگی است که از ترکیب رنگ سایت والد و قطب حاصل می شود. محاسبه ی رنگ هر پیکسل از صفحه با الگوریتم های رایج قبلی زمانی طولانی لازم دارد و با روش جدید و البته پس از یک بار پیش پردازش سرعت انجام اینکار زیر خطی است.
نمودار قطبی یکی از نمودارهای افراز صفحه مانند نمودار ورونوی است با این تفاوت که معیار اصلی در نمودار قطبی زاویه قطبی می باشد. زاویه قطبی سایت
نسبت به قطب
برابر است با زاویه ای که توسط نیم خط افقی رسم شده از به سمت راست (جهت مثبت محور 
ها) و پاره خط 
تولید می شود. فرض می شود قطب در سمت چپ تمام سایتها قرار دارد و بنابراین مقدار زاویه قطبی در بازه ی 
قرار دارد.
ناحیه قطبی یک سایت دلخواه که با 
نشان می دهیم، برابر با مکان هندسی تمام نقاطی از صفحه است که زاویه قطبی یا آنها تا سایت کوچکتراز زاویه قطبی آن نقاط تا هر سایت دیگری باشد. زاویه قطبی نقطه ی 
نسبت به سایت یعنی 
زاویه ای است که بین نیمخط افقی با مبدا سایت و به سمت منفی محور و خط واصل بین سایت و نقطه ی است. ناحیه قطبی را میتوان به صورت فرمول۱ نشان داد:
(۱)
تاکنون 
دو نوع نمودار قطبی تعریف شده است. نمودار قطبی با قطب در بینهایت و نمودار قطبی باقطب نزدیک. در نمودار قطبی با قطب در بینهایت، قطب در دور از سایتها و در بینهایت قرار دارد. شکل ۱ نمونه‌ای از نمودار قطبی با قطب در بینهایت را نشان می‌دهد.
در نمودار قطبی با قطب نزدیک، قطب در نزدیک سایتها قرار دارد. فرض می‌کنیم که قطب در سمت چپ همه سایتها قرار داشته باشد. در واقع ورودی این مسئله مجموعه‌ا‌ی از سایتها هستند که این مجموعه را با حرف
نشان می‌دهیم و یک نقطه‌ی به عنوان قطب. خروجی مسئله یک افراز از صفحه میباشد که با استفاده از آن برای هر نقطه دلخواه در صفحه میتوان گفت که متعلق به ناحیه قطبی کدام سایت است. شکل1(b) نمونه‌ای از نمودار قطبی با قطب نزدیک میباشد. نمودار قطبی اولین بار در سال ۱۹۹۸ در چهاردهمین کارگاه اروپایی هندسه محاسباتی در اسپانیا توسط گریما 1و همکارانش معرفی شد [۱]. آنها ضمن معرفی نمودار قطبی به ارائه الگوریتم رسم آن نیز پرداختند. همچنین نمودار قطبی را در مورد پاره‌خط‌ها، چندضلعی‌ها و دوایر گسترش دادند و به کاربردهای این نمودار درمسائل پوسته محدب2 و رؤیت‌پذیری3 اشاره کردند [۲].
در سال 2003، ارتگا4 و همکارانش در مورد کاربرد نمودار قطبی در مسائل برنامه‌ریزی حرکت5 و مسائل رؤیت‌پذیری بحث نمودند [۳] و الگوریتم‌هایی را برای حل این مسائل ارائه کردند که از یک پیش‌پردازش زاویه‌ای بر پایه نمودار قطبی استفاده می‌کرد.
دوگان نمودار قطبی توسط صادقی و همکارانش معرفی و الگوریتمی برای محاسبه آن ارائه شد [۴]. این الگوریتم دوگان را در زمان بهینه 
محاسبه میکند. در سال ۲۰۱۰ ارتگا و همکارانش این مسئله را به طور گسترده مورد بررسی قرار دادند وتحت عنوان یک راه حل برای مسئله مسیریابی با استفاده از نمودار قطبی به عنوان پیش‌پردازش، مقاله‌ای به چاپ رساندند [۵]. آنها در این مقاله الگوریتمی برای مسئله مسیریابی ارائه کردند که با استفاده از نمودار قطبی صفحه را به چندین ناحیه تقسیم بندی میکند. همچنین در سال ۲۰۱۳ ارتگا و همکارانش به کاربرد نمودار قطبی در مسائل رؤیت پذیری پرداختند [۶]. در الگوریتم بیان شده ابتدا چهار نمودار قطبی به عنوان پیش پردازش محاسبه و سپس در گام‌های الگوریتم از این چهار نمودار با توجه به جهت مشخص، استفاده شده‌است. در سال ۲۰۰۷ نوع دیگری از نمودار قطبی توسط صادقی و همکارانش معرفی شد که درآن قطب در نزدیک سایتها قرار داشت [۷]. به این نوع از نمودار قطبی، نمودار قطبی با قطب نزدیک گفته میشود. این گروه علاوه بر معرفی نمودار قطبی با قطب نزدیک، در مورد دوگان این نوع نمودار قطبی نیز بحث نمودند. همچنین نمودار قطبی با قطب نزدیک را برای پاره‌خط‌ها و چندضلعی‌ها و دوایر گسترش دادند و به کاربردهای این نمودار در مسائل رؤیت پذیری و مسیریابی اشاره کردند [۸]. بعد از آن و در سال 2008، صادقی و همکارانش نمودار قطبی پویا را معرفی نمودند [۹]. در نمودارقطبی پویا دو موضوع مورد بررسی قرار گرفته است. یکی حالتی است که در نمودار قطبی یک سایت اضافه و یا حذف شود. نمودار قطبی موجود با توجه به این که کدام اتفاق رخداده است، تغییر میکند و به روز می‌گردد. این تغییر از نمودار به گونه‌ای است که بخش زیادی از نمودار دست نخورده باقی می‌ماند و این موجب افزایش سرعت به روز رسانی نمودار میشود. این الگوریتم تغییرات را در زمان قابل قبولی در نمودار قطبی اعمال می‌کرد. سپس در سال ۲۰۱۰ احسانفر و همکارانش الگوریتمی ارائه کردند که اضافه یا حذف شدن سایتها در نمودار قطبی پویا به صورت بهینه انجام گردد[10]. نوع دیگری از نمودار قطبی پویا با عنوان نمودار قطبی اشیاء متحرک نیز توسط نوری بیگی و همکارش در سال ۲۰۰۸ مورد بررسی قرار گرفت [۱۱]. در این نوع از نمودار قطبی پویا سایتها در صفحه به صورت پیوسته حرکت می‌کنند و هدف بروز رسانی بهینه نمودار قطبی مجموعه سایتها میباشد. آنها از ساختمان داده جنبشی6 برای حل این مسئله استفاده کرده‌اند. همچنین الگوریتم بیان شده نمودار قطبی را در زمان بهینه بروز رسانی می‌نماید. در سال ۲۰۰۹ بزاز در پایان‌نامه کارشناسی ارشد خود در مورد نوع دیگری از نمودار قطبی بحث کرد که به کاربردهایی از آن اشاره دارد [12]. نتایج بدست آمده در پایان‌نامه‌ی بزاز و سپس در پایان نامه ی فاطمه ربانی[17] در خصوص نقاط در این پژوهش بررسی و به کار گرفته شده است در این نوع نمودار قطبی، قطب میتواند به طور پیوسته در صفحه و خارج ازپوسته محدب سایتها حرکت کند و نمودار قطبی با توجه به این حرکت به روز شود. در این پژوهش با استفاده از ساختمان دادهDCEL 7، مسئله با زمان پیش‌پردازش و نیز با بروز کردن نمودار در زمان 
حل شده است. در ادامه به معرفی نمودار قطبی با قطب نزدیک پرداخته میشود و سپس حالتی را مورد بررسی قرار خواهیم داد که قطب میتواند به طور پیوسته و البته خارج از پوسته محدب سایتها در صفحه حرکت کند. در بخش آخر نیز تحلیل نهایی از الگوریتم ارائه شده برای به روز رسانی نمودار قطبی با قطب نزدیک متحرک، صورت می‌گیرد.
2- نمودار قطبی با قطب نزدیک متحرک برای نقاط
فرض کنید مجموعه شامل
نقطه به عنوان سایت در صفحه و قطب در نزدیک سایتها داده شده است. همچنین فرض کنید که نمودار قطبی مجموعه و قطب با نام
با استفاده از الگوریتم افزایشی بیان شده در [۸] محاسبه شده و سپس قطب شروع به حرکت پیوسته در صفحه میکند. با حرکت قطب در صفحه، نمودار قطبی دچار تغییر خواهد شد. باید الگوریتمی ارائه شود که 
را در کمترین زمان ممکن بروزرسانی نماید.
ابتدا باید بررسی شود که با حرکت قطب چه رویدادهایی ممکن است برای نمودار قطبی رخ دهد و تحت چه شرایطی دست خوش تغییرات می‌گردد.
اگر به ازای هر سایت
که پیش از این در ناحیه قطبی سایت
بوده‌است (یا به عبارت دیگر
) همچنان سایت در ناحیه قطبی سایت
بماند وعضو ناحیه قطبی سایت دیگری نشود، می‌گوییم توپولوژی نمودارNPPD دچار تغییر نشده‌است. بنابراین هر گاه والد یکی از سایتها تغییر کند، توپولوژی نمودار تغییر خواهد کرد و لازم است نمودار در زمان سریع و قابل قبول ترمیم شود که در واقع هدف اصلی مقاله میباشد.
میتوان گفت که در الگوریتم رسم نمودارNPPD هر تغییر در لیست مرتب شده ی سایتها بر اساس زاویه قطبی، باعث تغییر در توپولوژی نمودارNPPD خواهد شد.
فرض کنید قطب به طور پیوسته و البته خارج از پوسته محدب سایتها در حال حرکت درصفحه است، با توجه به نکته قبلی، کافی است که در هر لحظه لیست مرتب شده سایتها بر اساس زاویه قطبی بررسی شود، اگر این لیست مرتب شده دچار تغییر شده باشد، به این معنا است که توپولوژی نمودار قطبی تغییر کرده است.
بررسی لیست مرتب شده در هر لحظه کاری پرهزینه است. لذا روشی دیگر پیشنهاد میشود که در آن نیازی نیست که در هر لحظه لیست مرتب شده بررسی گردد. در این روش ابتدا با یک پیش پردازش، صفحه به چندین ناحیه تقسیم‌بندی میشود. ویژگی هر ناحیه در این تقسیم‌بندی این است که با حرکت قطب در هر یک از این ناحیه‌ها، ترتیب سایتها درلیست مرتب شده تغییر نمی‌کند و لذا توپولوژیNPPD بدون تغییر باقی می‌ماند. ویژگی دیگر این نواحی این است که با عبور قطب از مرز هر یک از آنها، دقیقا جای دو سایت درلیست مرتب شده جابجا خواهند شد. در ادامه به تشریح نحوه ی افراز صفحه به این نواحی پرداخته میشود.
برای تقسیم‌بندی صفحه، خط گذرنده از هر دو سایت، در صفحه رسم میشود. واضح است که با این روش 
خط در صفحه رسم خواهد شد. اثبات شده است که در یک چیدمان از خطوط که شامل خط میباشد، رأس، یال و وجه وجود دارد[13]. بنابراین با وجود
خط در صفحه، 
رأس، یال و وجه در صفحه وجود خواهد داشت که این همان پیچیدگی فضایی الگوریتم نیز است. در کلیه ی مراحل پیش پردازش و پرس و جو این مقدار فضا برای تمام ذخیره سازی ها کافی است. هر یک از ناحیه‌های بدست آمده، یک ناحیه محدب میباشد و این ناحیه‌ها یا کراندار هستند و یا یک ناحیه بدون مرز. برای ذخیره این افراز از صفحه می توان از ساختارداده‌ایDCEL استفاده نمود. این ساختمان داده برای نگهداری تقسیم‌بندی‌هایی از صفحه به کار می‌رود که تمامی نواحی کراندار و محدود شده باشند. پس از معرفی ساختمان داده مناسب برای ذخیره سازی افراز صفحه باید دید با حرکت قطب چه رویدادهایی برای نمودار قطبی رخ خواهد داد. قبل از این که قطب شروع به حرکت کند، لازم است که موقعیت قطب مشخص گردد. بدین معنی که ابتدا باید دید که قطب درکدام یک از وجه‌ها قرار دارد. بررسی این که قطب در کدام یک از این وجه ها قرار دارد، یکی از مسائل مکان‌یابی8 میباشد. میدانیم که اگر یک افراز از صفحه شامل یال باشد، در زمان مورد انتظار
میتوان ساختمان داده ای ساخت که از حافظه 
استفاده میکند و هر پرس و جو از مکان‌یابی یک نقطه را در زمان
پاسخ می‌دهد[14] . در روشی که برای افراز صفحه در مسئله نمودار قطبی با قطب نزدیک متحرک بیان شد، تعداد خطوط از مرتبه و تعداد یال‌های به وجود آمده میباشد. بنابراین بررسی این که قطب در کدام ناحیه قرار گرفته است، در زمان امکان پذیر میباشد[15]. حال باید با استفاده از این ساختار داده و با توجه به تغییراتی که با حرکت قطب در نمودار NPPD رخ می‌دهد، زمان لازم برای بروز رسانی نمودار را تحلیل کنیم. در ادامه فرض کنید خط گذرنده از دو سایت و 
را با 
نشان می‌دهیم و هر خط صفحه را به دو نیم‌صفحه تقسیم میکند. واضح است که هر گاه قطب از خط عبور کند، ترتیب دو سایت و در لیست مرتب شده بر اساس زاویه قطبی، جابجا میشود و هر گاه قطب در درون یکی از ناحیه ها حرکت کند، توپولوژی نمودارNPPD تغییر نخواهد کرد و تنها زمانی نمودارNPPD دچارتغییر میشود که قطب از خط گذرنده بین دو سایت و، عبور کند. در واقع با حرکت قطب در صفحه و عبور آن از یکی از خطوط مجاور رسم شده بین هر دو سایت دلخواه، تنها دو سایت متوالی در لیست مرتب شده‌ی سایتها بر اساس زاویه قطبی، می‌توانند با یکدیگرجابجا شوند. ابتدا رویه محدب مجموعه سایتها و قطب محاسبه میشود. این رویه محدب با 
نشان داده میشود و با حرکت قطب به روز رسانی می‌گردد. رسم برای اولین بار از مرتبه زمانی 
میباشد ولی بروز کردن آن مطابق با حرکت قطب، در زمان ثابت امکان پذیر خواهد بود. در واقع حرکت پیوسته قطب و به روز رسانی نمودار قطبی به این صورت انجام می‌پذیرد که با عبور قطب از هر یک از خطوط مربوط به افراز صفحه، تغییرات لازم در نمودار قطبی اعمال می‌گردد. همچنین به روز رسانی نیز هنگامی انجام میشود که قطب از یکی از خطوط افراز صفحه عبور نموده است. به همین دلیل اگر قطب از خط عبور کرده باشد، تنها دو سایت و برای بروز رسانی مورد بررسی قرار خواهند گرفت. اگر خط یکی از اضلاع نباشد، آنگاه رویه محدب تغییری نخواهد کرد و اگر یکی از اضلاع رویه محدب باشد، با توجه به جهت حرکت قطب یکی از دو سایت و از رویه محدب حذف و یا به آن اضافه می شوند. این یک سایت که به
اضافه می شود یا از آن حذف میشود، لزوما یکی از اعضا رویه محدب مجموعه میباشد که در زمان ثابت میتوان آن را مشخص کرد.
فرض کنید قطب از خط
عبور کرده باشد (
و 
از رئوس رویه محدب مجموعه می باشند). اگر قطب از سمت چپ این خط به سمت راست آن حرکت کرده باشد، هرکدام از دو سایت و که تا کنون عضو نبوده‌اند، از این پس یکی از رئوس خواهند بود و اگر قطب از سمت راست این خط به سمت چپ آن حرکت کند،خط مماس از قطب به رویه محدب مجموعهS، از یکی از دو سایت و خواهد گذشت که این سایت عضو باقی می ماند و سایت دیگر از حذف خواهد شد.
برای مثال تصویر۲ نشان می‌دهد که قطب از خط
عبور کرده است. خط امتداد یکی از اضلاع رویه محدب مجموعه 
میباشد و قطب از سمت راست این خط به سمت چپ آن حرکت کرده است. با عبور قطب دو سایت 
و 
موردبررسی قرار می‌گیرند. همانطور که در تصویر نیز مشخص شده است، وقتی قطب از خط عبور کرد، سایت از رویه محدب حذف می‌گردد. حال اگر فرض کنیم که ابتدا قطب در مکان 
P قرار داشته باشد، با حرکت قطب از سمت چپ خط به سمت راست آن، سایت به رویه محدب اضافه می‌گردد.
در نمودار قطبی رسم شده، هر سایت که روی قرار دارد، در ناحیه قطبی سایتی قرار دارد که در در ترتیب ساعتگرد، قبل از آن قرار دارد. به عنوان مثال میتوان درشکل۱-(b) گفت که سایتهای 
به ترتیب در ناحیه قطبی سایت قبلی خود قرار دارند.
همچنین در همان شکل۱-(b) مشخص است که اگر هر سایت
(به طور مثال سایت )روی قرار داشته باشد، این سایت مانع دید سایتهای قبل از خودش
نسبت به سایتهای بعدی 
است.
اکنون با توجه به مطالب بیان شده، ناحیه‌ای را تعیین می‌کنیم که با حرکت قطب، تنها نمودار قطبی سایتهای درون این ناحیه می‌توانند دچار تغییر شوند:
فرض کنید قطب ابتدا در مکان قرار داشته باشد. حال در صدد آن هستیم که با عبور قطب از خط به طوری که در لیست مرتب شده قبل از قرار بگیرد (برای مثال در شکل ۳ عبور قطب از خط 
)، ناحیه‌ای از صفحه مانند را مشخص کنیم که فقط نمودار قطبی داخل آن امکان تغییر دارد. ناحیه مثلثی است که یکی از رئوس آن در مکان قطب () قرار دارد و دو رأس دیگر آن به صورت زیر تعیین می‌شوند:
T ناحیه‌ای در است که بین دو خط 
و 
قرار گرفته است که در آن
سایتی است که در دو شرط زیر به طور هم‌زمان صدق کند:
۱. در لیست مرتب شده ی سایتها، بعد از سایتهای و قرار گرفته باشد. (لزومی ندارد دقیقا سایت بعدی آنها در لیست مرتب شده باشد، بلکه کافی است که شیب 
از شیب
و
کمتر باشد).
۲. مانند شکل ۳ روی قرار گرفته باشد.
با توجه به مطالب گفته شده، میتوان قضیه زیر را جمعبندی نمود.
قضیه ۲.۱: فرض کنیم قطب از خط عبور کرده باشد، مکان هندسی ناحیه‌ای از نمودار است که در خارج از آن تغییر توپولوژی رخ نخواهد داد.
اثبات: سایت‌هایی که در لیست مرتب شده براساس زاویه قطبی قبل از و هستند، تحت تأثیر ناحیه قطبی این دو سایت قرار ندارند. بنابراین مرز بالایی ناحیه‌ای که تغییر توپولوژی در خارج از آن اتفاق نمی‌افتد٬ خط خواهد بود. همانطور که قبلا گفته شد، سایتe مانع از دید سایتهای قبل از خود نسبت به سایت‌هایی میشود که درلیست مرتب شده بعد از آن قرار دارند. بنابراین مرز پایینی مکان هندسی مورد نظر خط است.□
شکل ۳ نمودار قطبی را پس از عبور قطب از خط نشان می‌دهد. تغییرات توپولوژی فقط در مثلث 
رخ داده‌است.
Algorithm 1 |
Input: S includes n Point as a set of sites, Point P=(Px, Py) as a pole, NPPD(S), V as set of vertexes in planar subdivision, F as set of faces in planar subdivision, E as set of edges in planner region of P |
Output: Updated NPPD(S) when pole moves to new point P'=(P'x,P'y) that P' is in the adjacent region of P |
Step1: Determine the polar region where the pole is located Step2: Determine the face (fi Î F) where the pole is located Step3: Determine the edge of fi that is crossed by moving the Pole (P), suppose ei=L(sa,sb) Step4: Specify region T and update polar region of the sites inside the T, suppose that number of sites inside the T be k |
2-1- الگوریتم به روز رسانی نمودار قطبی با قطب نزدیک متحرک
تصویر۴ مراحل اجرای الگوریتم نمودار قطبی با قطب نزدیک متحرک را به صورت شبه کد نشان می‌دهد. برای محاسبه پیچیدگی زمانی بروز رسانی نمودار قطبی، ابتدا در هر گام از الگوریتم، پیچیدگی زمانی را تحلیل می‌کنیم. در گام اول مشخص میشود که قطب درناحیه قطبی کدام سایت قرار گرفته است. با داشت، در زمان 
میتوان تعیین کرد که قطب در ناحیه قطبی کدام سایت است. فرض کنید قطب در ناحیه قطبی سایت قرار داشته باشد.
در گام دوم تعیین می‌گردد که قطب در کدام وجه از تقسیم‌بندی صفحه قرار گرفته است.
طبق قضیه ای که پیش‌تر بیان شده است، با یال در تقسیم‌بندی صفحه، درزمان میتوان تعیین نمود که قطب در کدام وجه قرار دارد[15].
در گام سوم تعیین میشود که قطب با حرکت پیوسته خود، از کدام یک از یال‌های وجه‌ای که در آن قرار گرفته است، عبور کرده است و این یال مربوط به خط واصل کدام دو سایت میباشد.
افراز صفحه به روش بیان شده، موجب میشود که وجه‌هایی به صورت چندضلعی‌های محدب (کراندار یا نامحدود) در صفحه ایجاد شوند. این چندضلعی‌ها در بدترین حالت ممکن است ضلع داشته باشند. برای این که مشخص شود که قطب از کدام یک از این اضلاع عبور کرده است، لازم است که تقاطع بین پاره‌خط 
و چندضلعی ای که قطب در آن قرار دارد، محاسبه گردد. در ادامه قضیه‌ای بیان میشود که نشان می‌دهد پیداکردن این تقاطع در زمان امکان پذیر میباشد [۱۶]. حال فرض کنید قطب از خط
عبور کرده باشد.
در گام چهارم باید ناحیه که در قضیه ۲.۱ بیان شد، مشخص گردد و ناحیه قطبی سایتهای درون آن به روز رسانی گردد.
فرض کنید سایت درون ناحیه قرار گرفته باشند. بروز رسانی نمودار قطبی این ازمرتب
میباشد. زیرا ترتیب این سایتها بر اساس زاویه قطبی در نمودار قطبی اصلی موجود است.
2-2- پیچیدگی زمانی به روز رسانی نمودار قطبی با قطب نزدیک متحرک
قضیه ۲.۲ برای سایت داده شده در صفحه و نمودار قطبی با قطب نزدیک و متحرک، زمان مورد نیاز برای پیش‌پردازش و زمان بازسازی نمودار در هر حرکت متوالی قطب برابر است که در آن تعداد سایتهای داخل ناحیه است.
برای محاسبه پیچیدگی زمان این الگوریتم دو نوع زمان مورد بررسی قرار می‌گیرد. یکی زمان پیش پردازش و دیگری زمان اجرا.
در زمان پیش پردازش، نمودار قطبی محاسبه می‌گردد و افراز صفحه انجام میشود و همچنین یک پیش‌پردازش نیز برای مسئله مکان‌یابی نیز صورت می‌گیرد که مرتبه زمانی تمام این موارد برابر است با:
در زمان اجرا پس از عبور قطب از هر یک از خطوط افراز صفحه، ابتدا باید مشخص نمودکه قطب از کدام خطوط افراز صفحه عبور کرده است که با توجه به مطالب گفته شده این کار درزمان انجام می‌گیرد. سپس باید نمودار قطبی به روز رسانی گردد. که تنها کافیست نمودار قطبی در درون ناحیه دوباره رسم شود. با فرض این که k سایت در این ناحیه وجود دارند که ترتیب آنها بر اساس زاویه قطبی مشخص است، میتوان در زمان نمودار قطبی را بروز رسانی نمود. بنابراین پیچیدگی زمان اجرا برابر است با: .
در ادامه و در قالب یک قضیه نتایج فوق در مورد الگوریتم و پیچیدگی های زمانی و فضایی را جمعبندی می کنیم.
قضیه ۲.2: الگوریتم 1 مساله ی محاسبه ی دیاگرام قطبی با قطب نزدیک و متحرک را برای سایت با صرف 
فضا و در زمان پیش پردازش 
حل میکند. این زمان برای هر پرس و چو در مراحل بعدی برابر است.
قضیه 2.2 نتایج نظری به دست آمده را خلاصه سازی می کند. این نتایج نظری به راحتی می توانند در انواع کاربردها در زمینه های ردیابی اتومبیل های خودراننده [18] هدایت اشیا زیر سطحی (نظیر زیر دریایی) [19]. ارتباطات مغناطیسی [20] و سایر کاربردها دیده شوند و بدیهی است استفاده از نتایج جدید در خصوص پیچیدگی زمانی، باعث ارتقا کیفیت و سرعت پردازش نرم افزارهای مرتبط خواهد شد.
3- نتیجه گیری
مسئله اصلی که در این مقاله به عنوان پژوهش اصلی مورد توجه است، حل مسئله نمودارقطبی نقاط با قطب متحرک است که در آن قطب در نزدیکی سایتها و البته خارج پوسته محدب آنها، در حال حرکت است. الگوریتمی که در این مقاله ارائه شده است، ابتدا با یک پیش‌پردازش صفحه را افراز میکند و ناحیه‌ای را که قطب در آن قرار گرفته است، مشخص میکند. سپس ناحیه‌ای را تعیین میکند که با حرکت قطب، دچار تغییرات شده است و نیاز است که این بخش از نمودار قطبی با قطب نزدیک به روز رسانی گردد. در این الگوریتم زمان پیش‌پردازش الگوریتم و زمان باز رسم نمودار در هر حرکت متوالی قطب برابر با است که در آن تعداد سایتهای درون ناحیه است که احتمال تغییر در آنها وجود دارد.
با توجه به کاربردهای بالقوه زیاد این مفهوم در بینایی ماشین و مخابرات پیشنهاد میشود علاقمندان در آینده همین مساله را برای اشیا مختلف حل کنند و کاربردهای دقیقی ارایه دهند.
4-منابع
1.Grima, CI, Márquez, A, and Ortega, L. A locus approach to angle Problems in computational geometry. In Proc. of 14th European Workshop in Computational Geometry, Barcelona, 1998.
2.Grima, CI, Márquez, A, and Ortega, L. Polar diagrams of geometric objects. In 15th European Workshop in Computational Geometry, 1999.
3.Grima, C, Márquez, A, and Ortega, L. Motion Planning and visibility Problems using Polar diagrams. In Annual conference of the European association for computer graphics, EG. Citeseer, 2003.
4.Bigham, B Sadeghi and Mohades, Ali. The dual of Polar diagrams and its extraction. In International Conference of Computational Methods in Sciences and Engineering ICCMSE, vol. 7, PP. 451–454, 2006.
5.Ortega, Lidia M, Rueda, Antonio J, and Feito, Francisco R. A solution to the Path Planning Problem using angle Pre-Processing. Robotics and Autonomous Systems, 58(1):27–36, 2010.
6.Ortega, Lidia and Robles-Ortega, M Dolores. Visibility resolution with Polar diagrams. APPl. Math, 7(5):1651–1669, 2013.
7.Bigham, B Sadeghi and Mohades, Ali. Polar diagram with respect to a near Pole. In 23rd European Workshop on Computational Geometry EWCG07, Austria, PP. 206–209. Citeseer, 2007.
8.Bigham, Bahram Sadeghi, Eskandari, Marzieh, and Tahmasbi, Maryam. Near-Pole Polar diagram of objects and duality. Journal of Computational Science, 3(3):127–131, 2012.
9.Sadeghi Bigham, Bahram, Mohades, Ali, and Ortega, Lidia. Dynamic Polar diagram. Information Processing Letters, 109(2):142–146, 2008.
10.Ehsanfar, Ebrahim, Bigham, Bahram
Sadeghi, and Madadi, Najmeh. An optimal solution for dynamic Polar diagram. in CCCG, PP. 51–54, 2010.e
11.Beygi, Mojtaba Nouri and Ghodsi, Mohammad. Polar diagram of moving objects. In 20th Annual Canadian Conference on Computational Geometry, P. 51. Citeseer, 2008.
12.بزاز، زینب، کاربرد دیاگرام ورونوی حساس به زاویه در مسایل بینایی، پایان نامه کارشناسی ارشد، دانشگاه صنعتی امیرکبیر، 1389
13.Aronov, Boris, Edelsbrunner, Herbert, Guibas, Leonidas J., and Sharir, Micha. The number of edges of many faces in a line segment arrangement. Combinatorica, 12(3):261–274, 1992.
14.De Berg, Mark, Cheong, Otfried, van Kreveld, Marc, and Overmars, Mark. Computational geometry. SPringer Berlin Heidelberg, Berlin, third ed., 2008.
15.KirkPatrick, David. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28–35, 1983.
16.Chazelle, Bernard and Dobkin, David P. Intersection of convex objects in two and three dimensions. Journal of the ACM (JACM), 34(1):1–27, 1987.
17.ربانی، فاطمه، دیاگرام قطبی با قطب متحرک. پایان نامه کارشناسی ارشد، دانشگاه تحصیلات تکمیلی علوم پایه زنجان، 1391
18.Sun, Qinbo, et al. "Tacking Control of an Autonomous Sailboat Based on Force Polar Diagram." 2018 13th World Congress on Intelligent Control and Automation (WCICA). IEEE, 2018.
19.The magnetotelluric (MT) method is commonly used to estimate the subsurface conductivity structure.
20.Pranata, Erick, Selvi Misnia Irawati, and Sintia Windhi Niasari. "Magnetotelluric Data Analysis using Swift Skew, Bahr Skew, Polar Diagram, and Phase Tensor: a Case Study in Yellowstone, US."
[1] Grima
[2] Convex hull
[3] Visibility
[4] Ortega
[5] Motion planning
[6] Kinetic Data Structure
[7] Doubly-Connected Edges List
[8] Point location
