filmov
tv
Convex Hull Algorithm - Graham Scan and Jarvis March tutorial
Показать описание
Given a set of points on a 2 dimensional plane, a Convex Hull is a geometric object, a polygon, that encloses all of those points. The vertices of this polygon maximize the area while minimizing the circumference.
Note that if some additional points were to be included, then the covering area is reduced while the circumference is increased. Likewise, if some of the vertices of the Convex Hull are omitted, then the resulting polygon won’t cover all of the points in the set.
The Convex Hull has a wide variety of applications, ranging from image recognition in robotics to determining animal’s home range in ethology. And in this tutorial we are going to look at how to calculate the Convex Hull using two different algorithms. The first one is called “Graham Scan” while the second is called “Jarvis March”, also known as "gift wrapping algorithm". Both of them are conceptually fairly simple, but there are a few tricky implementation pitfalls that I will point out.
Then it sorts the remaining points, ordering them by the angle that they make relative to the bottom most point and the horizontal. You can see that the angles would range from 0 to 180 degrees, given that the reference point is the bottom most one in the set.
Finally, the algorithm loops over those points in sorted order, effectively scanning in the counterclockwise direction. Each point is placed on a stack, but only if it makes a line with a counterclockwise turn relative to the previous 2 points on the stack. If that is not the case, then the previous point is popped off the stack. The algorithm continues popping points off of the stack until the resulting turn is counterclockwise.
Graham Scan Java source code:
Let’s talk about some of the implementation details that you’ll need to handle. First of all, to determine if it’s a clockwise turn or not, you could calculate the degrees of the angles using trigonometry and then compare them. But we don’t really care what the actual angles are. We just want to know if it’s a clockwise turn or not. To do just that and save a few CPU cycles in the process, we can make use of a cross product.
If you don’t recall, the cross product of two vectors V & W calculates the signed area of the parallelogram that is formed if you connect the two vectors like so. If V is on the right of W, then the cross product ends up positive. But if V is on the left of W, then it’s negative.
But then, instead of doing any kind of sorting, it just loops through all of the points again in a brute force way to find the point that makes the smallest counterclockwise angle in reference to the previous vertex. It simply repeats this iteration through all of the points until all of the vertices are determined and it gets back to the starting point.
Jarvis March source code in Java:
Looping through every point for each vertex may seem like a lot more inefficient, but the algorithm terminates as soon as it finds all of the vertices. This means that if the number of vertices is small, in particular, less than log of n, then it’ll perform better than the Graham Scan algorithm.
More formally, the running time of Jarvis March is O(n * h) where h is the number of vertices.
Of course, if the number of vertices is large, such as when all of the points are along the perimeter, then the running time turns for the ugly of O(n^2).
By the way, the function for finding the point with the smallest counterclockwise angle is exactly the same as the one used previously that makes use of the cross product. As a little bonus, dealing with collinear points is a little easier because here you just need to pick the point that is furthest away distance wise, without needing to worry about the slope of the line.
Timothy Chan’s paper for divide and conquer algorithm:
Written and narrated by Andre Violentyev
Note that if some additional points were to be included, then the covering area is reduced while the circumference is increased. Likewise, if some of the vertices of the Convex Hull are omitted, then the resulting polygon won’t cover all of the points in the set.
The Convex Hull has a wide variety of applications, ranging from image recognition in robotics to determining animal’s home range in ethology. And in this tutorial we are going to look at how to calculate the Convex Hull using two different algorithms. The first one is called “Graham Scan” while the second is called “Jarvis March”, also known as "gift wrapping algorithm". Both of them are conceptually fairly simple, but there are a few tricky implementation pitfalls that I will point out.
Then it sorts the remaining points, ordering them by the angle that they make relative to the bottom most point and the horizontal. You can see that the angles would range from 0 to 180 degrees, given that the reference point is the bottom most one in the set.
Finally, the algorithm loops over those points in sorted order, effectively scanning in the counterclockwise direction. Each point is placed on a stack, but only if it makes a line with a counterclockwise turn relative to the previous 2 points on the stack. If that is not the case, then the previous point is popped off the stack. The algorithm continues popping points off of the stack until the resulting turn is counterclockwise.
Graham Scan Java source code:
Let’s talk about some of the implementation details that you’ll need to handle. First of all, to determine if it’s a clockwise turn or not, you could calculate the degrees of the angles using trigonometry and then compare them. But we don’t really care what the actual angles are. We just want to know if it’s a clockwise turn or not. To do just that and save a few CPU cycles in the process, we can make use of a cross product.
If you don’t recall, the cross product of two vectors V & W calculates the signed area of the parallelogram that is formed if you connect the two vectors like so. If V is on the right of W, then the cross product ends up positive. But if V is on the left of W, then it’s negative.
But then, instead of doing any kind of sorting, it just loops through all of the points again in a brute force way to find the point that makes the smallest counterclockwise angle in reference to the previous vertex. It simply repeats this iteration through all of the points until all of the vertices are determined and it gets back to the starting point.
Jarvis March source code in Java:
Looping through every point for each vertex may seem like a lot more inefficient, but the algorithm terminates as soon as it finds all of the vertices. This means that if the number of vertices is small, in particular, less than log of n, then it’ll perform better than the Graham Scan algorithm.
More formally, the running time of Jarvis March is O(n * h) where h is the number of vertices.
Of course, if the number of vertices is large, such as when all of the points are along the perimeter, then the running time turns for the ugly of O(n^2).
By the way, the function for finding the point with the smallest counterclockwise angle is exactly the same as the one used previously that makes use of the cross product. As a little bonus, dealing with collinear points is a little easier because here you just need to pick the point that is furthest away distance wise, without needing to worry about the slope of the line.
Timothy Chan’s paper for divide and conquer algorithm:
Written and narrated by Andre Violentyev
0:07:24
Convex Hull Algorithm - Graham Scan and Jarvis March tutorial
0:07:00
Convex hulls: Graham scan - Inside code
0:03:06
Graham Scan Tutorial: Convex Hull of a Set of 2D Points
0:07:49
Convex Hulls -- Graham Scan
0:10:22
GRAHAM SCAN ALGORITHM | Convex Hull | (solved example)
0:10:13
Convex Hulls -- Graham Scan (modified)
0:00:15
Graham Scan Algorithm For Convex Hull
0:16:58
Convex Hull using Graham Scan Algorithm | Step-by-Step Solved Example | CodeCraft with Lucky
0:11:30
Graham Scan Convex Hull Algorithm Explained with Code
0:25:16
Graham Scan Algorithm Explaination with Example || How to draw Convex hull from set of points.
0:13:35
Convex Hull (Graham Scan)
0:14:10
Graham Scan: Background & Python Code
0:39:52
Convex Hull Algorithms
0:01:44
Graham Scan: find the convex hull of a point set
0:11:36
Convex Hull in English - theory and examples
0:11:18
Convex hulls: Jarvis march algorithm (gift-wrapping) - Inside code
0:00:08
Building a 2D Convex Hull - Graham Scan
0:00:54
Convex Hull Graham Scan Demonstration SU
0:00:37
Convex Hull: Graham Scan algorithm - Manim animation
0:10:02
Convex Hull: Starting with graph algorithms for interviews
![[manim] Convex hull](https://i.ytimg.com/vi/V8mnyGf6sU8/hqdefault.jpg)
0:00:22
[manim] Convex hull (Graham scan)
0:04:41
Convex Hull | Graham Scan Method | Explanation
0:03:34
Graham Scan convex hull algorithm (2 Solutions!!)
0:00:56
Convex Hull Graham Scan Demo SU
Комментарии