0

我试图实现算法以获取给定点集的凸包，并使用 opencv 在 c++ 上使用以下代码可视化结果：

#include "opencv2/opencv.hpp"
#include "StdAfx.h"
#include <vector>
#include <cv.h>
#include <cv.hpp>
#include <cxcore.h>
#include <highgui.h>
#include <iostream>
#include <utility>
#include <math.h>
#include <time.h>  
#include <algorithm>
#include <stack>
using namespace std; 
using namespace cv;

vector<pair<int,int> > testPoints;
pair<int , int> pivot;
stack< pair<int , int> > hull;
const int frameSize=600;
const double PI = 3.141592653589793238462;
vector< pair <int,int> > points;
Mat img=Mat::zeros(frameSize,frameSize, CV_8UC1);

void drawFilledCircle( Mat img, Point center ,int radius)
{
 int thickness = -1;
 int lineType = 8;

 circle( img,
     center,
     radius,
     255,
     thickness,
     lineType );
}

void drawLine( Mat img, Point start, Point end ,int shade,int thickness)
{
  int lineType = 8;
  shade=shade%256;
  line( img,
    start,
    end,
    shade,
    thickness,
    lineType );
}

float getAngle(pair<int,int> p1 , pair<int,int>p2){
     return atan2(static_cast<double>(p1.second-p2.second) , static_cast<double>       (p1.first-p2.first))*180/PI;
}

bool compareFunction(pair<int,int> p1 , pair<int,int> p2){
    return ( getAngle(p1,pivot)>getAngle(p2,pivot) );
}

void printPoints(vector< pair<int,int> > points){
    for(int i=0;i<points.size();i++)
            cout<<"( "<<(points[i].first-frameSize/2)<<" , "<<(points[i].second-    frameSize/2)<<" )  "<<getAngle(points[i],pivot)<<endl;
     cout<<endl;
}

void mouseEvent(int evt, int x, int y, int flags, void* param){
    if(evt==CV_EVENT_LBUTTONDOWN){
        cout<<"Click at : ( "<<(x-frameSize/2)<<" , "<<(y-frameSize/2)<<" ) , Polar Angle: "<<getAngle(make_pair(x,y),pivot)<<endl;
    }
}

void setUpFrame(){
    int n;
    cout<<"Enter number of points: ";
    cin>>n;

    for(int i=0;i<n;i++)
        points.push_back(make_pair((rand()%static_cast<int>(frameSize*0.75)     +frameSize*0.125) , (rand()%static_cast<int>(frameSize*0.75)  +frameSize*0.125)));

    for(int i=0;i<n;i++)
        drawFilledCircle( img, Point(points[i].first, points[i].second) ,2);
    drawLine(img , Point(frameSize/2,0) , Point(frameSize/2,frameSize),100,1);
    drawLine(img , Point(0,frameSize/2) , Point(frameSize,frameSize/2),100,1);

    cout<<"Settingup frame...\nPress enter to continue."<<endl;
}

void setPivot(){
    int max=-2*frameSize , index=0;
    for(int i=0;i<points.size();i++){
        if(points[i].second>max){
            max=points[i].second;
            index=i;
        }
    }
    pivot=points[index];
    points.erase(points.begin()+index);

    drawFilledCircle( img, Point(pivot.first, pivot.second) ,6);
    cout<<"Pivot chosen at: ( "<<(pivot.first-frameSize/2)<<" , "<<(pivot.second-    frameSize/2)<<" )\nPress enter to continue."<<endl;
}

void sortPoints(){
    cout<<"Sorting points on the basis of polar angles."<<endl;
    std::sort(points.begin(),points.end(),compareFunction);
}

void createHull(){
    pair<int,int> previous,next;
    for(int i=0;i<points.size();i++){
        previous= (hull.size()==0) ? pivot : hull.top();
        next= (i==points.size()-1) ? pivot : points[i+1];

        int x1=(previous.first-points[i].first);
        int x2=(points[i].first-next.first);
        int y1=(previous.second-points[i].second);
        int y2=(points[i].second-next.second);

        if( x1*y2-x2*y1 <0 ) 
                hull.push(points[i]);
        drawFilledCircle( img, Point(hull.top().first, hull.top().second) ,4);
    }

    int size=hull.size();
    pair<int,int> pt;

 drawLine(img,Point(pivot.first,pivot.second),Point(hull.top().first,hull.top().second),200,1);
    for(int i=1;i<size;i++){
        pt=hull.top();
        hull.pop();
        drawLine(img,Point(pt.first,pt.second),Point(hull.top().first,hull.top().second),200,1);
    }
    drawLine(img,Point(pivot.first,pivot.second),Point(hull.top().first,hull.top().second),200,    1);
}

int main(int, char**)
{
    srand (time(NULL));
    namedWindow("Output",1);
    cvSetMouseCallback("Output", mouseEvent, 0);

    setUpFrame();
    setPivot();
    sortPoints();
    createHull();

    imshow("Output", img);
    waitKey(0);
    return 0;
}

我知道有内置库可以做到这一点，但我想自己实现算法。当点数较少时，事情似乎运作良好，例如 30 个点，但随着点数的增加，我开始得到一个奇怪的形状（如下面所示的 200 和 1000 点）。该算法似乎在与枢轴点（由具有最大半径的实心圆表示）对角的那些点中选择了额外的点（不应包含在船体中的点）。谁能帮我弄清楚我哪里出错了或者建议我可以在代码中进行一些修改？在此处输入图像描述 在此处输入图像描述

在此处输入图像描述

4

1 回答 1

1

看起来您想实现 Graham 的扫描，但没有成功。

Graham 的扫描结构如下：

Find the bottom-most point, then sort the points clockwise around it.
Set hull to the first two points.
For each point, say p, from the third onward:
  While you make a left turn from the last edge of hull to the line from hull.back to p:
    popback(hull);
  push(hull, p)

注意初始化的不同——格雷厄姆的扫描从边缘开始，而你从没有点开始。

还要注意循环内部的差异 --- 您使用左转标准作为某种拒绝测试，涉及来自 的另一个点points，而 Graham 的扫描使用新点来删除不再是船体一部分的点。

于 2013-05-22T13:42:33.653 回答