Graham Scan Algorithm
(Convex Hulls)
By
Group: 10
Group Details
# Name ID
1 Saimon Islam Chamok 011202002
2 K.M. Safiqur Rahaman Bapon 011202057
3 Zannatun Ferdous 0112310558
Table of Contents
# Content Name
1 Definition
2 Problem Statement
3 Brief History
4 Terminologies
5 Steps of the Algorithm
6 Pseudocode
7 Illustration with Example
8 Visual Representation
9 Applications
Graham Scan Algorithm - Definition
● Graham Scan algorithm is a computational geometry technique used to determine the
Convex Hull of a set of points in a 2D plane.
● A Convex Hull is the smallest convex polygon that completely encloses all the given
points.
● The algorithm sorts the points based on their polar angles and processes them to
construct the convex hull efficiently.
Problem Statement
● Given a set of points P in a two-dimensional plane, determine a subset of points that:
○ Form the vertices of a convex polygon.
○ Enclose all the given points in P within the polygon.
Brief History
● The algorithm was introduced by “Ronald
Graham” in 1972.
● It is one of the earliest algorithms developed for
solving the Convex Hull problem efficiently.
● Graham’s algorithm is known for its simplicity
and practical efficiency, with a time complexity
(1935 - 2020)
of O(n log n), where ‘n’ is the number of points.
Terminologies
1. Convex Hull 2. Convex Polygon
Smallest boundary A polygon with all
that completely interior angles less
encloses a set of than 180° and no
points boundary segment
extending outside
3. Polar Angle 4. Orientation Test
Counterclockwise angle Checks the orientation
from the x-axis to a of three points to
point relative to a pivot ensure a left turn
Steps of the Algorithm
Select the point with the lowest y-coordinate; if tied,
Step 1: Find the Bottom-Most Point choose the lowest x-coordinate. This point is the
pivot.
Sort all other points relative to the pivot by their
Step 2: Sort Points by Polar Angle polar angle in counterclockwise order. If two points
have the same polar angle, keep the closer one.
Add the pivot and the point with the smallest polar
Step 3: Initialize the Convex Hull angle to the Convex Hull.
Steps of the Algorithm (Continued)
Iterate through the sorted points and perform an
orientation test:
Step 4: Scan and Construct ● Remove the second-to-last point if a right turn
(counterclockwise) is detected.
● Keep the point if a left turn (clockwise) is
detected.
Continue until all points are processed. The Convex
Step 5: Close the Hull Hull will contain the vertices in counterclockwise
order.
Steps of the Algorithm (Continued)
Select the point with the lowest y-coordinate; if tied,
Step 1: Find the Bottom-Most Point choose the lowest x-coordinate. This point is the
pivot.
Steps of the Algorithm (Continued)
Sort all other points relative to the pivot by their
Step 2: Sort Points by Polar Angle polar angle in counterclockwise order. If two points
have the same polar angle, keep the closer one.
Steps of the Algorithm (Continued)
Add the pivot and the point with the smallest polar
Step 3: Initialize the Convex Hull angle to the Convex Hull. (with Pivot & First Point)
Steps of the Algorithm (Continued)
Iterate through the sorted points and perform an
orientation test:
Step 4: Scan and Construct ● Remove the second-to-last point if a right turn
(counterclockwise) is detected.
● Keep the point if a left turn (clockwise) is
detected.
Steps of the Algorithm (Continued)
Continue until all points are processed. The Convex
Step 5: Close the Hull Hull will contain the vertices in counterclockwise
order.
Pseudocode (Descriptive)
1. Structure Definition
This part is essential to represent the points in the 2D plane.
struct Point {
int x, y;
};
2. Orientation Function
The orientation function is crucial for determining the turn direction (clockwise,
counterclockwise or collinear).
int orientation(Point p, Point q, Point r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // collinear
return (val > 0) ? 1 : 2; // clockwise or counterclockwise
}
Pseudocode (Continued)
3. Finding the Pivot (Lowest Point)
Selecting the bottom-most (or leftmost if tie) point is crucial to begin sorting.
int min_y = 0;
for (int i = 1; i < n; i++) {
if (points[i].y < points[min_y].y ||
(points[i].y == points[min_y].y && points[i].x < points[min_y].x)) {
min_y = i;
}
}
swap(points[0], points[min_y]);
Point pivot = points[0];
Pseudocode (Continued)
4. Sorting Points by Polar Angle
Sorting helps arrange the points based on their polar angles with respect to the pivot.
sort(points.begin() + 1, points.end(), [pivot](Point p1, Point p2)
{
return orientation(pivot, p1, p2) == 2;
});
Pseudocode (Continued)
5. Hull Construction (Main Algorithm Loop):
This loop constructs the convex hull by processing sorted points and removing unnecessary
ones.
vector<Point> hull;
hull.push_back(points[0]);
hull.push_back(points[1]);
hull.push_back(points[2]);
for (int i = 3; i < n; i++) {
while (hull.size() > 1 && orientation(hull[hull.size() - 2], hull.back(), points[i])
!= 2) {
hull.pop_back();
}
hull.push_back(points[i]);
}
return hull; //This line will provide the final convex hull result.
Illustration 01
(with Example)
Example
Input Points:
(0, 0), (1, 1), (2, 2), (2, 0), (2, 4), (3, 3), (3, 1)
1. Pivot: (0, 0)
2. Sorted Points: (0, 0), (2, 0), (3, 1), (2, 2), (3, 3), (2, 4), (1, 1)
3. Convex Hull Construction:
● Start with (0, 0) and (2, 0).
● Process each point; remove (3, 1) as it makes a right turn.
● Final Convex Hull: (0, 0), (2, 0), (3, 3), (2, 4), (1, 1)
Special Cases
1. Collinear Points:
If multiple points are collinear, include only the endpoints of the line
segment.
2. Duplicate Points:
Ignore duplicates during preprocessing.
Visual Representation (Convex Hull)
Visual Representation - 1
Visual Representation - 2
Visual Representation - 3
Visual Representation - 4
Visual Representation - 5
Visual Representation - 6
Visual Representation - 7
Visual Representation - 8
Visual Representation - 9
Visual Representation - 10
Visual Representation - 11
Visual Representation - 12
Visual Representation - 13
Visual Representation - 14
Visual Representation - 15
Visual Representation - 16
Visual Representation (Final View)
Applications
1. Geographic Mapping:
Determining the boundary of geographical regions.
2. Pattern Recognition:
Detecting outer boundaries of objects in images.
3. Game Development:
Collision detection for objects.
4. Robotics:
Pathfinding and obstacle avoidance.
5. Data Clustering:
Outlier detection by identifying boundary points.
Do you have any questions?
THANKS
CREDITS: This presentation template was created by Slidesgo,
including icons by Flaticon, and infographics & images by Freepik
