python实现
思路：
- 首先，需要对顶点进行排序，顺时针或逆时针；
- 排序后，对每一条边，都判断其他点是否在边的同一侧。
1. 顶点排序
这里主要是用到向量积。对于xy平面上的两个向量，其向量积为(0, 0, z)向量，判断z的符号，通过右手系就可知道两个向量是顺时针还是逆时针了。
设有N个顶点，在其中随机选取一点A，我这里是用的序列中第一个点。以该点为起点，其他点为终点，得到N-1个向量。在这N-1个向量中，找到一个向量，其与其他向量的向量积的z都大于零（就是要得到逆时针的点序列。也可以是都小于零，这样得到的点序列就是顺时针了）。找到该向量之后，也就找到了相对A点第一个逆时针的点。将该向量删除，在剩下的向量中重复该过程，直到最后一个向量为止。
# 计算两个向量的向量积
# v1[0] --- x1, v1[1] --- y1
# v2[0] --- x2, v2[1] --- y2
def vec_prod(v1, v2):
Z = v1[0]*v2[1] - v1[1]*v2[0]
# 逆时针
if Z > 0:
return 1
# 顺时针
elif Z < 0:
return -1
# 三点共线
else:
return False
# 该函数对点序列按逆时针排序
# points[0] --- (x1, y1)
# points[1] --- (x2, y2)
# ...
def order_points(points):
first = points[0]
result = list()
result.append(first)
vectors = []
for point in points[1:]:
vectors.append((point[0] - first[0], point[1] - first[1]))
vec_num = len(vectors)
while vectors:
if len(vectors) == 1:
result.append((vectors[0][0]+first[0], vectors[0][1]+first[1]))
vectors.pop()
else:
for i, v in enumerate(vectors):
sign = list()
for t in vectors[0:i] + vectors[i+1:]:
sign.append(vec_prod(v, t))
sign = set(sign)
if False in sign:
return False
# 都是逆时针了
elif len(sign) == 1 and list(sign)[0] == 1:
result.append((v[0] + first[0], v[1] + first[1]))
vectors.pop(i)
break
# 意思是，当在所有向量上查找一次了，还没有找到一条与所有向量的向量积的z都大于0的那个向量，就返回False
# 这种情况只可能发生在非凸多边形中
# 在凸多边形中不可能有这种情况
# 因为在凸多边形中，起点相同的所有向量的夹角不会大于180度。
if i == vec_num - 1 and len(vectors) == vec_num:
return False
return result
>>> points = [[1, 1], [0, 1], [1, 0], [0, -1], [-1, 0]]
>>> print(order_points(points))
[[1, 1], (0, 1), (-1, 0), (0, -1), (1, 0)]
2. 判断其他点是否在边的同一侧
顶点排序之后，可对每条边，看看其他点是否在边的同一侧。使用函数距离来看看正负即可，也就是将点的坐标带入边的直线方程中，看看结果的正负，这是不用看是否位于线上，因为上面计算向量积是已经判断过了。
# line --- 边
# point --- 点
def fun_dist(line, point):
x1 = line[0][0]
x2 = line[1][0]
y1 = line[0][1]
y2 = line[1][1]
x = point[0]
y = point[1]
# 需要判断边是否垂直x或y轴
if x1 == x2:
tmp = x
elif y1 == y2:
tmp = y
else:
tmp = (y1 - y2) / (x1 - x2) * (x - x1) + y1 - y
return 1 if tmp > 0 else -1
# points必为排序后的点
# points[0] --- (x1, y1)
# points[1] --- (x2, y2)
# ...
def one_sied(points):
result = list()
# 遍历所有线
for i in range(len(points)-1):
line = points[i:i+2]
res = list()
# 对线之外的其他点进行判断
for p in points[:i] + points[i+2:]:
res.append(fun_dist(line, p))
res = set(res)
result.append(len(res))
result = set(result)
return True if len(result) == 1 else False
3. 合在一起
def convex(points):
# 返回的点是逆时针排序的
points = order_points(points)
if points == False:
return False
result = one_sied(points)
return result
>>> points = [[1, 1], [0, 1], [1, 0], [0, -1], [-1, 0]]
>>> result = convex(points)
>>> print(result)
True
可以使用plt.ginput()自己在图上获取点坐标，验证一下。
>>> x = np.linspace(-10, 10, 20)
>>> y = x * 0.5
>>> plt.plot(x,y)
>>> points = plt.ginput(8)
>>> points
[(-9.048387096774194, -5.547619047619044),
(-7.318548387096774, 6.595238095238102),
(-3.237903225806452, 11.952380952380963),
(2.6169354838709697, 10.642857142857153),
(7.71774193548387, 4.333333333333343),
(7.895161290322582, -6.4999999999999964),
(4.346774193548386, -15.071428571428568),
(-2.92741935483871, -13.999999999999996)]
>>> result = convex(points)
>>> print(result)
True
>>> plt.plot(x,y)
>>> points = plt.ginputs(8)
>>> points
[(-8.07258064516129, 2.428571428571434),
(-4.30241935483871, 15.523809523809533),
(2.7500000000000018, 14.333333333333343),
(7.495967741935486, 0.7619047619047663),
(3.459677419354838, -10.190476190476186),
(-4.391129032258064, -11.499999999999996),
(-4.258064516129032, -0.3095238095238031),
(6.254032258064518, 11.119047619047628)]
>>> result = convex(points)
>>> print(result)
False
