Codility每周一课：P99.5 PolygonConcav
0.png
P99.5 PolygonConcavityIndex
Check whether a given polygon in a 2D plane is convex; if not, return the index of a vertex that doesn't belong to the convex hull.
-
P99.5 凸包内点
判断一个多边形是否是凸多边形，不是的话，返回在凸包内部的点的索引
给出二维平面上点的集合A。这些点可组成一个多边形：每两个连续的点的连线构成多边形的边，并且有一个边是通过连接集合中的最后一个点和第一个点构成的。
二维平面上的一组点，其边界是一条直线，称为半平面。更准确地说，具有形式{(x, y): ax + by ≥ c}的直线都是半平面。半平面包含其边界。
当且仅当多边形的边界上的任意两点之间的线段没有超出多边形时，此多边形称为凸多边形。
例如，在笛卡尔直角坐标系中，由下面4个顶点：（-1，3）（3，1）（0，-1）（-2，1）构成的多边形是凸多边形
image
二维平面上有限点集的凸包是包含该集中所有点的最小凸多边形。
例如，笛卡尔直角坐标系中有7个点：(-1，3)，(1，2)，(1，1)，(3，1)，(0，-1)，(-2，1)，(-1，2)。包含上面七个点的凸包就是一个含有五个顶点的多边形。其顶点为：(-1，3)，(1，2)，(3，1)，(0，-1)，(-2，1)。
image
如果一个多边形是凹形的（也就是说，它不是凸形的），它至少有一个不在它的凸包边界上的顶点。现在就是找到这样一个顶点。 假设给出以下声明：
class Point2D(object):
x = 0
y = 0
编写函数：
def solution(A)
非空数组A由N个点组成，如果多边形是凸的，则返回−1。否则，函数应返回不在凸包边界上的任何一个点的索引。 注意：多边形的边可以共线（即多边形的某个内角可能为180度）。
要获得第K个点的坐标（其中0 ≤ K < N），请使用以下规则：
A[K].x获得X轴坐标，
A[K].y获得Y轴坐标。
例如，给定数组A：A[0].X=-1，A[0].Y=3，A[1].X=1，A[1].Y=2，A[2].X=3，A[2].Y=1，A[3].X=0，A[3].Y=-1，A[4].X=-2，A[4].Y=1，函数应返回−1。
但是，给定数组A：A[0].X=-1，A[0].Y=3，A[1].X=1，A[1].Y=2，A[2].X=1，A[2].Y=1，A[3].X=3，A[3].Y=1，A[4].X=0，A[4].Y=-1，A[5].X=-2，A[5].Y=1，A[6].X=-1，A[6].Y=2
image
函数应返回2或6。这些都是不在凸包边界上的点的索引。
假定：
- N是区间[3，10000]内的整数；
- 数组A中每个点的坐标都是[−1,000,000,000，1,000,000,000]内的整数；
- 多边形A的两条边只能在端点处相交；
- 数组A不包含重复的点。
- 解题思路
根据Graham Scan算法，在计算凸包的过程中，对于不是凸包上的点，返回其索引。如果遍历完点，没有返回，则说明是凸多边形，返回-1即可。
Graham Scan算法：
-
获得参考点T0：参考点就是所有点中，纵坐标最小的点，如果这样的点有多个，则把这些点中横坐标最小的点作为参考点。可知这个参考点肯定在凸包上。
-
点逆时针排序：
-
首先将参考点T0移动到原点P0，其他的点也按照上述规则移动到相应的点；
-
计算原点与其他的点构成的向量与x轴正向构成的夹角，按照夹角从小到大对点进行排序，夹角相同的，按照纵坐标的值降序排列；
-
上面的序列开头添加P0，后面添加P0，最终获得的点的序列就是按照逆时针排列的；
-
判断相邻的3个点是否是凸包上的点
假设相邻的三个点分别是P0，P1，P2:
image
- Python3代码
# -*- coding：utf-8 -*-
# &Author AnFany
# Lesson 99：Future training
# P 99.5 PolygonConcavityIndex
def solution(A):
"""
判断A中点组成的多边形是否是凸多边形，是的话返回-1，不是的话返回在凸包内部的任意一点的索引
利用Graham扫描算法得到凸包
:param A: 顶点的坐标
:return: -1或者凸包内部任意点的索引
"""
if len(A) == 3:
return -1
# 所有点的集合
point_set = []
for i in range(len(A)):
point_set.append([i, [A[i].x, A[i].y]])
#point_set.append([i, [A[i][0], A[i][1]]])
# 选出所有点中纵坐标最小的点，纵坐标相同的选择横坐标最小的点
point_set.sort(key=lambda s: [s[1][1], s[1][0]])
min_y_point = point_set[0]
# 将上面选择的点，转移到原点，计算其他所有点转移后和原点组成的向量与x轴正向的夹角
# 按照tan值从小到大排列，相同角度的按照y值的降序排列
more_than_zero = [] # tan值大于0的升序排列，相同值得按照y的降序排列
less_than_zero = [] # tan值小于0的升序排列，相同值得按照y的降序排列
zero = [] # tan值等于0的按照y值的降序排列
for p in point_set[1:]:
point = [p[1][0] - min_y_point[1][0], p[1][1] - min_y_point[1][1]]
if point[0] != 0:
tan = point[1] / point[0]
if tan >= 0:
more_than_zero.append([p[0], [tan, point[1]], point])
else:
less_than_zero.append([p[0], [tan, point[1]], point])
else:
zero.append([p[0], [0, point[1]], point])
more_than_zero.sort(key=lambda m: [m[1][0], -m[1][1]])
less_than_zero.sort(key=lambda m: [m[1][0], -m[1][1]])
zero.sort(key=lambda m: -m[1][1])
# 合并后，所有点是按着夹角逆时针排列的
trans_point_angle = more_than_zero + zero + less_than_zero
# 开始位置添加第一个元素
trans_point_angle.insert(0, [point_set[0][0], [0, 0], [0, 0]])
# 最后位置添加第一个元素
trans_point_angle.append(trans_point_angle[0])
# 把前2个点p0, p1放入栈中，把p1后面的点p2作为评判点，如果向量的叉积V_p0p2*V_p0p1<0,说明p2在p0p1的逆时针方向，是对的，如果为0，
# 说明三点共线，如果大于0，说明p2在p0p1的顺时针方向，说明P1点是凹进去的
current = [trans_point_angle[0], trans_point_angle[1]]
for index in trans_point_angle[2:]:
p0, p1, p2 = [current[0], current[1], index]
p0_p = p0[2]
p1_p = p1[2]
p2_p = p2[2]
p0p2 = p2_p[0] - p0_p[0], p2_p[1] - p0_p[1]
p0p1 = p1_p[0] - p0_p[0], p1_p[1] - p0_p[1]
product = p0p2[0] * p0p1[1] - p0p2[1] * p0p1[0]
if product < 0:
current = [current[1], index]
elif product == 0:
current = [current[0], index]
else:
return current[1][0]
return -1
- 结果
image
点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。
image
image
