文件名称:convexhull_Grahamscan
介绍说明－－下载内容均来自于网络，请自行研究使用
Input : A set S of planar points
Output : A convex hull for S
Step 1: If S contains no more than five points, use exhaustive searching to find the convex hull and return.
Step 2: Find a median line perpendicular to the X-axis which divides S into SL and SR SL lies to the left of SR .
Step 3: Recursively construct convex hulls for SL and SR. Denote these convex hulls by Hull(SL) and Hull(SR) respectively.
Step 4: Apply the merging procedure to merge Hull(SL) and Hull(SR) together to form a convex hull.
Time complexity:
T(n) = 2T(n/2) + O(n)
= O(n log n)
-Input: A set S of planar pointsOutput: A convex hull for SStep 1: If S contains no more than five points, use exhaustive searching to find the convex hull and return.Step 2: Find a median line perpendicular to the X-axis which divides S into SL and SR SL lies to the left of SR. Step 3: Recursively construct convex hulls for SL and SR. Denote these convex hulls by Hull (SL) and Hull (SR) respectively.Step 4: Apply the merging procedure to merge Hull (SL) and Hull (SR) together to form a convex hull. Time complexity: T (n) = 2T (n/2)+ O (n) = O (n log n)
Output : A convex hull for S
Step 1: If S contains no more than five points, use exhaustive searching to find the convex hull and return.
Step 2: Find a median line perpendicular to the X-axis which divides S into SL and SR SL lies to the left of SR .
Step 3: Recursively construct convex hulls for SL and SR. Denote these convex hulls by Hull(SL) and Hull(SR) respectively.
Step 4: Apply the merging procedure to merge Hull(SL) and Hull(SR) together to form a convex hull.
Time complexity:
T(n) = 2T(n/2) + O(n)
= O(n log n)
-Input: A set S of planar pointsOutput: A convex hull for SStep 1: If S contains no more than five points, use exhaustive searching to find the convex hull and return.Step 2: Find a median line perpendicular to the X-axis which divides S into SL and SR SL lies to the left of SR. Step 3: Recursively construct convex hulls for SL and SR. Denote these convex hulls by Hull (SL) and Hull (SR) respectively.Step 4: Apply the merging procedure to merge Hull (SL) and Hull (SR) together to form a convex hull. Time complexity: T (n) = 2T (n/2)+ O (n) = O (n log n)
(系统自动生成,下载前可以参看下载内容)
下载文件列表
convex hull
...........\convex hull.cpp
...........\convex hull.cpp