1. 题目
题目
2. 解题思路
这道题还是比较难，需要一些背景知识（已整理到第3节中）。本题的解题思路其实是需要寻找一个点集的凸外壳，Jarvis’s 算法比较容易理解，我们从x轴最左边的点出发，寻找“最逆时针”的下一个点，直到回到最x轴左边的点，完成凸外壳的构建。
3. 背景知识
3.1 凸与非凸
凸与非凸
凸：集合中任意两点的连线在集合中
非凸：集合中存在两点，其连线不在集合中
3.2 三点方向（Orientation）
image.png
如图所示，三个有序点的方向可以分为顺时针、逆时针和共线三种。
如果（ABC）是共线，那么（CBA）也是共线，如果（ABC）是顺时针，那么（CBA）为逆时针。
3.3 方向计算
给定三点 A（x1, y1）, B (x2, y2), C(x3, y3), （ABC）方向可以通过线段斜率来计算。
image.png
线段AB的斜率 ：i = (y2 - y1) / (x2 - x1)
线段BC的斜率 : j = (y3 - y2) / (x3 - x3)
i < j （左图）：逆时针
i > j (右图）：顺时针
i = j : 共线
所以，方向 r 可以这么计算：
r = (y2 - y1)(x3 - x2) - (y3 - y2)(x2 - x1)
r > 0, 顺时针, 反之 r < 0 为逆时针，r = 0则为共线。
- 参考代码
'''
@auther: Jedi.L
@Date: Sat, May 4, 2019 12:04
@Email: xiangyangan@gmail.com
@Blog: www.tundrazone.com
'''
class Solution:
def orientation(self, a, b, c):
ori = (b[1] - a[1]) * (c[0] - b[0]) - (c[1] - b[1]) * (b[0] - a[0])
if ori == 0:
return 0 # colinear
res = 1 if ori > 0 else 2 # clock or counterclock wise
return res
def inbetween(self, a, b, c):
ori = (b[1] - a[1]) * (c[0] - b[0]) - (c[1] - b[1]) * (b[0] - a[0])
if ori == 0 and min(a[0], c[0]) <= b[0] and max(
a[0], c[0]) >= b[0] and min(a[1], c[1]) <= b[1] and max(
a[1], c[1]) >= b[1]:
return True # b in between a , c
def outerTrees(self, points):
points.sort(key=lambda x: x[0])
lengh = len(points)
# must more than 3 points
if lengh < 4:
return points
hull = []
a = 0
start = True
while a != 0 or start:
start = False
hull.append(points[a])
c = (a + 1) % lengh
for b in range(0, lengh):
if self.orientation(points[a], points[b], points[c]) == 2:
c = b
for b in range(0, lengh):
if b != a and b != c and self.inbetween(
points[a], points[b],
points[c]) and points[b] not in hull:
hull.append(points[b])
a = c
return hull
如何刷题 : Leetcode 题目的正确打开方式
我的GitHub : GitHub
其他题目答案：leetcode题目答案讲解汇总（Python版 持续更新）
其他好东西： MyBlog----苔原带
网友评论