A convex hull is the smallest area enclosing a particular set of points. If the angle between any two of a polygon’s adjacent edges is consistently less than 1800, the polygon is said to be convex. If not, it is referred to as a concave polygon. Self-intersecting polygons are complex polygons.
The convex polygon P that contains all of the supplied points is the convex Hull of the collection of points Q. The convex hull issue is the one that involves determining the smallest polygon P such that every point in a set Q is either within P or on its edge. The following figure shows the convex Hull of the relevant spots. A point that is shared by two adjacent edges is referred to as a polygon’s vertex.
Brute Force Approach
Constructing a line connecting two points and determining whether or not all of the points are on the same side is the brute force approach for identifying convex Hull. These n(n – 1) /2 lines each have n points, and the remaining n – 2 points are used to compare each line to see if they fall on the same side. Therefore, the brute force method requires O(n3) processing time. Can divide and conquer be used more successfully?
- The approach of “Divide and Conquer.”
- The convex hull problem can be solved in a number of ways. We’ll go over a divide-and-conquer strategy to solve it in this article.
- By their X coordinates, order each point. A tie is broken by placing points in order of their Y coordinate.
- Choose two polar opposites. A and B, where A stands for the furthest left point and B for the outermost right point. The vertices of the convex Hull would be A and B. The solution set should include lines AB and BA.
- Locate point C that is the furthest distance from line AB.
- Determine the convex Hull of each point on the right and left sides of the line AC. Line AB from the initial solution set should be removed and replaced.
Complexity analysis
Sorting the points in increasing order of their X coordinates is a stage in the pre-processing process. Sorting takes only O(log2 n) time to complete. It takes O(1) time to find the two farthest points from the sorted list. Points are split into two halves. S1 and S2 join A and B in O(1) time. S1 and S2 typically contain half of the points. Therefore, it takes T(n/2) for each to recursively compute the convex Hull of A and B. Finding the orthogonally furthest point allows for the merging of two convex hulls in linear time O(n). Following point pre-processing, the total running time is provided by,
T(n) equals 2T(n/2) + O(n) + O(1) + n (1)
T(n/2) = 2T(n/4) + n/2 is the solution to the original recurrence for n/2.
Equation (1) is changed to T(n) = 2[2T(n/4) + n/2] by substituting this. + n s= 22 T(n/22) + 2n s. s. s.
T(n) = 2k after k substitutions. T(n/2k) + k.n … (2)
Let’s assume that k increases to log2n by dividing by the height of the binary tree created by the division of the array: k = log2n n = 2k
Example of Convex Hull
Problem: Using the divide and conquer method, find the convex Hull for a given set of points.
The solution is equal to Solution – AC – AD, DC = AD, DC, CB, BA.
Regions X0, X1, and X2 should be labeled as in the above figure.
Call FindHull (X1, A, D) and FindHull repeatedly (X2, D, C)
However, since sets X1 and X2 are empty, the algorithm returns.
Step 4 : FindHull(X2, C, B) (X2, C, B)
Find the orthogonal distance between point E and line CB.
Solution = solution – “CB,” “CE,” “EB,” “AD,” “DC,” “CE,” “EB,” and “BA,”
Label the three sections in Fig. P.3.6.1 as X0, X1, and X2 (d).
Call FindHull (X1, C, E) and FindHull repeatedly (X2, E, B).
However, since sets X1 and X2 are empty, the algorithm returns. We will now examine the S2 points on the right side of the line BA.
Step 5: Use FindHull(S2, B, A) to determine where to point F is orthogonally closest to line BA.
Region names X0, Collision avoidance: If the convex Hull of an automobile prevents collisions with obstacles, then the vehicle itself accomplishes the same. A convex vehicle is often used to build paths since it makes it much simpler to calculate collision-free routes.
The convex Hull of the polygon is determined in the first phase of minimum rectangle methods because the lowest area rectangle that encloses the polygon has at least one side flush with the Hull. The 3D-convex Hull also plays an important role in determining the smallest three-dimensional box that contains an object.
As seen in the last illustration, X1 and X2.
Call FindHull (X1, F, G) and FindHull repeatedly (X2, G, A).
But since sets X1 and X2 are empty, the procedure succeeds. And there are no longer any recursive calls. Thus, a polygon with edges.
Applications of Convex Hull
- Avoiding collisions with objects is the same for the car as it is for its convex Hull. A convex hull is widely used to build paths because it makes it much simpler to calculate collision-free routes.
- Convex hulls assist in determining the smallest box necessary to contain an object. The object’s box size should be determined. The 3D-convex Hull also plays an important role in determining the smallest three-dimensional box that contains an object.
- Analyzing an object’s shape is made easier by the convex Hull of the object.
- More realistic applications of convex Hull include pattern recognition, image processing, statistics, geographic information systems, game theory, phase diagram generation, and static code analysis via abstract interpretation.
If you want to learn more about the convex hull and other algorithms in DSA, consider joining the data structure course right away.