平面上 $N$ 个点所组成凸包的算法.
凸包(convex hull)问题是找出一个将平面上的点集围住的(面积)最小的凸多边形的问题.
试给出寻找凸包的一个 $O(N\log N)$ 算法.
References:
Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Third Edition.
张怀勇 等译. Ex. 10.51, P.349
凸包(convex hull)问题是找出一个将平面上的点集围住的(面积)最小的凸多边形的问题.
试给出寻找凸包的一个 $O(N\log N)$ 算法.
References:
Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Third Edition.
张怀勇 等译. Ex. 10.51, P.349