پیمایش گراهام: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز حذف برچسب ویکی سازی |
جز ربات ردهٔ همسنگ (۳۰) +املا+مرتب+تمیز (۱۴.۹ core): + رده:الگوریتم‌های پوش محدب |
||
خط ۱۰:
برای افزایش سرعت محاسبه لازم نیست زاویهٔ واقعی که این نقاط با محور X می‌سازند محاسبه شود در عوض، محاسبه کسینوس این زاویه کافیست.
این الگوریتم با در نظر گرفتن هر نقطه در آرایه مرتب شده پیش می‌رود. برای هر نقطه این موضوع را در نظر می‌گیرد که آیا حرکت از دو نقطه‌ای که
[[
بازهم برای تعیین اینکه آیا سه نقطه تشکیل یک چرخش به چپ را می‌دهند یا چرخش به راست، نیازی نیست زاویه واقعی میان دو پاره خط محاسبه شود و در واقع می‌توانید تنها با حسابی ساده به این هدف برسید. برای سه نقطه (x1,y1)، (x2,y2)و (x3,y3)، محاسبه جهت ضرب خارجی دو برداری که با نقاط (x1,y1) , (x2,y2)و
این
{{-}}
== پیچیدگی زمانی ==
مرتب سازی نقاط دارای پیچیدگی زمانی (O(n logn می‌باشد. در حالی که ممکن است به نظر برسد پیچیدگی زمانی حلقه از O(n2) می‌باشد. زیرا برای هر نقطه به عقب برمی گردد تا چک کند آیا هر یک از نقاط قبلی چرخش به راست ایجاد می‌کنند، اما در واقع از (O(n می‌باشد زیرا هر نقطه در نهایت از هر جهت چه گردش به راست و چه گردش به چپ، دو بار در نظر گرفته می‌شود. هر نقطه فقط یک بار به عنوان نقطه
{{-}}
خط ۲۶:
{{چپ‌چین}}
# ''Three points are a counter-clockwise turn if ccw
# ''ccw <
# ''gives the signed area of the triangle formed by p1, p2 and p3.''
'''function''' ccw(p1, p2, p3):
خط ۳۹:
'''swap''' points[1] with the point with the lowest y-coordinate
'''sort''' points by polar angle with points[1]
# ''We want points[0] to be a sentinel point that will stop the loop.''
'''let''' points[0] = points[N]
# ''M will denote the number of points on the convex hull.''
'''let''' M = 2
خط ۵۴:
'''else'''
M -= 1
# ''Update M and swap points[i] to the correct place.''
M += 1
خط ۶۳:
== منابع ==
{{پانویس}}
{{چپ‌چین}}
1. ^ De Berg, Mark; Cheong, Otfried; Van Kreveld, Marc; Overmars (2008). Computational Geometry Algorithms and Applications. Berlin: Springer. pp. 2–14. doi:10.1007/978-3-540-77974-2. {{شابک|978-3-540-77973-5}}.
سطر ۷۰ ⟵ ۷۱:
[[رده:الگوریتم‌ها]]
[[رده:الگوریتم‌های پوش محدب]]
| |||