DEBUG提示错误:
First-chance Exception in ConvexHull.exe(NTDLL.DLL);0xC00000FD:Stack Overflow
点击ALT+7之后查看调用栈内容如下:
NTDLL! 77452c33()
NTDLL! 77455ae0()
NTDLL! 774c5f63()
NTDLL! 7748a40a()
NTDLL! 77455ae0()
_heap_alloc_base(unsigned int 64) line 200
_heap_alloc_dbg(unsigned int 16, int 1, const char * 0x00000000, int 0) line 378 + 9 bytes
_nh_malloc_dbg(unsigned int 16, int 1, int 1, const char * 0x00000000, int 0) line 248 + 21 bytes
_nh_malloc(unsigned int 16, int 1) line 197 + 19 bytes
operator new(unsigned int 16) line 24 + 11 bytes
std::_Allocate(int 1, dot * 0x00000000) line 30 + 12 bytes
std::allocator<dot>::allocate(unsigned int 1, const void * 0x00000000) line 59 + 40 bytes
std::vector<dot,std::allocator<dot> >::insert(dot * 0x00000000, unsigned int 1, const dot & {...}) line 158 + 14 bytes
std::vector<dot,std::allocator<dot> >::insert(dot * 0x00000000, const dot & {...}) line 154
std::vector<dot,std::allocator<dot> >::push_back(const dot & {...}) line 142 + 50 bytes
Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 63
Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes
Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes
Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes
Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes
Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes
Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes
......
使用的是VC6.0,编译器就是VC6.0默认的。
本人是个菜鸟,根据调用栈给出的内容完全不知道如何定位错误。
本人的程序是快速凸包算法(一个课后作业),程序在数据量比较少的情况下,点的个数在1000以下都运行正常,程序逻辑没有错误,当数据量增大到2000、3000的时候程序就提示出上述异常。
顺便说一下设置栈保留大小也已经试过了,将栈保留大小设置为16000000也无效。
以下是本人代码:
// ConvexHull.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "dot.h"
#include <iostream>
#include <vector>
#include "BruteForceCH.h"
#include "line.h"
#include <windows.h>
#include <time.h>
#include <fstream>
#include "comm.h"
#include "GrahamScan.h"
#include <stack>
#include "QuickTuBao.h"
#define random(x) (rand()%x)
using namespace std;
int main(int argc, char* argv[])
{
int n;
printf("input dots number:\n");
cin >> n;
//随机点生成算法
//*
vector<dot> vec;
srand((int)time(0));
for(int i=0;i<n;) {
dot d;
d.x = random(100) + (float)random(10)/(float)10;
d.y = random(100) + (float)random(10)/(float)10;
//d.x = random(10);
//d.y = random(10);
if(find(vec.begin(),vec.end(),d) != vec.end());
else {
vec.push_back(d);
i++;
}
}
//*/
//将生成的点写入文件,便于MATLAB读入
ofstream f1("C:\\MATLAB7\\work\\dot\\dots.txt");//打开文件用于写,若文件不存在就创建它
if(!f1)
return 0;//打开文件失败则结束运行
vector<dot>::iterator it;
for(it=vec.begin();it!=vec.end();it++) {
dot d = *it;
//cout<<d.x<<","<<d.y<<endl;
f1<<d.x<<" "<<d.y<<endl;
}
f1.close();//关闭文件
//记录运行时间
LARGE_INTEGER BegainTime ;
LARGE_INTEGER EndTime ;
LARGE_INTEGER Frequency ;
QueryPerformanceFrequency(&Frequency);
QueryPerformanceCounter(&BegainTime) ;
QuickTuBao(vec);
QueryPerformanceCounter(&EndTime);
//输出运行时间(单位:s)
cout << "运行时间(单位:s):" <<(double)( EndTime.QuadPart - BegainTime.QuadPart )/ Frequency.QuadPart <<endl;
//将结果写入文件
ofstream f2("C:\\MATLAB7\\work\\dot\\outdots.txt");//打开文件用于写,若文件不存在就创建它
if(!f2)
return 0;//打开文件失败则结束运行
//vector<dot>::iterator it;
for(it=vec.begin();it!=vec.end();it++) {
dot d = *it;
f2<<d.x<<" "<<d.y<<endl;
}
it=vec.begin();
dot d = *it;
f2<<d.x<<" "<<d.y<<endl;
f2.close();//关闭文件
system("pause") ;
return 0;
}
// QuickTuBao.cpp : 快速凸包算法的具体实现代码.
//
#include "stdafx.h"
#include "QuickTuBao.h"
//#pragma comment(linker,stack:16000000,16000000)
static vector<dot> outpts;//点集pts的凸包
//计算三角形的有向面积
double getArea(dot p1, dot p2, dot p3) {
return p1.x * p2.y + p3.x * p1.y + p2.x * p3.y - p3.x * p2.y - p2.x * p1.y - p1.x * p3.y;
}
//计算叉乘
float cross(dot pi, dot top, dot ntop)
{
return (pi.x-ntop.x)*(top.y-ntop.y) - (top.x-ntop.x)*(pi.y-ntop.y);
}
//递归
void Divide(dot d1, dot d2, vector<dot> ptsleft) {
vector<dot>::iterator it;
if(ptsleft.empty()) {
if(find(outpts.begin(),outpts.end(),d1) == outpts.end())
outpts.push_back(d1);
if(find(outpts.begin(),outpts.end(),d2) == outpts.end())
outpts.push_back(d2);
return;
}
//寻找pMax,面积最大的就是pMax
double area = 0, maxArea = 0;
dot pMax = d1;
for(it=ptsleft.begin();it!=ptsleft.end();it++) {
area = abs(getArea(d1, d2, *it));
if(area > maxArea) {
pMax = *it;
maxArea = area;
}
}
//找出位于(p1, pMax)直线左边的点集s1
//找出位于(pMax, p2)直线左边的点集s2
vector<dot> s1;
vector<dot> s2;
dot d;
for(it=ptsleft.begin();it!=ptsleft.end();it++) {
d = *it;
if(getArea(d1,pMax,d) > 0)
s1.push_back(d);//d属于左(上)
else if(getArea(pMax,d2,d) > 0)
s2.push_back(d);//d属于右(下)
}
/*
cout<<"------------s1---------"<<endl;
for(it=s1.begin();it!=s1.end();it++) {
cout<<*it<<endl;
}
cout<<"------------s2---------"<<endl;
for(it=s2.begin();it!=s2.end();it++) {
cout<<*it<<endl;
}
*/
//递归
Divide(d1, pMax, s1);//分别求解
Divide(pMax, d2, s2);//分别求解
}
void QuickTuBao(vector<dot> &vec) {
//按x轴对pts排序
sort(vec.begin(),vec.end(),lessCompare);
dot d1 = vec[0];//最左边的点
dot d2 = vec[vec.size()-1];//最右边的点,用直线p1p2将原凸包分成两个小凸包
cout<<d1<<endl;
cout<<d2<<endl;
//左右凸包点集
vector<dot> ptsleft;
vector<dot> ptsright;
//穷举所有的点,将点集按照直线d1d2分为左右两个凸包(上下凸包)
dot d;
vector<dot>::iterator it;
for(it=vec.begin();it!=vec.end();it++) {
d = *it;
double area = getArea(d1,d2,d);
if(area > 0)
ptsleft.push_back(d);//d属于左(上)
else if(area < 0)
ptsright.push_back(d);//d属于右(下)
}
Divide(d1, d2, ptsleft);//分别求解
Divide(d2, d1, ptsright);//分别求解
vec = outpts;
//去除共线的点
vector<dot> in;
int size = vec.size();
int j,k;
for(int i=0;i<size;i++) {
j=(i+1)%size;
k=(i+2)%size;
if(cross(vec[j],vec[k],vec[i]) == 0) {
//加入内点
in.push_back(vec[j]);
}
}
for(it=vec.begin();it!=vec.end();) {
d = *it;
if(find(in.begin(),in.end(),d) != in.end())
it = vec.erase(it);
else
it++;
}
}