淘先锋技术网

首页 1 2 3 4 5 6 7

graham算法是先要对顶点进行预处理:
首先通过找到起始点LTL,然后其他点按照与起始点间极角的大小排序。
在这里插入图片描述
然后我们利用两个堆栈来对点集中的点进行操作,先是初始化:
在这里插入图片描述
之后我们会对T逐个元素的扫描看其是否为极点,每次扫描后都会让问题的规模线性减少,也就是必然有一个堆栈中的一个元素被剔除(判断为非极点),最终栈S中剩下的元素就是逆时针排放好的极点集合。

代码实现:

#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
#include <graphics.h>
#include <time.h>
#include <conio.h>
using namespace std;
#define POINTNUM 10
struct Point
{
    double x;    // x坐标
    double y;    // y坐标
    double z;    // z坐标(默认为0,如果需要三维点则给z赋值)

    Point(double a = 0, double b = 0, double c = 0) { x = a; y = b; z = c; } // 构造函数
};
Point sub(const Point& lhs, const Point& rhs)//向量减法
{
    Point res;

    res.x = lhs.x - rhs.x;
    res.y = lhs.y - rhs.y;
    res.z = lhs.z - rhs.z;

    return res;
}
Point div(const Point& p, double ratio)//向量除法
{
    Point res;
    
    res.x = p.x / ratio;
    res.y = p.y / ratio;
    res.z = p.z / ratio;

    return res;
}
double length(const Point& vec)//向量长度
{
    return (sqrt(pow(vec.x, 2) + pow(vec.y, 2) + pow(vec.z, 2)));
}
Point normalize(const Point& vec)//向量标准化
{
    Point res;
    res = div(vec, length(vec));//向量除以向量长度
    return res;
}
double dotMultiply(const Point& vec1, const Point& vec2)//向量点乘
{
    return(vec1.x * vec2.x + vec1.y * vec2.y + vec1.z * vec2.z);
}
Point multiply(const Point& vec1, const Point& vec2)//向量叉乘
{
    Point result;

    result.x = vec1.y * vec2.z - vec2.y * vec1.z;
    result.y = vec1.z * vec2.x - vec2.z * vec1.x;
    result.z = vec1.x * vec2.y - vec2.x * vec1.y;

    return result;
}
// 参数: vec1 矢量1  vec2 矢量2
double Cos(const Point& vec1, const Point& vec2)//向量余弦
{
    Point unit_vec1 = normalize(vec1);
    Point unit_vec2 = normalize(vec2);

    return dotMultiply(unit_vec1, unit_vec2);
}
//利用行列式的几何意义,通过判断正负来判断点在直线向量的左侧还是右侧
int Area2(Point a,Point b,Point c){
	return a.x*b.y-a.y*b.x+b.x*c.y-b.y*c.x+c.x*a.y-c.y*a.x;
}
bool ToLeft(Point a,Point b,Point c){
	return Area2(a,b,c)>0;
}
// 参数: points : 平面点集
//
vector<Point> findConvexGraham(const vector<Point>& points)
{
    vector<Point> result;

    // 点的数量必须大于三个
    if (points.size() < 3)
        return result;

    // 寻找最底部的点(LTL)
    int index = 0;
    for (int i = 0; i < points.size(); ++i)
    {
        if (points[i].y < points[index].y ||(points[i].y == points[index].y && points[i].x < points[index].x))
        {
            index = i;
        }
    }
    Point convex_p = points[index];

    // 计算每个点的极角
    map<double, int> cos_map;
    Point x_vec(1.0, 0.0);
    for (int i = 0; i < points.size(); ++i)
    {
        if (i != index)
        {
            double cos_value = Cos(sub(points[i], convex_p), x_vec);
            // 如果有多个点有相同的极角,则取最远的点
            if (cos_map.count(-cos_value) != 0)
            {
                if (length(points[i]) > length(points[cos_map[-cos_value]]))
                    cos_map[-cos_value] = i;
            }
            else
                cos_map[-cos_value] = i;
        }
    }
    
    // 保存结果的栈
    stack<int> result_stack;
    // 存入开始的两个点
    result_stack.push(index);
    result_stack.push(cos_map.begin()->second);

    for (auto iter = (++cos_map.begin()); iter != cos_map.end(); ++iter)
    {
        int first = result_stack.top();
        result_stack.pop();
        int second = result_stack.top();

        Point vec1 = sub(points[first], points[second]);
        Point vec2 = sub(points[iter->second], points[first]);
		//判断当前点是否在上一条极边的左侧还是右侧
        //if (ToLeft(points[second],points[first],points[iter->second]))
		if (multiply(vec1, vec2).z>0)//在左侧则保留上一极点
            result_stack.push(first);
        result_stack.push(iter->second);
    }

    // 将数据从栈中读取
    while (!result_stack.empty())
    {
        result.push_back(points[result_stack.top()]);
        result_stack.pop();
    }

    std::reverse(result.begin(), result.end());

    return result;
}
int main()
{
	vector<Point> points;
	initgraph(600,600);//创建一个600*600的窗口
	srand((unsigned)time(NULL));//产生随机种子
	for(int i=0;i<POINTNUM;i++){//随机生成10个点
		Point point;
		point.x=rand()%600;
		point.y=rand()%600;
		points.push_back(point);
		setlinecolor(RGB(255,0,0));
		setfillcolor(RGB(255,0,0));
		fillcircle(point.x,point.y,3);
	}
	vector<Point> result=findConvexGraham(points);
	//画出结果
	int len=result.size();
	for(int i=0;i<len-1;i++){
		setlinecolor(RGB(0,0,255));
		line(result[i].x,result[i].y,result[i+1].x,result[i+1].y);
	}
	setlinecolor(RGB(0,0,255));
	line(result[len-1].x,result[len-1].y,result[0].x,result[0].y);
	getch();
	closegraph();
	return 0;
}

然而这个实现还是有问题的。。。。:
在这里插入图片描述
不知道为什么,总是有一个点会莫名其妙被算入极点。希望有大神可以解答