پیمایش گراهام (Graham Scan) — به زبان ساده

۵۰۱ بازدید
آخرین به‌روزرسانی: ۲۰ تیر ۱۴۰۲
زمان مطالعه: ۱۲ دقیقه
پیمایش گراهام (Graham Scan) — به زبان ساده

«پیمایش گراهام» (Graham Scan) روشی برای پیدا کردن «پوش محدب» (Convex Hull) برای یک مجموعه متناهی از نقاط موجود در صفحه است. این الگوریتم، به افتخار «رونالد گراهام» (Ronald Graham) که در سال ۱۹۷۲ الگوریتم اصلی را منتشر کرد، پیمایش گراهام نام‌گذاری شده است. الگوریتم پیمایش گراهام، همه راس‌های قرار گرفته در امتداد مرزهای پوش محدب را پیدا می‌کند. در الگوریتم پیمایش گراهام از «پشته» برای شناسایی و حذف موثر تقعرها در مرزها استفاده می‌شود. پیچیدگی زمانی این روش از درجه O(n log n)‎ است. در این مطلب، به طور کامل و به زبان ساده، به پیمایش گراهام پرداخته و پیاده‌سازی آن در «زبان برنامه‌نویسی پایتون» (Python Programming Language)، زبان C، «سی‌پلاس‌پلاس» (C++‎)، «گو» (Go)، «جاوا» (Java)، «جاوا اسکریپت» (Java Script)، «جولیا» (Julia) و «هسکل» (Haskell) انجام شده است.

پیمایش گراهام (Graham Scan) -- به زبان ساده

پیمایش گراهام

تقریبا به طور هم‌زمان با «جارویس مارس» (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

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۳ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
ویکی‌پدیای انگلیسیalgorithm-archive
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *