Python 使用 Jarvis 算法或包装的凸包（Convex Hull using Jarvis’ Algorithm or Wrapping）
给定平面中的一组点，该集合的凸包是包含该集合所有点的最小凸多边形。
我们强烈建议您先阅读以下文章。
如何检查两个给定的线段是否相交？
c++ https://blog.csdn.net/hefeng_aspnet/article/details/141713655
java https://blog.csdn.net/hefeng_aspnet/article/details/141713762
python https://blog.csdn.net/hefeng_aspnet/article/details/141714389
C# https://blog.csdn.net/hefeng_aspnet/article/details/141714420
javascript https://blog.csdn.net/hefeng_aspnet/article/details/141714442
贾维斯算法的思想很简单，我们从最左边的点（或 x 坐标值最小的点）开始，然后继续沿逆时针方向包裹点。
最大的问题是，给定一个点 p 作为当前点，如何在输出中找到下一个点？
这里的想法是使用orientation()。
//c++ C++ 3 个有序点的方向（Orientation of 3 ordered points）-CSDN博客
//java Java 3 个有序点的方向（Orientation of 3 ordered points）-CSDN博客
//python Python 3 个有序点的方向（Orientation of 3 ordered points）_gh python 判断三点是否顺时针方向 如果是则反序-CSDN博客
//C# C# 3 个有序点的方向（Orientation of 3 ordered points）-CSDN博客
//Javascript javascript 3 个有序点的方向（Orientation of 3 ordered points）_threejs计算三个点的朝向-CSDN博客
下一个点被选为在逆时针方向上领先于所有其他点的点，即，如果对于任何其他点 r，我们有“orientation(p, q, r) = 逆时针”，则下一个点是 q。
算法：
步骤 1)将 p 初始化为最左边的点。
步骤 2)继续进行，直到不再回到第一个（或最左边的）点。2.1
)下一个点 q 是这样的点，即对于任何其他点 r，三元组 (p, q, r) 都是逆时针的。
为了找到这一点，我们只需将 q 初始化为下一个点，然后遍历所有点。
对于任意点 i，如果 i 更偏向逆时针，即 orientation(p, i, q) 是逆时针的，则我们将 q 更新为 i。
我们的 q 的最终值将是最逆时针的点。2.2
） next[p] = q（将 q 作为 p 的下一个存储在输出凸包中）。2.3
） p = q（将 p 设置为 q 以进行下一次迭代）。
以下是上述算法的实现:
# Python3 program to find convex hull of a set of points. Refer
# https://www.geeksforgeeks.org/orientation-3-ordered-points/
# for explanation of orientation()
# point class with x, y as point
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def Left_index(points):
'''
Finding the left most point
'''
minn = 0
for i in range(1,len(points)):
if points[i].x < points[minn].x:
minn = i
elif points[i].x == points[minn].x:
if points[i].y > points[minn].y:
minn = i
return minn
def orientation(p, q, r):
'''
To find orientation of ordered triplet (p, q, r).
The function returns following values
0 --> p, q and r are collinear
1 --> Clockwise
2 --> Counterclockwise
'''
val = (q.y - p.y) * (r.x - q.x) - \
(q.x - p.x) * (r.y - q.y)
if val == 0:
return 0
elif val > 0:
return 1
else:
return 2
def convexHull(points, n):
# There must be at least 3 points
if n < 3:
return
# Find the leftmost point
l = Left_index(points)
hull = []
'''
Start from leftmost point, keep moving counterclockwise
until reach the start point again. This loop runs O(h)
times where h is number of points in result or output.
'''
p = l
q = 0
while(True):
# Add current point to result
hull.append(p)
'''
Search for a point 'q' such that orientation(p, q,
x) is counterclockwise for all points 'x'. The idea
is to keep track of last visited most counterclock-
wise point in q. If any point 'i' is more counterclock-
wise than q, then update q.
'''
q = (p + 1) % n
for i in range(n):
# If i is more counterclockwise
# than current q, then update q
if(orientation(points[p],
points[i], points[q]) == 2):
q = i
'''
Now q is the most counterclockwise with respect to p
Set p as q for next iteration, so that q is added to
result 'hull'
'''
p = q
# While we don't come to first point
if(p == l):
break
# Print Result
for each in hull:
print(points[each].x, points[each].y)
# Driver Code
points = []
points.append(Point(0, 3))
points.append(Point(2, 2))
points.append(Point(1, 1))
points.append(Point(2, 1))
points.append(Point(3, 0))
points.append(Point(0, 0))
points.append(Point(3, 3))
convexHull(points, len(points))
# This code is contributed by
# Akarsh Somani, IIIT Kalyani
输出：
（0，3）
（0，0）
（3，0）
（3，3）
时间复杂度：O(m * n)，其中 n 是输入点数，m 是输出点数或船体点数 (m <= n)。对于船体上的每个点，我们都会检查所有其他点以确定下一个点。
最坏情况，时间复杂度：O(n 2 )。最坏情况发生在所有点都在船体上（m = n）。
辅助空间：O（n），因为已占用 n 个额外空间。
集合 2-凸包（Graham 扫描）
注意：当凸包中存在共线点时，上述代码可能会对不同顺序的输入产生不同的结果。例如，当输入 (0, 3), (0, 0), (0, 1), (3, 0), (3, 3) 时，它产生 (0, 3) (0, 0) (3, 0) (3, 3) 的输出；当输入 (0, 3), (0, 1), (0, 0), (3, 0), (3, 3) 时，输出为 (0, 3) (0, 1) (0, 0) (3, 0) (3, 3)。如果是共线，我们通常需要最远的下一个点，如果是共线点，我们可以通过添加一个 if 条件来获得所需的结果。请参考此修改后的代码。
资料来源：
http://www.dcs.gla.ac.uk/~pat/52233/slides/Hull1x1.pdf
原文地址：https://blog.csdn.net/hefeng_aspnet/article/details/141716444
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！