Table of Content
1. 题目
2. 解题思路
这道题还是比较难，需要一些背景知识（已整理到第3节中）。本题的解题思路其实是需要寻找一个点集的凸外壳，Jarvis’s 算法比较容易理解，我们从x轴最左边的点出发，寻找“最逆时针”的下一个点，直到回到最x轴左边的点，完成凸外壳的构建。
3. 背景知识
3.1 凸与非凸
凸：集合中任意两点的连线在集合中
非凸：集合中存在两点，其连线不在集合中
3.2 三点方向（Orientation）
如图所示，三个有序点的方向可以分为顺时针、逆时针和共线三种。
如果（ABC）是共线，那么（CBA）也是共线，如果（ABC）是顺时针，那么（CBA）为逆时针。
3.3 方向计算
给定三点 A（x1, y1）, B (x2, y2), C(x3, y3), （ABC）方向可以通过线段斜率来计算。
线段AB的斜率 ：i = (y2 - y1) / (x2 - x1)
线段BC的斜率 : j = (y3 - y2) / (x3 - x3)
i < j （左图）：逆时针
i > j (右图）：顺时针
i = j : 共线
所以，方向 r 可以这么计算：
|
1 |
r = (y2 - y1)(x3 - x2) - (y3 - y2)(x2 - x1) |
r > 0, 顺时针, 反之 r < 0 为逆时针，r = 0则为共线。
- 参考代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
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 |
