今天春*_*天春天 1 algorithm geometry convex-hull convex computational-geometry
我需要找到一种算法,该算法根据给定的一组S大小点计算凸包n.我知道有刚好6点,从S形成的凸包.
S
n
计算这个的最佳和最有效的方法是什么？
我想要生成所有可能的点组合S(这将是n选择6点),这将采用O(n ^ 6),然后检查这是否是一个凸包,这将采取O(n)但导致一个非常总运行时间不好.肯定有更好的办法.任何提示？
Abh*_*sal 5
如果只有6个点位于凸包上,那么Jarvis March或Gift-wrapping算法将非常有效.它在O(nh)时间上运行,其中h是凸包上的点数.
O(nh)
h
归档时间：
9 年，2 月 前
查看次数：
164 次
最近记录：