پیمایش گراهام (Graham Scan) — به زبان ساده
«پیمایش گراهام» (Graham Scan) روشی برای پیدا کردن «پوش محدب» (Convex Hull) برای یک مجموعه متناهی از نقاط موجود در صفحه است. این الگوریتم، به افتخار «رونالد گراهام» (Ronald Graham) که در سال ۱۹۷۲ الگوریتم اصلی را منتشر کرد، پیمایش گراهام نامگذاری شده است. الگوریتم پیمایش گراهام، همه راسهای قرار گرفته در امتداد مرزهای پوش محدب را پیدا میکند. در الگوریتم پیمایش گراهام از «پشته» برای شناسایی و حذف موثر تقعرها در مرزها استفاده میشود. پیچیدگی زمانی این روش از درجه O(n log n) است. در این مطلب، به طور کامل و به زبان ساده، به پیمایش گراهام پرداخته و پیادهسازی آن در «زبان برنامهنویسی پایتون» (Python Programming Language)، زبان C، «سیپلاسپلاس» (C++)، «گو» (Go)، «جاوا» (Java)، «جاوا اسکریپت» (Java Script)، «جولیا» (Julia) و «هسکل» (Haskell) انجام شده است.
پیمایش گراهام
تقریبا به طور همزمان با «جارویس مارس» (Jarvis March)، «رونالد گراهام» (R. L. Graham) نیز الگوریتمی را برای پیدا کردن پوش محدب یک مجموعه تصادفی از نقاط ارائه داد. برخلاف روش جارویس مارچ که عملیاتی از درجه O(nh) است، پیمایش گراهام از مرتبه O(nlog(n)) است. در پیچیدگی زمانی بیان شده، n تعداد نقاط و h اندازه پوش است. این یعنی پیچیدگی پیمایش گراهام به خروجی حساس نیست. علاوه بر آن، مواردی وجود دارند که روش جارویس مارس برای حل آنها بهینهتر است. این موضوع بستگی به اندازه پوش و تعداد نقاط قابل پوشش دارد.
در الگوریتم پیمایش گراهام، برخلاف الگوریتم جارویس مارس که کار از سمت چپیترین نقطه شروع میشود، پیمایش از پایین آغاز میشود. سپس، توزیع نقاط بر مبنای زاویه بین پایینترین نقطه، نقطه اصلی و هر یک از دیگر نقاط مرتبسازی میشود. پس از مرتبسازی، به صورت نقطه به نقطه، جستجو برای نقاط پوش محدب انجام و سایر نقاط به دور انداخته میشود. این کار با جستجو کردن به صورت چرخش پادساعتگرد انجام میشود. اگر زاویه بین سه نقطه، درونی شود، شکل قطعا پوش نیست. بنابراین، میتوان این نتیجه را به دور انداخت. همچنین، میتوان بررسی کرد که چرخش پادساعتگرد با توابع مثلثاتی و یا با استفاده از ضرب داخلی مانند آنچه در زیر وجود دارد است.
کد پایتون
1#Is the turn counter clockwise?
2def counter_clockwise(p1, p2, p3):
3 return (p3[1]-p1[1])*(p2[0]-p1[0]) >= (p2[1]-p1[1])*(p3[0]-p1[0])
کد C
1double ccw(struct point a, struct point b, struct point c) {
2 return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
3}
کد ++C
1bool ccw(point a, point b, point c){
2 return ((b.x - a.x)*(c.y - a.y) > (b.y - a.y)*(c.x - a.x));
3}
کد Go
1func counterClockwise(p1, p2, p3 point) bool {
2 return (p3.y-p1.y)*(p2.x-p1.x) >= (p2.y-p1.y)*(p3.x-p1.x)
3}
کد جاوا
1static double ccw(Point a, Point b, Point c) {
2 return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
3}
کد جاوا اسکریپت
1function ccw(a, b, c) {
2 return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
3}
کد جولیا
1function ccw(a::Point, b::Point, c::Point)
2 return ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x))
3end
کد هسکل
1ccw :: Point -> Point -> Point -> Double
2ccw (xa, ya) (xb, yb) (xc, yc) = (xb - xa) * (yc - ya) - (yb - ya) * (xc - xa)
اگر خروجی این تابع ۰ باشد، نقاط خطی هستند. اگر خروجی مثبت باشد، نقاط یک چرخش چپ پادساعتگرد را شکل میدهند. اگر خروجی منفی باشد، نقاط یک چرخش راست ساعتگرد را شکل میدهند. اساسا، چرخش ساعتگرد مد نظر نیست، زیرا این به معنای قرار داشتن در زاویه داخلی است.
برای کاهش مصرف حافظه و اجتناب از عملیات پرهزینه append()، در نهایت جستجو برای نقاطی که باید روی پوش باشند انجام میشود و آنها با اولین عناصر موجود در آرایه جا به جا میشوند. اگر M عنصر روی پوش وجود داشته باشند، M عنصر اول در توزیع تصادفی خروجی نقاط، پوش خواهند بود. در پایان، کد باید به صورت زیر باشد.
کد پایتون
1def graham_scan(gift):
2 gift = list(set(gift)) #Remove duplicate points
3 start = min(gift, key=lambda p: (p[1], p[0])) #Must be in hull
4 gift.remove(start)
5
6 s = sorted(gift,key=lambda point: polar_angle(start, point))
7 hull = [start,s[0],s[1]]
8
9 #Remove points from hull that make the hull concave
10 for pt in s[2:]:
11 while not counter_clockwise(hull[-2], hull[-1], pt):
12 del hull[-1]
13 hull.append(pt)
کد C
1size_t graham_scan(struct point *points, size_t size) {
2 qsort(points, size, sizeof(struct point), cmp_points);
3 polar_angles_sort(points, points[0], size);
4
5 struct point tmp_points[size + 1];
6 memcpy(tmp_points + 1, points, size * sizeof(struct point));
7 tmp_points[0] = tmp_points[size];
8
9 size_t m = 1;
10 for (size_t i = 2; i <= size; ++i) {
11 while (ccw(tmp_points[m - 1], tmp_points[m], tmp_points[i]) <= 0) {
12 if (m > 1) {
13 m--;
14 continue;
15 } else if (i == size) {
16 break;
17 } else {
18 i++;
19 }
20 }
21
22 m++;
23 struct point tmp = tmp_points[i];
24 tmp_points[i] = tmp_points[m];
25 tmp_points[m] = tmp;
26 }
27
28 memcpy(points, tmp_points + 1, size * sizeof(struct point));
29
30 return m;
31}
کد ++C
1std::vector<point> grahamScan(std::vector<point> points){
2 //selecting lowest point as pivot
3 int lowIndex = 0;
4 for(size_t i = 1; i < points.size(); i++) {
5 if(points[i].y < points[lowIndex].y){
6 lowIndex = i;
7 }
8 }
9 std::swap(points[0], points[lowIndex]);
10 point pivot = points[0];
11
12 //sorting points by polar angle
13 std::sort(points.begin()+1, points.end(), [pivot](point a, point b){
14 return ccw(pivot, a, b);
15 });
16
17 //creating convex hull
18 size_t m = 1;
19 for(size_t i = 2; i < points.size(); i++) {
20 while(ccw(points[m - 1], points[m], points[i]) <= 0){
21 if(m > 1) {
22 m--;
23 continue;
24 } else if(i == points.size()) {
25 break;
26 } else {
27 i++;
28 }
29 }
30 m++;
31 std::swap(points[i], points[m]);
32 }
33 return std::vector<point>(points.begin(), points.begin() + m + 1);
34}
کد Go
1func grahamScan(points []point) []point {
2 sort.Slice(points, func(a, b int) bool {
3 return points[a].y < points[b].y || (points[a].y == points[b].y && points[a].x < points[b].x)
4 })
5
6 start := points[0]
7 points = points[1:]
8
9 sort.Slice(points, func(a, b int) bool {
10 return polarAngle(start, points[a]) < polarAngle(start, points[b])
11 })
12
13 hull := []point{start, points[0], points[1]}
14 for _, p := range points[2:] {
15 for !counterClockwise(hull[len(hull)-2], hull[len(hull)-1], p) {
16 hull = hull[:len(hull)-1]
17 }
18 hull = append(hull, p)
19 }
20
21 return hull
22}
کد جاوا
1static List<Point> grahamScan(List<Point> gift) {
2 gift = gift.stream()
3 .distinct()
4 .sorted(Comparator.comparingDouble(point -> -point.y))
5 .collect(Collectors.toList());
6
7 Point pivot = gift.get(0);
8
9 // Sort the remaining Points based on the angle between the pivot and itself
10 List<Point> hull = gift.subList(1, gift.size());
11 hull.sort(Comparator.comparingDouble(point -> polarAngle(point, pivot)));
12
13 // The pivot is always on the hull
14 hull.add(0, pivot);
15
16 int n = hull.size();
17 int m = 1;
18
19 for (int i = 2; i < n; i++) {
20 while (ccw(hull.get(m - 1), hull.get(m), hull.get(i)) <= 0) {
21 if (m > 1) {
22 m--;
23 } else if (m == 1) {
24 break;
25 } else {
26 i++;
27 }
28 }
29 m++;
30
31 Point temp = hull.get(i);
32 hull.set(i, hull.get(m));
33 hull.set(m, temp);
34 }
35 return hull.subList(0, m + 1);
36}
کد جاوا اسکریپت
1function grahamScan(points) {
2 // First, sort the points so the one with the lowest y-coordinate comes first (the pivot)
3 points = [...points].sort((a, b) => (a.y - b.y));
4 const pivot = points[0];
5
6 // Then sort all remaining points based on the angle between the pivot and itself
7 const hull = points.slice(1).sort((a, b) => polarAngle(a, pivot) - polarAngle(b, pivot));
8
9 // The pivot is always on the hull
10 hull.unshift(pivot);
11
12 let n = hull.length;
13 let m = 1;
14 for (let i = 2; i < n; i++) {
15 while (ccw(hull[m - 1], hull[m], hull[i]) <= 0) {
16 if (m > 1) {
17 m -= 1;
18 } else if (m === i) {
19 break;
20 } else {
21 i += 1;
22 }
23 }
24
25 m += 1;
26 [hull[i], hull[m]] = [hull[m], hull[i]];
27 }
28
29 return hull.slice(0, m + 1);
30}
کد جولیا
1function graham_scan!(points::Vector{Point})
2 N = length(points)
3
4 # Place the lowest point at the start of the array
5 sort!(points, by = item -> item.y)
6
7 # Sort all other points according to angle with that point
8 other_points = sort(points[2:end], by = item -> atan(item.y - points[1].y,
9 item.x - points[1].x))
10
11 # Place points sorted by angle back into points vector
12 for i in 1:length(other_points)
13 points[i+1] = other_points[i]
14 end
15
16 # M will be the point on the hull
17 M = 2
18 for i = 1:N
19 while (ccw(points[M-1], points[M], points[i]) <= 0)
20 if (M > 2)
21 M -= 1
22 # All points are collinear
23 elseif (i == N)
24 break
25 else
26 i += 1
27 end
28 end
29
30 # ccw point found, updating hull and swapping points
31 M += 1
32 points[i], points[M] = points[M], points[i]
33 end
34
35 return points[1:M]
36end
کد هسکل
1grahamScan :: [Point] -> [Point]
2grahamScan [] = []
3grahamScan pts = wrap sortedPts [p0]
4 where p0@(x, y)= minimumBy (compare `on` snd) pts
5 sortedPts = sortOn (\(px, py) -> atan2 (py-y) (px-x) ) $ filter (/=p0) pts
6 wrap [] ps = ps
7 wrap (s:ss) [p] = wrap ss [s, p]
8 wrap (s:ss) (p1:p2:ps)
9 | ccw s p1 p2 > 0 = wrap (s:ss) (p2:ps)
10 | otherwise = wrap ss (s:p1:p2:ps)
نمونه کد پیمایش گراهام در پایتون
1from math import atan2
2
3
4#Is the turn counter clockwise?
5def counter_clockwise(p1, p2, p3):
6 return (p3[1]-p1[1])*(p2[0]-p1[0]) >= (p2[1]-p1[1])*(p3[0]-p1[0])
7
8
9#Find the polar angle of a point relative to a reference point
10def polar_angle(ref, point):
11 return atan2(point[1]-ref[1],point[0]-ref[0])
12
13
14def graham_scan(gift):
15 gift = list(set(gift)) #Remove duplicate points
16 start = min(gift, key=lambda p: (p[1], p[0])) #Must be in hull
17 gift.remove(start)
18
19 s = sorted(gift,key=lambda point: polar_angle(start, point))
20 hull = [start,s[0],s[1]]
21
22 #Remove points from hull that make the hull concave
23 for pt in s[2:]:
24 while not counter_clockwise(hull[-2], hull[-1], pt):
25 del hull[-1]
26 hull.append(pt)
27
28 return hull
29
30
31def main():
32 test_gift = [(-5, 2), (5, 7), (-6, -12), (-14, -14), (9, 9),
33 (-1, -1), (-10, 11), (-6, 15), (-6, -8), (15, -9),
34 (7, -7), (-2, -9), (6, -5), (0, 14), (2, 8)]
35 hull = graham_scan(test_gift)
36
37 print("The points in the hull are:")
38 for point in hull:
39 print(point)
40
41
42main()
نمونه کد پیمایش گراهام در C
1#include <math.h>
2#include <stddef.h>
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6
7struct point {
8 double x, y;
9};
10
11int cmp_points(const void *a, const void *b) {
12 struct point* pa = (struct point*) a;
13 struct point* pb = (struct point*) b;
14
15 if (pa->y > pb->y) {
16 return 1;
17 } else if (pa->y < pb->y) {
18 return -1;
19 } else {
20 return 0;
21 }
22}
23
24double ccw(struct point a, struct point b, struct point c) {
25 return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
26}
27
28double polar_angle(struct point origin, struct point p) {
29 return atan2(p.y - origin.y, p.x - origin.x);
30}
31
32void polar_angles_sort(struct point *points, struct point origin, size_t size) {
33 if (size < 2) {
34 return;
35 }
36
37 double pivot_angle = polar_angle(origin, points[size / 2]);
38
39 int i = 0;
40 int j = size - 1;
41 while (1) {
42 while (polar_angle(origin, points[i]) < pivot_angle) {
43 i++;
44 }
45 while (polar_angle(origin, points[j]) > pivot_angle) {
46 j--;
47 }
48
49 if (i >= j) {
50 break;
51 }
52
53 struct point tmp = points[i];
54 points[i] = points[j];
55 points[j] = tmp;
56
57 i++;
58 j--;
59 }
60
61 polar_angles_sort(points, origin, i);
62 polar_angles_sort(points + i, origin, size - i);
63}
64
65size_t graham_scan(struct point *points, size_t size) {
66 qsort(points, size, sizeof(struct point), cmp_points);
67 polar_angles_sort(points, points[0], size);
68
69 struct point tmp_points[size + 1];
70 memcpy(tmp_points + 1, points, size * sizeof(struct point));
71 tmp_points[0] = tmp_points[size];
72
73 size_t m = 1;
74 for (size_t i = 2; i <= size; ++i) {
75 while (ccw(tmp_points[m - 1], tmp_points[m], tmp_points[i]) <= 0) {
76 if (m > 1) {
77 m--;
78 continue;
79 } else if (i == size) {
80 break;
81 } else {
82 i++;
83 }
84 }
85
86 m++;
87 struct point tmp = tmp_points[i];
88 tmp_points[i] = tmp_points[m];
89 tmp_points[m] = tmp;
90 }
91
92 memcpy(points, tmp_points + 1, size * sizeof(struct point));
93
94 return m;
95}
96
97int main() {
98 struct point points[] = {{2.0, 1.9}, {1.0, 1.0}, {2.0, 4.0}, {3.0, 1.0},
99 {2.0, 0.0}};
100
101 printf("Points:\n");
102 for (size_t i = 0; i < 5; ++i) {
103 printf("(%f,%f)\n", points[i].x, points[i].y);
104 }
105
106 size_t hull_size = graham_scan(points, 5);
107
108 printf("\nHull:\n");
109 for (size_t i = 0; i < hull_size; ++i) {
110 printf("(%f,%f)\n", points[i].x, points[i].y);
111 }
112
113 return 0;
114}
نمونه کد پیمایش گراهام در ++C
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct point{
6 double x;
7 double y;
8};
9
10bool ccw(point a, point b, point c){
11 return ((b.x - a.x)*(c.y - a.y) > (b.y - a.y)*(c.x - a.x));
12}
13
14std::vector<point> grahamScan(std::vector<point> points){
15 //selecting lowest point as pivot
16 int lowIndex = 0;
17 for(size_t i = 1; i < points.size(); i++) {
18 if(points[i].y < points[lowIndex].y){
19 lowIndex = i;
20 }
21 }
22 std::swap(points[0], points[lowIndex]);
23 point pivot = points[0];
24
25 //sorting points by polar angle
26 std::sort(points.begin()+1, points.end(), [pivot](point a, point b){
27 return ccw(pivot, a, b);
28 });
29
30 //creating convex hull
31 size_t m = 1;
32 for(size_t i = 2; i < points.size(); i++) {
33 while(ccw(points[m - 1], points[m], points[i]) <= 0){
34 if(m > 1) {
35 m--;
36 continue;
37 } else if(i == points.size()) {
38 break;
39 } else {
40 i++;
41 }
42 }
43 m++;
44 std::swap(points[i], points[m]);
45 }
46 return std::vector<point>(points.begin(), points.begin() + m + 1);
47}
48
49void print(std::vector<point> points){
50 for ( auto p : points){
51 std::cout <<"(" << p.x << ", " << p.y <<")\n";
52 }
53}
54
55int main(){
56 std::vector<point> points = {{-5, 2}, {5, 7}, {-6, -12}, {-14, -14}, {9, 9},
57 {-1, -1}, {-10, 11}, {-6, 15}, {-6, -8}, {15, -9},
58 {7, -7}, {-2, -9}, {6, -5}, {0, 14}, {2, 8}};
59 std::cout << "original points are as follows:\n";
60 print(points);
61 std::vector<point> hull = grahamScan(points);
62 std::cout << "points in hull are as follows:\n";
63 print(hull);
64 return 0;
65}
نمونه کد پیمایش گراهام در Go
1package main
2
3import (
4 "fmt"
5 "math"
6 "sort"
7)
8
9type point struct {
10 x, y int
11}
12
13func counterClockwise(p1, p2, p3 point) bool {
14 return (p3.y-p1.y)*(p2.x-p1.x) >= (p2.y-p1.y)*(p3.x-p1.x)
15}
16
17func polarAngle(ref, point point) float64 {
18 return math.Atan2(float64(point.y-ref.y), float64(point.x-ref.x))
19}
20
21func grahamScan(points []point) []point {
22 sort.Slice(points, func(a, b int) bool {
23 return points[a].y < points[b].y || (points[a].y == points[b].y && points[a].x < points[b].x)
24 })
25
26 start := points[0]
27 points = points[1:]
28
29 sort.Slice(points, func(a, b int) bool {
30 return polarAngle(start, points[a]) < polarAngle(start, points[b])
31 })
32
33 hull := []point{start, points[0], points[1]}
34 for _, p := range points[2:] {
35 for !counterClockwise(hull[len(hull)-2], hull[len(hull)-1], p) {
36 hull = hull[:len(hull)-1]
37 }
38 hull = append(hull, p)
39 }
40
41 return hull
42}
43
44func main() {
45 points := []point{{-5, 2}, {5, 7}, {-6, -12}, {-14, -14}, {9, 9},
46 {-1, -1}, {-10, 11}, {-6, 15}, {-6, -8}, {15, -9},
47 {7, -7}, {-2, -9}, {6, -5}, {0, 14}, {2, 8}}
48
49 fmt.Println("The points in the hull are:")
50 hull := grahamScan(points)
51 for _, p := range hull {
52 fmt.Println(p)
53 }
54}
نمونه کد پیمایش گراهام در جاوا
1import java.util.ArrayList;
2import java.util.Comparator;
3import java.util.List;
4import java.util.stream.Collectors;
5
6public class GrahamScan {
7
8 static class Point {
9 public double x;
10 public double y;
11
12 public Point(double x, double y) {
13 this.x = x;
14 this.y = y;
15 }
16
17 @Override
18 public boolean equals(Object o) {
19 if (o == null) return false;
20 if (o == this) return true;
21 if (!(o instanceof Point)) return false;
22 Point p = (Point)o;
23 return p.x == this.x && p.y == this.y;
24 }
25 }
26
27 static double ccw(Point a, Point b, Point c) {
28 return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
29 }
30
31 static double polarAngle(Point origin, Point p) {
32 return Math.atan2(p.y - origin.y, p.x - origin.x);
33 }
34
35 static List<Point> grahamScan(List<Point> gift) {
36 gift = gift.stream()
37 .distinct()
38 .sorted(Comparator.comparingDouble(point -> -point.y))
39 .collect(Collectors.toList());
40
41 Point pivot = gift.get(0);
42
43 // Sort the remaining Points based on the angle between the pivot and itself
44 List<Point> hull = gift.subList(1, gift.size());
45 hull.sort(Comparator.comparingDouble(point -> polarAngle(point, pivot)));
46
47 // The pivot is always on the hull
48 hull.add(0, pivot);
49
50 int n = hull.size();
51 int m = 1;
52
53 for (int i = 2; i < n; i++) {
54 while (ccw(hull.get(m - 1), hull.get(m), hull.get(i)) <= 0) {
55 if (m > 1) {
56 m--;
57 } else if (m == 1) {
58 break;
59 } else {
60 i++;
61 }
62 }
63 m++;
64
65 Point temp = hull.get(i);
66 hull.set(i, hull.get(m));
67 hull.set(m, temp);
68 }
69 return hull.subList(0, m + 1);
70 }
71
72 public static void main(String[] args) {
73 ArrayList<Point> points = new ArrayList<>();
74
75 points.add(new Point(-5, 2));
76 points.add(new Point(5, 7));
77 points.add(new Point(-6, -12));
78 points.add(new Point(-14, -14));
79 points.add(new Point(9, 9));
80 points.add(new Point(-1, -1));
81 points.add(new Point(-10, 11));
82 points.add(new Point(-6, 15));
83 points.add(new Point(-6, -8));
84 points.add(new Point(15, -9));
85 points.add(new Point(7, -7));
86 points.add(new Point(-2, -9));
87 points.add(new Point(6, -5));
88 points.add(new Point(0, 14));
89 points.add(new Point(2, 8));
90
91 List<Point> convexHull = grahamScan(points);
92
93 convexHull.forEach(p -> System.out.printf("% 1.0f, % 1.0f\n", p.x, p.y));
94 }
95}
نمونه کد پیمایش گراهام در جاوا اسکریپت
1function grahamScan(points) {
2 // First, sort the points so the one with the lowest y-coordinate comes first (the pivot)
3 points = [...points].sort((a, b) => (a.y - b.y));
4 const pivot = points[0];
5
6 // Then sort all remaining points based on the angle between the pivot and itself
7 const hull = points.slice(1).sort((a, b) => polarAngle(a, pivot) - polarAngle(b, pivot));
8
9 // The pivot is always on the hull
10 hull.unshift(pivot);
11
12 let n = hull.length;
13 let m = 1;
14 for (let i = 2; i < n; i++) {
15 while (ccw(hull[m - 1], hull[m], hull[i]) <= 0) {
16 if (m > 1) {
17 m -= 1;
18 } else if (m === i) {
19 break;
20 } else {
21 i += 1;
22 }
23 }
24
25 m += 1;
26 [hull[i], hull[m]] = [hull[m], hull[i]];
27 }
28
29 return hull.slice(0, m + 1);
30}
31
32function polarAngle(a, b) {
33 return Math.atan2(a.y - b.y, a.x - b.x);
34}
35
36function ccw(a, b, c) {
37 return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
38}
39
40const points = [
41 { x: 1, y: 3 },
42 { x: 2, y: 4 },
43 { x: 4, y: 0 },
44 { x: 1, y: 0 },
45 { x: 0, y: 2 },
46 { x: 2, y: 2 },
47 { x: 3, y: 4 },
48 { x: 3, y: 1 },
49];
50
51const convexHull = grahamScan(points);
52convexHull.forEach(p => console.log(`(${p.x}, ${p.y})`));
نمونه کد پیمایش گراهام در جولیا
1struct Point
2 x::Float64
3 y::Float64
4end
5
6function ccw(a::Point, b::Point, c::Point)
7 return ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x))
8end
9
10function graham_scan!(points::Vector{Point})
11 N = length(points)
12
13 # Place the lowest point at the start of the array
14 sort!(points, by = item -> item.y)
15
16 # Sort all other points according to angle with that point
17 other_points = sort(points[2:end], by = item -> atan(item.y - points[1].y,
18 item.x - points[1].x))
19
20 # Place points sorted by angle back into points vector
21 for i in 1:length(other_points)
22 points[i+1] = other_points[i]
23 end
24
25 # M will be the point on the hull
26 M = 2
27 for i = 1:N
28 while (ccw(points[M-1], points[M], points[i]) <= 0)
29 if (M > 2)
30 M -= 1
31 # All points are collinear
32 elseif (i == N)
33 break
34 else
35 i += 1
36 end
37 end
38
39 # ccw point found, updating hull and swapping points
40 M += 1
41 points[i], points[M] = points[M], points[i]
42 end
43
44 return points[1:M]
45end
46
47function main()
48 # This hull is just a simple test so we know what the output should be
49 points = [
50 Point(-5,2), Point(5,7), Point(-6,-12), Point(-14,-14), Point(9,9),
51 Point(-1,-1), Point(-10,11), Point(-6,15), Point(-6,-8), Point(15,-9),
52 Point(7,-7), Point(-2,-9), Point(6,-5), Point(0,14), Point(2,8)
53 ]
54 hull = graham_scan!(points)
55 println(hull)
56end
57
58main()
نمونه کد پیمایش گراهام در هسکل
1import Data.List (sortOn, minimumBy)
2import Data.Function (on)
3
4type Point = (Double, Double)
5
6ccw :: Point -> Point -> Point -> Double
7ccw (xa, ya) (xb, yb) (xc, yc) = (xb - xa) * (yc - ya) - (yb - ya) * (xc - xa)
8
9grahamScan :: [Point] -> [Point]
10grahamScan [] = []
11grahamScan pts = wrap sortedPts [p0]
12 where p0@(x, y)= minimumBy (compare `on` snd) pts
13 sortedPts = sortOn (\(px, py) -> atan2 (py-y) (px-x) ) $ filter (/=p0) pts
14 wrap [] ps = ps
15 wrap (s:ss) [p] = wrap ss [s, p]
16 wrap (s:ss) (p1:p2:ps)
17 | ccw s p1 p2 > 0 = wrap (s:ss) (p2:ps)
18 | otherwise = wrap ss (s:p1:p2:ps)
19
20main = do
21 -- We build the set of points of integer coordinates within a circle of radius 5
22 let pts = [(x,y) | x<-[-5..5], y<-[-5..5], x^2+y^2<=5^2]
23 -- And extract the convex hull
24 print $ grahamScan pts
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش ساختمان دادهها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی
- برنامه تشخیص وجود دور در گراف جهتدار — راهنمای کاربردی
- رنگآمیزی گراف به روش حریصانه — به زبان ساده
^^