Before reading this article, I recommend you to visit following two articles. Many concepts and codes are referred from there.
- Determining if two consecutive segments turn left or right
- Convex Hull Algorithms: Jarvis’s March (Introduction Part)
Introduction
In this article, I am going to talk about the linear time algorithm for merging two convex hulls. Given two convex hull as shown in the figure below.
The algorithm should produce the final merged convex hull as shown in the figure below.
Note: In order for this algorithm to work correctly, two convex hulls must be in the distinct left and right position and should not be overlapped. That means the x-coordinates of all the points of the left convex hull must be less than the x-coordinates of all the points of the right convex hull.
Algorithm
- Find the rightmost point $(p)$ of the left convex hull and leftmost $(q)$ for the right convex hull.
- Make two copies of $p$ and $q$. Now we have two $p$s and two $q$s.
- Raise the first copy of $p$ and $q$ to the make the upper tangent.
- Lower the second copy of $p$ and $q$ to make the lower tangent.
The details of steps 3, 4 are given in the next section with the help of an example.
Example
Suppose we want to merge the following two convex hulls.
First, we find the rightmost point ($p$) of the left convex hull ($q$) and leftmost point of the right convex hull and make two copies of the points $p$ and $q$.
Next, we raise the one copies of $pq$ (shown by a green line segment) to the upper tangent. This is how we do it. We keep the point $p$ fix and rotate the point $q$ in a clockwise direction as long as the sequence $p$, $q$ and the clockwise neighbor of $q$ makes the left turn (anti-clockwise turn). In this case, it makes a left turn so we move the point $q$ as shown in the figure below.
Again keep the $p$ fix in its previous position, we try to raise $q$. The sequence $p$, $q$ and the clockwise neighbor of $q$ constitutes a right turn and we stop. That means we can not raise $q$ further. Now, we keep the point $q$ fix and try to raise the point $p$ using the opposite logic. That is, we continue to raise $p$ as long as $q$, $p$ and anti-clockwise neighbor of $p$ makes a right turn. Since they make a right turn, we move $p$ as shown in the figure below.
Again, sequence $q$, $p$ and anti-clockwise neighbor of $p$ makes a right turn. Therefore, we move $p$.
Now, we try to raise $p$ but we can not do that because the sequence makes left turn. We stop here and repeat the process keeping $p$ fix. The sequence $p$, $q$ and clockwise neighbor of $q$ makes right turn. That means we can not raise $q$ further. Segment $pq$ is now the upper tangent.
We use the similar approach to lower another copies of $pq$ (shown by the red line). First keeping $p$ fix and lowering $q$ as long as the sequence $p$, $q$ and anti-clockwise neighbor of $q$ makes the right turn. Second we fix $q$ and lower $p$ as long as the sequence $q$, $p$ and clockwise neighbor of $p$ constitutes left turn. We stop when we cannot lower both $p$ and $q$ further.
In the above example, we lower the $q$ sine the sequence makes a right turn.
We can not lower $q$ further. We try to lower $p$ keeping $q$ fixed. Since the sequence makes a left turn, we lower it.
The sequence makes right turn. We stop and try to lower $q$ again keeping $p$ fixed. As the sequence makes a right turn, we lower $q$.
$pq$ is now the lower tangent as we cannot lower both of them any further. The algorithm terminates here.
Implementation
To implement the algorithm in linear time, a suitable data structure is needed. Here I am using a circular linked list where each point holds the references to the next nearest points in a clockwise and anti-clockwise direction. A node of the linked list can be implemented as below.
1 | class Point: |
Variable cw_next
holds the adjacent point in the clockwise direction and variable ccw_next
holds the adjacent point in the counter clockwise direction. The merge method is straight forward as described in the algorithm section.
1 | def merge(chull1, chull2): |
The following code can be tested with the test case given below.
1 | if __name__ == '__main__': |
Complexity
If you observe the code, you notice there is a nested while loop. You might be tempted to think this has a quadratic time complexity. But if you carefully observe, each point is covered at most twice. So the overall complexity is $O(n)$.
References
- Mount, D. M. (n.d.). CMSC 754 Computational Geometry. Lecture. Retrieved August 23, 2018, from https://www.cs.umd.edu/class/spring2012/cmsc754/Lects/cmsc754-lects.pdf