凸包问题-贪心法解决

问题描述

设计一个求解凸包问题的贪心算法,并测试算法正确性。

【注:凸包问题】给定平面上n个点,从中找出一个最小点集,使得该点集所组成的凸多边形包围所有的n个点。

问题分析

在二维空间中,凸包就是一个刚好包裹住一个集合中所有点的圈,围成这个圈的点是由集合中的点组成的.这里考虑的是贪心算法处理这个问题,贪心算法的要求是每次做出的选择都是当前最优的.这里我们用一个栈来存储每次所作出的选择,我们的贪心选择策略就是判断当前点与栈顶两个元素的位置关系来决定是否让这个点加入栈中.如果当前点在栈顶两个元素所围凸包得外面,则把栈顶得第一个元素去掉,将栈顶元素弹出栈并将当前点加入到栈中,反之则不用将当前点加入栈中,继续遍历下一个点,知道最终求出解.

算法设计

首先需要找到点集中纵坐标最小的点,我们这里暂且称之为原点(注:这里并非真正得原点),然后将点集按照各点与原点的夹角(也可以叫极角)从小到大(0°~180°)排序,显然纵坐标最小的点和夹角最小的点一定属于构成凸包的子集, 这里我们使用堆栈来存储每一步所作的选择,所以我们可以首先将这两个元素压入栈中.

在说明如何做出选择之前,我们要引入一个叉乘的概念,利用这个概念,我们可以得到两个向量的位置信息.对于二维向量的计算:

关于结果的讨论:

  1. 如果 > 0,在的顺时针方向
  2. 如果 < 0,在的逆时针方向
  3. 如果 = 0,在共线

由此我们可以通过两个向量的成绩来判断是否将当前点加入到堆栈中.不妨设当前点位Cur,栈顶元素为top1,栈顶的下一个元素为top2,这样的话

,

如果大于0,则将当前点加入到堆栈中,如果小于0,则弹出栈顶元素,将当前点加入到堆栈中.因为当前点位于栈顶两个元素所围凸包的外侧,当前点是一个更好的选择.按照这个策略遍历剩下的每一个点,这样栈中的元素就是最终构成图凸包的点.

算法实现

 

 

运行结果

输入:

10

1 -2

1 2

5 3

4 5

2 -4

6 -6

7 0

10-3

9 4

8 -1

凸包问题输入

输出:

C:\Users\28472\AppData\Local\Microsoft\Windows\INetCache\Content.Word\凸包问题的解.jpg

Leave a Reply

发表评论

邮箱地址不会被公开。 必填项已用*标注

本站所有文章均为原创,若需转载,请注明出处©twn29004 | 陕ICP备 20000896 网站备案号

总访问量:9605459    今日访问量:529    您是今天第:529 个访问者