در این مطلب، ویدئو اسکن گراهام: پسزمینه و کد پایتون با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,060 –> 00:00:02,790
چه اتفاقی برای همه در این ویدیو می افتد،
2
00:00:02,790 –> 00:00:04,350
ما سری الگوریتم پایتون
3
00:00:04,350 –> 00:00:05,819
خود را با معرفی الگوریتم اسکن گراهام ادامه می دهیم،
4
00:00:05,819 –> 00:00:07,799
یک رویکرد کارآمد برای
5
00:00:07,799 –> 00:00:10,139
ساخت بدنه های محدب،
6
00:00:10,139 –> 00:00:11,160
ابتدای این درس به طور خلاصه برخی از
7
00:00:11,160 –> 00:00:13,139
پیشینه ها را در مورد بدنه های محدب پوشش می دهد و
8
00:00:13,139 –> 00:00:14,460
به نظریه پشت گراهام می پردازد.
9
00:00:14,460 –> 00:00:16,079
الگوریتم اسکن تا پایان،
10
00:00:16,079 –> 00:00:17,190
ویرایشگر کدنویسی خود را باز می کنیم و
11
00:00:17,190 –> 00:00:18,930
الگوریتم اسکن گراهام را در پایتون به
12
00:00:18,930 –> 00:00:20,490
همراه چند نمونه آزمایشی و تجسم پیاده سازی می کنیم
13
00:00:20,490 –> 00:00:22,529
تا اطمینان حاصل کنیم که رویکرد ما معتبر است، همانطور که
14
00:00:22,529 –> 00:00:23,880
همیشه
15
00:00:23,880 –> 00:00:25,199
اگر از ویدیو لذت می برید به من کمک کنید یا نظر خود را ارسال کنید.
16
00:00:25,199 –> 00:00:26,820
و اگر می خواهید
17
00:00:26,820 –> 00:00:28,439
در مورد بقیه محتوای کدنویسی پایتون من به روز بمانید، مشترک شوید تا
18
00:00:28,439 –> 00:00:31,410
19
00:00:31,410 –> 00:00:32,640
قبل از اینکه بتوانیم واقعاً در مورد
20
00:00:32,640 –> 00:00:34,079
الگوریتم اسکن گراهام صحبت کنیم، باید
21
00:00:34,079 –> 00:00:36,570
بدانیم که بدنه محدب چیست، همانطور که
22
00:00:36,570 –> 00:00:38,160
می بینیم. اسلاید مجموعه ای از نقاط XY داده می شود
23
00:00:38,160 –> 00:00:40,230
، بدنه محدب کوچکترین
24
00:00:40,230 –> 00:00:42,440
مجموعه محدب را که شامل تمام نقاط است، تشکیل می
25
00:00:42,440 –> 00:00:44,489
دهد، بنابراین اگر
26
00:00:44,489 –> 00:00:46,770
مجموعه ای از نقاط XY برای شما ارائه شود، d از شما خواسته می شود تا
27
00:00:46,770 –> 00:00:48,660
بدنه محدب را بسازید که باید
28
00:00:48,660 –> 00:00:50,129
زیر مجموعه ای از آن
29
00:00:50,129 –> 00:00:52,350
نقاط را برگردانید که تماما محدب هستند و
30
00:00:52,350 –> 00:00:54,600
حاوی تک تک نقاط این درس هستند،
31
00:00:54,600 –> 00:00:55,800
فرض می کنم شما از قبل می دانید محدب
32
00:00:55,800 –> 00:00:57,420
به چه معناست، اما اگر نه در واقع یک
33
00:00:57,420 –> 00:00:58,739
راه واقعا ساده وجود دارد. بررسی اینکه آیا
34
00:00:58,739 –> 00:01:01,379
شکل شما محدب است، کاری که انجام میدهید این است
35
00:01:01,379 –> 00:01:02,489
که از هر یک از راسهای
36
00:01:02,489 –> 00:01:04,680
شکل شروع کنید و
37
00:01:04,680 –> 00:01:06,960
38
00:01:06,960 –> 00:01:10,860
اگر مجبور شدید در
39
00:01:10,860 –> 00:01:12,659
جهت عقربههای ساعت به سمت بیرون بچرخید تا به راس بعدی بروید، شکل را به ترتیب خلاف جهت عقربههای ساعت از راس به راس دیگر بچرخانید.
40
00:01:12,659 –> 00:01:14,939
راس محدب نیست، یعنی
41
00:01:14,939 –> 00:01:17,189
مقعر خواهد بود، بنابراین برای پنتاگون در
42
00:01:17,189 –> 00:01:19,110
سمت راست میدانیم که محدب است،
43
00:01:19,110 –> 00:01:20,220
زیرا
44
00:01:20,220 –> 00:01:22,350
اگر رئوس را در
45
00:01:22,350 –> 00:01:25,950
خلاف جهت عقربههای ساعت بچرخانیم، راهی برای
46
00:01:25,950 –> 00:01:28,409
تجسم بدنه محدب 2 بعدی، هرگز لازم نیست که در جهت عقربههای ساعت بچرخیم.
47
00:01:28,409 –> 00:01:29,880
توضیح دادن آن دشوارتر از دیدن
48
00:01:29,880 –> 00:01:31,970
حضوری خواهد بود که
49
00:01:31,970 –> 00:01:33,780
اساساً اگر به یک
50
00:01:33,780 –> 00:01:35,220
تخته میخ مانند در سمت
51
00:01:35,220 –> 00:01:37,170
راست پایین صفحه دسترسی داشته باشید و
52
00:01:37,170 –> 00:01:38,850
در هر یک از گیره ها قرار داده باشید، این آزمایش نوار لاستیکی است. مکان نقاط XY
53
00:01:38,850 –> 00:01:41,040
در ورودی خود می توانید یک
54
00:01:41,040 –> 00:01:42,479
نوار لاستیکی را در اطراف بیرونی
55
00:01:42,479 –> 00:01:44,520
گیره ها بکشید و به طور خودکار
56
00:01:44,520 –> 00:01:46,409
در جهت دقیق بدنه محدب
57
00:01:46,409 –> 00:01:49,530
قرار می گیرد و برای آن نقاط داده دقیق می توانید
58
00:01:49,530 –> 00:01:50,939
به مثال در تصویر بگردید،
59
00:01:50,939 –> 00:01:52,530
چهار نقطه داخل آن وجود دارد.
60
00:01:52,530 –> 00:01:54,360
بدنه محدب که سه باند لاستیکی را لمس میکنند
61
00:01:54,360 –> 00:01:56,700
و چهارمی در مرکز اکنون که
62
00:01:56,700 –> 00:01:57,899
ما یک ایده تقریبی از ظاهر بدنه محدب
63
00:01:57,899 –> 00:01:59,430
داریم ممکن است تعجب کنید که
64
00:01:59,430 –> 00:02:00,960
آنها برای چه چیزی میتوانند در دنیای واقعی استفاده شوند،
65
00:02:00,960 –> 00:02:03,119
مثالی عالی از یک موضوع داغ درست است. در حال
66
00:02:03,119 –> 00:02:04,860
حاضر اجتناب از اشیا با
67
00:02:04,860 –> 00:02:07,110
اتومبیل های خودران یا هر وسیله نقلیه خودکاری
68
00:02:07,110 –> 00:02:09,479
است، تصور کنید که در حال رانندگی اتومبیل
69
00:02:09,479 –> 00:02:11,008
مجهز به سنسوری است که فقط می
70
00:02:11,008 –> 00:02:13,560
تواند چراغ های عقب قرمز یا یک دوربین خام را تشخیص دهد که
71
00:02:13,560 –> 00:02:13,710
72
00:02:13,710 –> 00:02:15,120
فقط می تواند لبه های اتومبیل
73
00:02:15,120 –> 00:02:16,680
های مقابل شما را تشخیص دهد. هر یک از این موارد
74
00:02:16,680 –> 00:02:17,820
اگر ماشین شما مایل به
75
00:02:17,820 –> 00:02:19,560
تصمیم گیری آگاهانه است، برای این منظور باید از
76
00:02:19,560 –> 00:02:21,120
محدوده بیرونی همه وسایل نقلیه اطراف خود مطلع
77
00:02:21,120 –> 00:02:23,520
باشد، داده های جمع آوری شده
78
00:02:23,520 –> 00:02:24,990
توسط دوربین. سیستم را می توان به
79
00:02:24,990 –> 00:02:26,270
الگوریتمی برای ساخت بدنه محدب وارد کرد که به
80
00:02:26,270 –> 00:02:28,350
طور موثر داده های تصویر خام را
81
00:02:28,350 –> 00:02:30,150
به خطوط کلی همه وسایل نقلیه اطراف تبدیل می کند،
82
00:02:30,150 –> 00:02:32,490
زیرا مطمئن هستم که متوجه می شوید این
83
00:02:32,490 –> 00:02:34,050
یکی از نمونه های متعدد است
84
00:02:34,050 –> 00:02:36,150
که اساساً هر زمانی که بخواهیم
85
00:02:36,150 –> 00:02:37,920
اطلاعات را از یک مجموعه تقطیر کنیم. از
86
00:02:37,920 –> 00:02:40,110
نقاط دادههای فضایی یا حتی پنهان،
87
00:02:40,110 –> 00:02:43,050
بدنه محدب ممکن است مفید باشد، بنابراین اکنون
88
00:02:43,050 –> 00:02:44,730
پیشزمینهای در مورد بدنههای محدب
89
00:02:44,730 –> 00:02:46,430
و نحوه استفاده از آنها در عمل پوشش
90
00:02:46,430 –> 00:02:48,360
دادهایم، آن را به موضوع اصلی این ویدیو منتقل میکنیم که
91
00:02:48,360 –> 00:02:50,420
چگونه میشوند.
92
00:02:50,420 –> 00:02:52,530
حتی اگر این درس بر
93
00:02:52,530 –> 00:02:54,180
روی اسکن گراهام تمرکز دارد، توجه داشته باشید که در
94
00:02:54,180 –> 00:02:55,860
صورت
95
00:02:55,860 –> 00:02:57,420
نیاز به ایجاد
96
00:02:57,420 –> 00:02:59,840
بدنه های محدب در یک برنامه دنیای واقعی، رویکردهای ممکن متعددی وجود دارد،
97
00:02:59,840 –> 00:03:01,980
بدیهی است که هر رویکرد متفاوت
98
00:03:01,980 –> 00:03:04,320
مزایا و معایب خاص خود را در
99
00:03:04,320 –> 00:03:05,640
این اسلاید دارد.
100
00:03:05,640 –> 00:03:06,810
101
00:03:06,810 –> 00:03:09,180
هنگام مقایسه
102
00:03:09,180 –> 00:03:10,860
الگوریتمهای بدنه محدب که کارایی را
103
00:03:10,860 –> 00:03:13,500
با استفاده از اندازه ورودی و اندازه ورودی ارزیابی میکنیم، میتوان میانگین پیچیدگیهای زمانی را برای برخی از رویکردهای محبوبتر مشاهده کرد. d و
104
00:03:13,500 –> 00:03:16,650
همچنین خروجی یک حفره با اندازه H، برای مثال
105
00:03:16,650 –> 00:03:17,910
اگر روی پروژه ای کار می کنید
106
00:03:17,910 –> 00:03:19,950
که اندازه ورودی بزرگی دارید اما بدانید که
107
00:03:19,950 –> 00:03:21,600
بدنه نهایی فقط از
108
00:03:21,600 –> 00:03:23,310
تعداد حداقلی از نقاط داده تشکیل شده است، ممکن است
109
00:03:23,310 –> 00:03:24,570
بخواهید انتخاب کنید. الگوریتمی
110
00:03:24,570 –> 00:03:26,280
مانند چان که به
111
00:03:26,280 –> 00:03:29,430
اندازه بدنه نهایی حساس است، ایده معرفی
112
00:03:29,430 –> 00:03:31,290
اسکن گراهام در واقع
113
00:03:31,290 –> 00:03:34,080
توسط یک بیننده جان کانگر لیو به من توصیه شد و من
114
00:03:34,080 –> 00:03:35,030
واقعاً این ایده را دوست دارم که
115
00:03:35,030 –> 00:03:36,930
اسکن گراهام عملکرد رقابتی را
116
00:03:36,930 –> 00:03:38,790
عمدتاً به استفاده از مرتبسازی کارآمد بستگی دارد.
117
00:03:38,790 –> 00:03:40,650
ما به تازگی سری الگوریتم مرتبسازی خود را به پایان رساندهایم،
118
00:03:40,650 –> 00:03:42,540
119
00:03:42,540 –> 00:03:43,740
باید بتوانیم بسیاری از چیزهایی را
120
00:03:43,740 –> 00:03:45,300
که برای بهبود ساخت بدنههای محدب آموختهایم به همراه داشته باشیم،
121
00:03:45,300 –> 00:03:48,270
بنابراین در سطح بالاتر
122
00:03:48,270 –> 00:03:49,590
آنچه را که در داخل الگوریتم اسکن گراهام اتفاق میافتد پوشش
123
00:03:49,590 –> 00:03:51,600
دادهایم.
124
00:03:51,600 –> 00:03:53,370
از نقاط و برگرداندن زیر مجموعه ای از آن
125
00:03:53,370 –> 00:03:54,930
نقاط که نقاط روی
126
00:03:54,930 –> 00:03:57,240
بدنه محدب را در سطح پایین تر تشکیل می دهند، می
127
00:03:57,240 –> 00:03:58,650
توانیم اجرا را به چهار
128
00:03:58,650 –> 00:04:00,750
مرحله مجزا در اولین مرحله که
129
00:04:00,750 –> 00:04:02,640
محل poi را تعیین می کنیم تقسیم کنیم. nt در مجموعه ورودی
130
00:04:02,640 –> 00:04:04,800
با کمترین مختصات y، اگر
131
00:04:04,800 –> 00:04:06,180
چندین نقطه وجود داشته باشد که کمترین
132
00:04:06,180 –> 00:04:07,440
مختصات y را به اشتراک میگذارند، یکی را انتخاب میکنیم که
133
00:04:07,440 –> 00:04:09,720
کمترین مختصات x را داشته باشد، در اینجا این
134
00:04:09,720 –> 00:04:11,700
نقطه را P مینامیم و از کلمه استفاده میکنیم.
135
00:04:11,700 –> 00:04:12,930
لنگر چون فکر میکنم
136
00:04:12,930 –> 00:04:14,790
با دقت بیشتری آنچه را که در مرحله دوم اتفاق میافتد توصیف میکند،
137
00:04:14,790 –> 00:04:16,200
ما نقاط باقیمانده
138
00:04:16,200 –> 00:04:17,579
را به ترتیب افزایش
139
00:04:17,579 –> 00:04:20,730
زاویه قطبی به نقطه P مرتب میکنیم، همانطور که
140
00:04:20,730 –> 00:04:22,260
در تصویر میبینید، میتوانیم با
141
00:04:22,260 –> 00:04:23,730
ترسیم تمام نقاط با توجه به
142
00:04:23,730 –> 00:04:25,830
P این را تجسم کنیم. در مبدأ و رد کردن یک خط
143
00:04:25,830 –> 00:04:27,280
در خلاف جهت عقربههای ساعت
144
00:04:27,280 –> 00:04:29,569
با شروع از محور x مثبت، هر
145
00:04:29,569 –> 00:04:30,919
نقطه به لیست اضافه میشود به
146
00:04:30,919 –> 00:04:32,780
ترتیبی که
147
00:04:32,780 –> 00:04:34,520
اگر نقاطی با زاویه قطبی مشابه وجود داشته باشد،
148
00:04:34,520 –> 00:04:36,080
مرتبسازی ثانویه را به ترتیب
149
00:04:36,080 –> 00:04:38,720
افزایش اعمال میکنیم. فاصله از P پس از
150
00:04:38,720 –> 00:04:40,190
مرتبسازی نقاط باقیمانده، میتوانیم
151
00:04:40,190 –> 00:04:41,419
فهرست دیگری را برای نگه داشتن نقاط روی
152
00:04:41,419 –> 00:04:43,669
بدنه محدب شروع کنیم و آن را با
153
00:04:43,669 –> 00:04:45,740
P اولین عنصر و اولین
154
00:04:45,740 –> 00:04:48,169
عنصر فهرست مرتبشده به عنوان دومین عنصر
155
00:04:48,169 –> 00:04:49,550
است. وارد حلقه اصلی اسکن گراهام شوید،
156
00:04:49,550 –> 00:04:51,440
جایی که ما روی عناصر باقیمانده
157
00:04:51,440 –> 00:04:53,750
از لیست مرتب شده برای هر
158
00:04:53,750 –> 00:04:55,099
عنصری که بررسی می کنیم، تکرار می کنیم تا ببینیم که آیا اضافه کردن آن به
159
00:04:55,099 –> 00:04:56,780
بدنه محدب فعلی منجر به
160
00:04:56,780 –> 00:04:58,819
چرخش جهت عقربه های ساعت نسبت به
161
00:04:58,819 –> 00:05:01,340
دو عنصر قبلی می شود. باعث
162
00:05:01,340 –> 00:05:02,990
چرخش در جهت عقربههای ساعت میشود، میدانیم که
163
00:05:02,990 –> 00:05:04,630
مشکلی در خانه فعلی ما وجود دارد،
164
00:05:04,630 –> 00:05:06,500
زیرا از ما خواسته شده است که شکل محدب باشد.
165
00:05:06,500 –> 00:05:08,720
پیمایش خلاف جهت عقربههای ساعت
166
00:05:08,720 –> 00:05:10,130
راسها هرگز نیازی به
167
00:05:10,130 –> 00:05:13,130
چرخش در جهت عقربههای ساعت ندارد، بنابراین تا زمانی که
168
00:05:13,130 –> 00:05:14,569
اضافه کردن این نقطه جدید نتیجه ای نداشته باشد، به عقب برمیگردیم. در
169
00:05:14,569 –> 00:05:16,220
یک چرخش در جهت عقربههای ساعت، وقتی میگوییم
170
00:05:16,220 –> 00:05:17,569
در اینجا به عقب برگردید، منظور ما
171
00:05:17,569 –> 00:05:19,130
حذف آخرین عنصر در بدنه محدب است
172
00:05:19,130 –> 00:05:21,139
و همانطور که گفتیم این کار تکرار میشود
173
00:05:21,139 –> 00:05:22,849
تا زمانی که نقطه جدید را اضافه کنید،
174
00:05:22,849 –> 00:05:24,470
به جای چرخش در جهت عقربههای ساعت
175
00:05:24,470 –> 00:05:27,289
در هدیه پایین سمت راست، به چرخش در خلاف جهت عقربههای ساعت منجر شود.
176
00:05:27,289 –> 00:05:28,580
شما می توانید ببینید که
177
00:05:28,580 –> 00:05:30,440
هر زمان که نقطه ای از بدنه محدب فعلی حذف شود،
178
00:05:30,440 –> 00:05:37,820
پس از اتمام
179
00:05:37,820 –> 00:05:39,530
تکرار بر روی نقاط مرتب شده،
180
00:05:39,530 –> 00:05:41,389
بدنه لی رخ می دهد. st فقط شامل عناصر
181
00:05:41,389 –> 00:05:43,669
موجود در بدنه محدب به منظور
182
00:05:43,669 –> 00:05:47,210
افزایش زاویه قطبی از P خواهد بود، اکنون که
183
00:05:47,210 –> 00:05:48,320
مراحل مربوط به
184
00:05:48,320 –> 00:05:49,969
اسکن گراهام را پوشش داده ایم، ویرایشگر کدنویسی خود را باز کرده
185
00:05:49,969 –> 00:05:51,110
و الگوریتم را در پایتون پیاده سازی می کنیم،
186
00:05:51,110 –> 00:05:53,840
بنابراین قبل از اینکه به
187
00:05:53,840 –> 00:05:55,250
تابع اسکن واقعی گراهام ما چندین
188
00:05:55,250 –> 00:05:57,560
تابع کمکی باقی مانده است که ابتدا باید آن را پوشش دهیم تا
189
00:05:57,560 –> 00:05:59,060
شروع کنیم، برای کار کردن با آن به چند نقطه داده XY نیاز داریم،
190
00:05:59,060 –> 00:06:00,740
بنابراین برای این منظور
191
00:06:00,740 –> 00:06:02,409
یک تابع می نویسیم و نقاط ایجاد می کنیم
192
00:06:02,409 –> 00:06:04,550
که اولین پارامتر برای ایجاد
193
00:06:04,550 –> 00:06:06,289
تعداد نقاط نشان دهنده تعداد نقاط داده ای
194
00:06:06,289 –> 00:06:08,360
که باید برای هر نقطه داده ایجاد کنیم، هر
195
00:06:08,360 –> 00:06:09,889
دو مختصات X و y
196
00:06:09,889 –> 00:06:11,210
به طور تصادفی با استفاده از تابع راندون انتخاب می شوند،
197
00:06:11,210 –> 00:06:14,000
ما تابع تصادفی را
198
00:06:14,000 –> 00:06:15,680
با پارامترهای دوم و سوم min و
199
00:06:15,680 –> 00:06:17,509
Max ارسال کردیم تا همه مقادیر به
200
00:06:17,509 –> 00:06:22,909
طور پیش فرض در یک محدوده ب