2017-10-01
Sort points on x-coordinate's value
dividing the points into two sets recursiveliy(Base case: three points in the set)
Make convex hull of the three points, merge the convex hull based on below:
We can merge two convex hulls by finding upper and lower common tangents
Start with the rightmost point of the left hull and the leftmost point of the right hull
The upper common tangent can be found by:
-scanning the left hull in a anti-clockwise direction untill slope decreases and untill its a tangent to left hull. -scanning the right hull in clockwise direction untill its a tangent to right hull.The lower common tangent can be found similarly by moving in opposite direction. Merge the two hulls by removing the internal edges joining the tangent vertices.
Sort points on x-coordinate's value
dividing the points into two sets recursiveliy(Base case: three points in the set)
Make convex hull of the three points, merge the convex hull based on below:
We can merge two convex hulls by finding upper and lower common tangents
Start with the rightmost point of the left hull and the leftmost point of the right hull
The upper common tangent can be found by:
-scanning the left hull in a anti-clockwise direction untill slope decreases and untill its a tangent to left hull.
-scanning the right hull in clockwise direction untill its a tangent to right hull.
The lower common tangent can be found similarly by moving in opposite direction.
Merge the two hulls by removing the internal edges joining the tangent vertices.
(c) 2024 Yioop - PHP Search Engine