سریع ترین روش برای یافتن مستطیل های همسایه - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

سریع ترین روش برای یافتن مستطیل های همسایه

+1 امتیاز

سلام.

من قصد دارم که با توجه به شکل زیر برای هر مستطیل نزدیک همسایه آن را پیدا کنم.سریع ترین روش پیشنهادی شما چیست؟

c++, vector, nearest-neighbor, هوش مصنوعی, الگوریتم

ممنون

سوال شده شهریور 7, 1393  بوسیله ی ملک پور (امتیاز 145)   8 27 33
ویرایش شده دی 30, 1393 بوسیله ی haniye sarbazi

1 پاسخ

0 امتیاز
سلام.اگه بتونی مرکز هر مستطیل رو پیدا کنی و فاصله مرکز هر مستطیل رو با مستطیل های دیگه از رابطه اقلیدسی محاسبه کن اونوقت اونی که کمترین فاصله رو با هر مستطیل داره میتونه نزدیکترین همسایش باشد

واسه بهدست اوردن مرکز مستطیل x = (x1+x2)/2 و y = (y1+y2)/2 را محاسبه کنی که x1 و x2 به ترتیب مختصات x ابتدا و انتهای یکی از قطزهای مستطیله و y1 و y2 هم به همین ترتیب.
پاسخ داده شده شهریور 7, 1393 بوسیله ی Pashmak (امتیاز 644)   8 15 31
ممنون.این روش خیلی خیلی کنده یعنی شما باید همه مستطیل ها را با هم تمام مستطیل ها distance بگیرید.order اینکار در بدترین حالت همین روشیه که فرمودید
روش دیگه ای که میشه در نظر گرفت  مثلا نقطه ای در صفحه در نظر بگیر فرض کن نقطه در نظر گرفته در گوشه بالا سمت راست باشه. حالا فاصله اقلیدسی مرکز تمامی مستطیل ها رو تا اون نقطه حساب کن. مرحله بعدی  دسته بندی مستطیل هاست در بازه های مربوطه شان. مثلا کل بازه فاصله (یعنی شروع از کمترین فاصله تا بیشترین فاصله از نقطه در نظر گرفته شده) رو به چندین دسته تقسیم کن. مثلا فرض کن کمترین فاصله 5 باشه و بیشترین فاصله 20 باشه. در اینجا می تونی 3 تا بازه تشکیل بدی. که بازه اولت از 5 تا 10، بازه دوم از 10.00001 تا 15 و بازه آخر هم از 15.00001 تا 20. تقسیم بندی بازه ها با خودته. حالا هر مستطیل رو می تونی با مستطیل داخل بازه خودش برای پیدا کردن نزدیک ترین همسایگی بررسی کنی. این روش باعث میشه که نخواد هر مستطیلی رو با همه مستطیل ها بررسی کنی. هر چه بازه ها رو کوچکتر در نظر بگیری احتمال پیدا شدن همسایه برای یک مستطیل بالاترمیره.
خوب اگر اینطوری باشه به فرض یک مربعی در 10 باشه و همسایش تو 11 اینا  دو تا توی یک بازه نیستند پس در نتیجه همسایه هم نیستند .
 با روش شما نمی تونیم برای مربع 10 همسایه 11 را پیدا کنیم و یا بالعکس.
بالاتر هم در حمله آخر گفتم در روش دوم همه چیز بستگی به بازه مورد نظر داره.
در روش دیگه می تونی مثلا دو تا نقطه رو برای اندازه گیری فاصله اقلیدسی تعریف کنی. به این صورت در ابتدا دو تا نقطه به صورت تصادفی در صفحه انتخاب کنی. فاصله مرکز تمامی مستطیلها رو با این دو نقطه حساب کن و دوباره طبق حالت قبلی همسایگی ها رو تشکیل بده. در اینجا برای هر مستطیل دو تا مجموعه همسایگی درست میشه توی هر مجموعه می تونی نزدیک ترین همسایگی رو انتخاب کنی بعدش فاصله مرکز مستطیل را با دو همسابه به دست آمده از دو مجموعه محاسبه کن اونی که کمترین فاصله رو داره می تونه به عنوان نزدیک ترین همسایه شناخته بشه. در این روش هر چی به تعداد نقاط افزایش پیدا کنه تعداد مجموعه های همسایگی هم بیشتر میشه در نتیجه دقت محاسبات برای به دست آوردن نزدیک ترین همسایه بیشتر میشه اما محاسبات با افزایش تعداد نقاط بیشتر میشه
...