با سلام
دوستان من اطلاعاتی راجب الگوریتم convex hull یا تریقه نوشتن این برنامه به زبان C++می خواستم. ممنون میشم اگر من رو راهنمایی کنید.
با سلام
دوستان من اطلاعاتی راجب الگوریتم convex hull یا تریقه نوشتن این برنامه به زبان C++می خواستم. ممنون میشم اگر من رو راهنمایی کنید.
منم همین مشکلو دارم . ولی الن مراحل ساخت برنامش رو دارم تموم می کنم .نوشته شده توسط hamid-gh
تموم که شد ، یه آموزش ت وسایت میذارم . چون خودم تو سایت گشتم ، پیدا نکردم .
مغزم متلشی شد . این چه برنامه ایه لامصب . بالاخره تموم شد .
البته بره اینکه مطمئن بشم توابع درست کار می کنن ، الآن فقط برنامه رو میذارم تا دوستانی که پیگیر هستن ، امتحانش کنن و اگه تو تمام مراحل و با نقاط متفاوت به جواب درست رسیدین ، اعلام کنید تا لینک آموزششو براتون بذارم ( البته لینکی که بره آموزش ، خودم دارم آماده می کنم . هنوز تکمیل نشده)
تو نوشتن برنامه از توابع پایه ی OpenGL بهره گرفته شده . اگه یک موقع برنامه به درستی اجرا نشد ، احتمالا به دلیل کمبود فایل های dll مربوط به OpenGL هست . که بره نصبشون تو تاپیک های برنامه نویس ، دو سه جا آموزشش اومده .
آخرین ویرایش به وسیله mahak006 : جمعه 21 مهر 1391 در 21:16 عصر
با سلام
من این فایلو دانلود کردم
کلا اجرا نشد
و سورس کد هم نداشت !!!!!
نقل قول: convex hull
سورس کد رو که نمی ذارن . این فایل به خاطر اینکه از OpenGL توش استفاده شده ، بره سیتم هایی که dll های OpenGL رو ندارن ، مشکل داشت . در ضمن یه اشتباه توش پیدا کردم که تو فایل تصحیحش کردم . فقط وقت نکردم که فایل جدید رو بذارم .
اینم از فایل جدید :
استقبال زیاد باشه ، آموزش پوش محدب رو تو تاپیک جدیدی براتون می نویسم . ( البته اگه کسی پیشدستی نکنه)
file.rar
سورس کد رو که نمی ذارن . این فایل به خاطر اینکه از OpenGL توش استفاده شده ، بره سیتم هایی که dll های OpenGL رو ندارن ، مشکل داشت . در ضمن یه اشتباه توش پیدا کردم که تو فایل تصحیحش کردم . فقط وقت نکردم که فایل جدید رو بذارم .
اینم از فایل جدید :
استقبال زیاد باشه ، آموزش پوش محدب رو تو تاپیک جدیدی براتون می نویسم . ( البته اگه کسی پیشدستی نکنه
file.rar
مرسی بابت فایل
اما من سورس کد رو چطوری میتونم داشته باشم؟؟؟
یه سوال این با چه الگوریتمی کار میکنه ؟؟
من دنبال الگوریتم گراهام اسکن هستم
ممنون میشم کمکم کنی
با تشکر
با الگوریتم گراهام کار می کنه .
یه کمک سریع که میشه کرد اینه ( که البته شاید بشه بهینه تر از این برنامه رو نوشت . اما من بهترینش رو اینطوری دیدم ) :
1 : تو الگوریتم اصلی گراهام ( تو پست های قبلی ، میتونی لینک ویکیپدیا رو ببینی که توش سودوکد رو نوشته ) اینطوری توضیح داده شده که اول باید پایین ترین نقطه ( نقطه مینیمم ) رو پیدا کنی . البته ممکنه که تو نقطه های ورودی ، چند نقطه دارای y یکسان باشن . یعنی مینیمم باشن . ما اینجا طبق الگوریتم ، فقط یه نقطه p0 میخوایم و برامون فرقی نمی کنه که کدوم یکی از اون نقاط مینیمم انتخاب بشن .
2 : بعد از پیدا کردن p0 باید بقیه ی نقاط رو بر حسب p0 به صورت راست گرد بچینیم . اینجا نیاز داریم که ابتدا نقاط رو تو صفحه مختصات انتقال بدیم . به طوری که نقطه p0 مرکز مختصاتیمون باشه . توجه کنید که این مختصات جدید ، باید طوری ذخیره بشن که امکان دسترسی به مختصات قدیمی باشه . ( بره رسم پوش محدب به مختصات اصلی نقاط نیاز داریم که نباید از بین برن )
new_x = old_x - p0_x;
new_y = old_y - po_y;
3 : با استفاده از مختصات جدید و 2 فرمول زیر می تونیم زاویه و فاصله ی هر نقطه رو نسبت به مرکز مختصات ( که بعد از انتقال ، همون p0 هستش ) به دست بیاریم .
#include<math.h>
r = sqrt(x*x+y*y);
teta = atan2(y,x);
اینجا به این سؤال بر میخوریم که آیا راهی هست که بشه مراحل 2 و 3 ( انتقال نقاط دکارتی و سپس پیدا کردن مختصات قطبی ) به طوری یکجا انجام بشن ( ادغام بشن ) تا سرعت برنامه بالاتر بره ؟
بله حتما راهی هستش . خودمم روش دارم فکر می کنم . ولی باید تسلط به مسائل ریاضی و اعداد قطبی داشته باشیم که البته من اینطور نیستم و یه کم برام سخته
4 : حالا بر اساس زاویه قطبی teta که در مرحله قبل حساب کردیم ، نقاط رو از p0 به بعد ، مرتب می کنیم ( p0 نقطه ی اول لیست مرتب شده باید باشه . ) سؤال اینجاست که r از مرحله قبل به چه دردی میخوره ؟
در مرتب کردن ، هر جا که دو teta با هم برابر شدند ، باید ( باید ) اون نقطه ای که r کوچک تری داره ، جلوتر قرار بگیره . اینجا r خیلی اهمیت داره . چون اگه نباشه مشکل برنامه می شه مشکل فایل اول من
این هم دقت کنید که لیست نقاط قدیمی رو که داریم هم باید مرتب کنیم ( اگه مختصات انتقالیشون ، جا به جا شد ، نقطه اصلی هم باید تو لیست مربوط به خودش جا به جا بشه .
5 : حالا که لیست مرتب شده ای از نقاط رو داریم ، میریم به سمت قسمت اصلی الگوریتم گراهام ، یعنی پیدا کردن نقاط پوش محدب .
اول نقطه ی اولی لیست مرتب شده ( همون p0 ) و نقطه دومی ( p1 ) رو به ترتیب وارد پشته می کنیم .
6 : حالا تا پایان نقطه ها ، هر نقطه رو از لیست برمیداریم و چک می کنیم که سمت راست خط گذرای از دو نقطه ی اول روی پشته هست یا نه . اگه باشه ، یعنی نقطه ی اولی پشته ، نمی تونه جزء نقاط پوش محدب انتخاب بشه . پس باید از روی پشته این نقطه رو pop کنیم . همین ترتیب رو تا جایی پیش می بریم که نقطه ی جدید ، سمت راست خط واصل دو نقطه ی روی پشته نباشه ( روی خط باشه یا سمت چپ خط ) . اینجا نقطه ی جدید رو وارد پشته می کنیم .
7 : در پایان ، نقاط مانده در پشته ، همان نقاط پوش محدب هستند که به ترتیب باید به هم وصل شوند و سپس نقطه ی پایانی به نقطه ی ابتدایی وصل بشه .
اگه جایی از تعاریف ، ابهامی یا اشکالی وجود داره ، حتما بگید .
راستی من برنامه رو به دو صورت ( با آرایه و با لیست پیوندی ) پیاده سازی کردم . هر دو روش تو توضیحات بالا تقریبا یکسان هیتند . فقط ریزه کاری ها فرق می کنه . مخصوصا تو مرحله ی 2و3
تو هر زمینه ای از دو نوع که بخواین ، می تونم کمکتون کنم. ولی به خاطر قوانین ، سورس کد رو نمیتونم براتون بذارم .
دوست عزیز من یه سوال داشتم
در شماره 6 ما چطوری بفهیمیم که نقطه ی جدید ، سمت راست خط واصل دو نقطه ی روی پشته هست یا نه؟
فرموله خواصی داره؟
این یه مقدار وقت میبره . تسلط کامل به مباحث رسم خط با داشتن شیب خط و به دست آوردن شیب خط می خواد .
m=(y1-y0)/(x1-x0);
y=m(x-x0)+y0;
خط اول شیب خط رو محاسبه می کنه که به ترتیب باید x , y دو نقطه ی روی پشته رو براش قرار بدی . خط دوم معادله ی خط هست که با استفاده از اون و با توجه به اینکه خطت کجا رسم می شه ( همینجاش بحث مفصلی داره ) x نقطه جدید رو داخل معادله میذاری و y که از معادله به دست میاد رو با y نقطه جدید مقایسه می کنی و با توجه به محل قرار گرفتن خط ، مشخص می شه که نقطه ، سمت راست خط هست یا نه .
*** منظور از محل قرار گیری خط اینه که بره تشکیل پوش محدب ، تا کجا پیش رفتی . مثلا اگه خطت شیبش مثبت باشه ، این خط می تونه دو جا قرار بگیره . یکی جنوب شرقی پوش محدب ( تقریبا ) و یکی شمال غربی که شرط سمت راست بودن نقطه ی جدید بره جنوب شرقی ، کاملا بر عکس شمال غربی هست . حالا با استفاده از تفاضل x ها یا y ها می شه فهمید که شیب خط ، مربوط به کدوم قسمته .( یه بار با نقاط مختلف امتحان کنید ، کاملا متوجه می شید منظورم چیه ) . به این موضوع هم توجه کنید که بره شیب های صفر و بی نهایت هم این موضوع صدق می کنه . اینم بدونید که بهتره قبل از به دست آوردن شیب خط ، چک کنید که شیب خط اگه بی نهایت میشه ، اونو محاسبه نکنه . چون جواب بی نهایت تو مجموعه مقادیر متغیر ها ، قابل شناسایی نیست و حتی اگر هم قابل شناسایی باشه ، شما نمی تونید تو شرطتون بگید که اگر m = بی نهایت !!!
باز هم سؤالاتتون رو بگید و اگه جایی به مشکل برخوردید بگید .
دوستان من تونستم این الگوریتم رو پیاده سازی کنم.
بهتون پیشنخاد میکنم برای راحتی کار ابتدا مقدار cos هر نقطه رو با نقطه p(نقطه ای که کمترین yرا داره)محاسبه کنید و بعد مقدار cosنقطه ها رو از کوچک به بزرگ مرتب کنید و همزمان مقادیر متنازر xوyآنها روه مرتب کنیدو در ادامه فقط کافیه نوع کردش 3نقطه در هر لحظه را حساب کنید.برای ادامه کار اول نقطهp(نقطه ای که کمترین y را دارد) را push کنید ودر بعد از مقایسه 3نقطه که در صورت محدب بودن شما نقطه دوم را push می کنید .
push(p);
for(i=0;i<9;i++)
{
if((tabe tashkhis gardesh(sx[topx],x[i+1],x[i+2],sy[topy],y[i+1],y[i+2]))==true)
{
push(x[i+1],y[i+1]);
}
//p=(x,y)نقطه ای که کمترین yرا دارد
//در نقطه شروعsx[topx]&sy[topy]==p
//x[i+1],x[i+2],y[i+1],y[i+2]:نقاط بعدی که دز آرایه های که مقادیر x&yرا در خودشان نگهداری می کنند }
sx[]:پشته مربوط به مقادیر x
sy[]:پشته مربوط به مقدارy
امید وارم بدردتون بخوره اگر سوالی داشتید من در خدمتم...
به فرض 6 نقطه در نظر میگیرم
a1(2,4) a2(3,7) a3(4,5) a4(-5,-5) a5 ( -3,2) a6(2,-2) l پس نقطه a4 من میشه مینیمم .و ترتیب فاصله های من که به صورت صعودی تنضیم کنم میشه a6<a3<a1<a2<a5 و طبق الگوریتم من باید نقطه a4 و a6 رو پوش کنم.
در اینجا مقدار m من میشهm=3/7در نتیجه شیبش مثبت است یا جنوب شرقی یا شمال غربی است.
منظورتون کدوم x ها یا y هاست؟حالا با استفاده از تفاضل x ها یا y ها می شه فهمید که شیب خط ، مربوط به کدوم قسمتهنقطه جدید منظورتون a3 هست؟y معادله رو با y جدید چه مقایسیه کنم؟x نقطه جدید رو داخل معادله میذاری و y که از معادله به دست میاد رو با y نقطه جدید مقایسه می کنی
البته دوست عزیز ما در صفحه مانیتور مختصات منفی نداریم و شما مختصات های خو دا بر حسب افزایش زاویه کسینوس آنها با نقطه مینیمم(نقطه ای که کمترین yرا دارد)مرتب کنید. برای بدست اوردن این زاویه می توانید خطی را بین 1نقطه تا نقطهp فرض کنید و با رابطه فیثاغورس طول آ نخط را بدست بیاوری و با طول آن خط وضلع مجاور میزان کوسینوس آن را محاسبه کنید
دوست عزیز مشکل من مرتب کردن هانه نیستش.مشکل من قسمت 6 ام اگوریتمه من اونجا رو خوب درک نمیکنم چیهالبته دوست عزیز ما در صفحه مانیتور مختصات منفی نداریم و شما مختصات های خو دا بر حسب افزایش زاویه کسینوس آنها با نقطه مینیمم(نقطه ای که کمترین yرا دارد)مرتب کنید. برای بدست اوردن این زاویه می توانید خطی را بین 1نقطه تا نقطهp فرض کنید و با رابطه فیثاغورس طول آ نخط را بدست بیاوری و با طول آن خط وضلع مجاور میزان کوسینوس آن را محاسبه کنید
int convexhull::tashkhis_gardesh(int x1,int x2,int x3,int y1,int y2,int y3)
{
tash=(x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
return (tash);
}
این تابع رو من برای تشخیص گردش نوشتموتوضیحا ر هم برات فرستادم اگر باز جایش برات نا مفهوم بود بگو برات توضیح بدم
برای این مثال ، مراحل رو کامل می ریم جلو :
1 :
min = 1 ; //index of the minimum point
for (int i=2;i<7;i++)
if(a[i].y<a[m].y)
m=i;
return m;
2:
for(int i=1;i<7;i++)
{
a_p[i].x=a[i].x-a[m].x;
a_p[i].y=a[i].y-a[m].y;
}
3:
for(int i=1;i<7;i++)
{
ghotbi_a[i].r=sqrt(a_p[i].x*a_p[i].x+a_p[i].y-a_p[i].y);
ghotbi_a[i].teta=atan2(a_p[i].y,a_p[i].x);
}
4 :
swap(a_p[1],a_p[min]);
swap(ghotbi_a[1],ghotbi_a[min]);
for (int i=2;i<7;i++)
for(int j=i+1;j<7;j++)
{
if (ghotbi_a[i].teta>ghotbi_a[j].teta)
{
swap(a_p[i],a_p[j]);
swap(ghotbi_a[i],ghotbi_a[j]);
}
else if(ghotbi_a[i].teta==ghotbi_a[j])
if(ghotbi_a[i].r>ghotbi_a[j])
{
swap(a_p[i],a_p[j]);
swap(ghotbi_a[i],ghotbi_a[j]);
}
}
5 و 6 و 7:
stack.push(a_p[1]);
stack.push(a_p[2]);
for(int i=3;i<7;i++)
{
while(right(stack[top],stack[top-1],a_p[i]))
stack.pop();
stack.push(a_p[i]);
}
حالا تابع Right :
if(s[top].x-s[top-1].x==0) //m is unknown
if (s[top].y-s[top-1].y>0)
if(new_point.x>s[top].x) //new_point.x>s[top-1].x
return true; //new point is writer than the line
else
return false;
else
if(new_point.x<s[top].x)
return true;
else
return false;
else
{
m=(s[top].y-s[top-1].y)/(s[top].x-s[top-1].x); //(s[top-1].y-s[top].y)/(s[top-1].x-s[top].x)
if(m>0) //in this example , we are here ;
{
y_line=m*(new_point.x-s[top].x)+s[top].y; //y_line=m*(new_point.x-s[top-1].x)+s[top-1].y or we can compute x_line instead of y_line
if(s[top].y>s[top-1].y) // s[top].x>s[top-1].x //line is in southeast -> jonube sharghi
if(new_point.y<y_line)
return 1;
else
return 0;
else //line is in northwest -> shomal gharbi
if(new_point.y>y_line)
return true;
else
return false;
}
}
دو حالت رو نوشتم . دو حالت دیگه هم خودتون محاسبه کنید . به همین راحتی به دست میاد . البته لازمه که ذکر کنم الگوریتم این قسمت هم میشه بهینه تر نوشت که باز نیاز به تسلط بیش تر روی مباحث طراحی الگوریتم و صفحه مختصات داره . مثلا می شه گفت راهی وجود داره که این if های تو در تو ، همه در یک معادله ی خاص ، گنجانده بشه .
من پیاده سازی میکنم ولی نمی دونم چرا یکی اشتباه جواب میده.
#define MAX 30
class convexhull
{
public:
convexhull();
void input();
void findmin();
void bubbleSort ();
void findangel();
int right(int ,int ,int ,int ,int ,int );
int get_n();
int get_x(int a);
int get_y(int b);
private:
int x[MAX];
int y[MAX];
double D[MAX];//araye baraie sabte zavie ha
double R[MAX];//vatar ha
int n;//tedade noghte ha
int count;//shomare y ke minimi ast
};
convexhull::convexhull()
{
n=0;
count=0;
}
void convexhull::findmin()
{
int min;
min=y[0];
for(int i=0;i<n;i++)
{
if(y[i]<min)
{
min=y[i];//kochik tarin y
count=i;//shomare kochik tarin y
}
}
}
void convexhull::input()
{
cout <<"how many are there point in the screen = ";
cin >>n;
for(int i=0;i<n;i++)
{
cout <<"\nEnter X point"<<i+1<<" = ";
cin >>x[i];
cout <<"Enter y point"<<i+1<<" = ";
cin >>y[i];
}
}
void convexhull::findangel()
{
double x1,y1;//noghte haie jadid
for(int i=0;i<n;i++)
{
x1=x[i]-x[count];
y1=y[i]-y[count];
D[i]=(atan2(y1,x1)*180)/3.14;
R[i]=sqrt(x1*x1 + y1*y1);
}
}
void convexhull::bubbleSort()
{
double item;
int item2,item3;
for(int i = n - 1 ; i > 0; i --)
{
for(int j = 0; j < i ; j++)
if(D[j] > D[j + 1])
{
item = D[j] ;
D[j] = D[j + 1];
D[j + 1] = item ;
item2 = x[j] ;
x[j] = x[j + 1];
x[j + 1] = item2 ;
item3 = y[j] ;
y[j] = y[j + 1];
y[j + 1] = item3 ;
}
else if(D[i]==D[i+1])
{
if(R[j] > R[j + 1])
{
item = R[j] ;
R[j] = R[j + 1];
R[j + 1] = item ;
item2 = x[j] ;
x[j] = x[j + 1];
x[j + 1] = item2 ;
item3 = y[j] ;
y[j] = y[j + 1];
y[j + 1] = item3 ;
}
}
}
}
int convexhull::right(int x1,int x2,int x3,int y1,int y2,int y3)//x1 = top-1 x2=top x3=new x
{
int m,y_line;
if(x2-x1==0)
{
if (y2-y1>0)
{
if(x3>x2)
return true;
else
return false;
}
else
{
if(x3<x2)
return true;
else
return false;
}
}
else
{
m=(y2-y1)/(x2-x1);
if(m>0)
{
y_line=m*(x3-x1)+y1;//
if(y2>y1)
if(y3<y_line)
return false;
else
return true;
else
if(y3>y_line)
return true;
else
return false;
}
}
}
int convexhull::get_n()
{
return n;
}
int convexhull::get_x(int a)
{
return x[a];
}
int convexhull::get_y(int b)
{
return y[b];
}
/////////////
int main()
{
stack ob1,ob2;//2ta object baraie stack yeki x yeki y
convexhull ob;
int top,n;
ob.input();
ob.findmin();
ob.findangel();
ob.bubbleSort();
n=ob.get_n();
for(int i=0;i<2;i++)
{
ob1.push(ob.get_x(i));
ob2.push(ob.get_y(i));
}
for(int i=2;i<n;i++)
{
top=ob1.get_top();
if(ob.right(ob1.get_stack(top-1),ob1.get_stack(top),ob.get_x(i),ob2.get_stack(to p-1),ob2.get_stack(top-2),ob.get_y(i))==true)
{
ob1.pop();
ob2.pop();
}
else
{
ob1.push(ob.get_x(i));
ob2.push(ob.get_y(i));
}
}
من while رو به if تغیر دادم چون دیگه تو صفحه نمایش چیزی نشون نمیداد stack خالی میشه
for(int i=2;i<n;i++)
{
top=ob1.get_top();
if(ob.right(ob1.get_stack(top-1),ob1.get_stack(top),ob.get_x(i),ob2.get_stack(to p-1),ob2.get_stack(top-2),ob.get_y(i))==true)
}[/CPP]
من while رو به if تغیر دادم چون دیگه تو صفحه نمایش چیزی نشون نمیداد stack خالی میشه[/QUOTE]
من یه نگاه اجمالی انداختم . زیاد دقیق ندیدم . شاید جای دیگه ای هم ایراد داشته باشه .
ولی الگوریتم رو تغییر نده . با همون while بنویس . چون اگه با if باشه ، فقط یه بار می تونه pop رو انجام بده . در حالی که ممکنه تو یه مرحله ، 2 یا چند بار نیاز به pop باشه . همچنین یه نگاهی به آرگومان های ورودی تابع right بنداز . بره x ها ، top و top-1 به کار بردی . ولی بره y ها top-1 و top-2 در حالی که باید متناظر باشن .
for(int i=2;i<n;i++)
{
top=ob1.get_top();
while(ob.right(ob1.get_stack(top-1),ob1.get_stack(top),ob.get_x(i),ob2.get_stack(to p-1),ob2.get_stack(top),ob.get_y(i)))
{
ob1.pop();
ob2.pop();
}
ob1.push(ob.get_x(i));
ob2.push(ob.get_y(i));
}
من این کد نوشتم ولی باز هم مشکل داره.
مثال:
)3,7) a2(2,3) a3 (-3,6) a4(0,5) کار میکنه ولی مثلا تونقطه های قبلی که نوشتم کار نمیکنهa1
با سلام
اقا شرمنده واسه پیاده سازی
بعد از پیداکردن نزدیک ترین نقطه که کم ترین Yرو داره تو پشته ذخیره میشه ؟؟یا تو یه متغییر؟؟
میشه راهنمایی کنید؟؟؟
اقا من این کده شما رو اجرا کردم
یه سوال پیش امد برام
متد هایpush,pop,get_stackرو داخل کلاس گراهام نوشتید؟؟؟ یا اینکه یه stackایجاد کردید؟؟
این برنامه پایین ، باید یه کم تغییر پیدا کنه که بشه اون چیزی که لازمش داریم . مثلا بعضی متغیر ها به واسطه ی یه توابعی که قبلا استفاده کردم و الآن از تو برنامه برداشتم ، به صورت سراسری تعریف شدند . در حالی که میتونن نباشن .
همچنین دو فرمول جدید براتون می نویسم که با این ها می شه مرحله 2 و 3 رو ادغام کرد و بدون تغییر مختصات که لازمش تبدیل دوباره ی مختصات به حالت قبلی یا ذخیره ی مختصات جدید در آرایه ای جداگانه بود ، می شه مختصات قطبی رو بر حسب p0 محاسبه کرد که البته باز هم این معادله ها تو کد زیر استفاده نشدن .
#include<iostream>
#include"math.h"
///////////class decart
class decart
{
public:
double x;
double y;
void input(double m,double n)
{x=m;
y=n;}
friend class stack;
friend class ghotb;
friend int minimum(decart [],int);
friend void change_axis(decart [], int ,int);
friend bool right(stack,decart);
friend void covex_hull();
}; //////////class point************
///////////class ghotb
class ghotb
{
private:
double r;
double teta;
public:
void convert(decart m)
{
r=sqrt(m.x*m.x+m.y*m.y);
teta=atan2(m.y,m.x);
}
friend void ghotb_sort(ghotb[],decart[],int,int);
};
///////////class stack
class stack
{
private:
int top;
decart st[100];
public:
stack()
{top=-1;}
bool IsFull()
{return (top==99);}
bool IsEmpty()
{return (top==-1);}
void push(decart k)
{
if(!IsFull())
st[++top]= k;
}
decart pop()
{
decart k;
k.x=0;
k.y=0;
if(!IsEmpty())
k=st[top--];
return k;
}
friend bool right(stack,decart);
}; ////////////class stack************
///////////prototypes
bool right(stack,decart);
int minimum(decart [],int);
void convex_hull();
stack graham (decart [],int);
void change_axis(decart[],int,int);
void ghotb_sort(ghotb[],decart[],int,int);
template <class type>
void change(type &, type &);
///////////prototypes************
decart q[50];
decart h[50];
int num,hull;
///////////main
int main()
{
double x,y;
cout<<"Convex Hull with Graham algorithm\nHow many points are in XOY page ?\n";
cin>>num;
for (int i=0;i<num;i++)
{
cout<<"enter x & y"<<endl;
cin>>x>>y;
h[i].input(x,y);
}
stack convex;
convex = graham(h,num);
q[0]=convex.pop();
cout<<"from ( "<<q[0].x<<" , "<<q[0].y<<" ) to ( ";
for(hull=1;!convex.IsEmpty();hull++)
{
q[hull]=convex.pop();
cout<<q[hull].x<<" , "<<q[hull].y<<" )"<<endl;
cout<<"from ( "<<q[hull].x<<" , "<<q[hull].y<<" ) to ( ";
}
cout<<q[0].x<<" , "<<q[0].y<<" )"<<endl;
cin>>x;
return 0;
}
///////////minimum function
int minimum(decart s[],int n)
{
int min=0;
for(int i=1;i<n;i++)
if(s[i].y<s[min].y)
min=i;
return min;
}
///////////minimum function***************
//////////graham algorithm
stack graham(decart k[],int n)
{
stack result;
decart out;
decart p[100];
for(int i=0;i<n;i++)
p[i]=k[i];
int min=minimum(p,n);
change_axis(p,n,min);
ghotb f[100];
for (int i=0;i<n;i++)
f[i].convert(p[i]);
ghotb_sort(f,k,n,min);
result.push(k[0]);
result.push(k[1]);
for(int i=2;i<n;i++)
{
while (right(result,k[i]))
out=result.pop();
result.push(k[i]);
}
return result;
}
//////////graham algorithm************
//////////change axis funktion
void change_axis(decart k[],int size,int new_o)
{
double new_x,new_y;
new_x=-1*k[new_o].x;
new_y=-1*k[new_o].y;
for(int i=0;i<size;i++)
k[i].input(k[i].x+new_x,k[i].y+new_y);
}
//////////change axis function**********
//////////ghotb sort function
void ghotb_sort(ghotb s[],decart k[],int size , int o_o)
{
change(s[0],s[o_o]);
change(k[0],k[o_o]);
for(int i=1;i<size;i++)
for(int j=i+1;j<size;j++)
{
if(s[i].teta>s[j].teta)
{
change(s[i],s[j]);
change(k[i],k[j]);
}
if(s[i].teta==s[j].teta)
if(s[i].r>s[j].r)
{
change(s[i],s[j]);
change(k[i],k[j]);
}
}
}
///////////ghotb sort function***********
///////////right checker function
bool right(stack f,decart k)
{
float m,line_y;
if(f.st[f.top].x-f.st[f.top-1].x==0)
if(f.st[f.top].y>f.st[f.top-1].y)
if(k.x>f.st[f.top].x)
return 1;
else
return 0;
else
if(k.x<f.st[f.top].x)
return 1;
else
return 0;
else
{
m=(f.st[f.top].y-f.st[f.top-1].y)/(f.st[f.top].x-f.st[f.top-1].x);
if(m==0)
if(f.st[f.top].x>f.st[f.top-1].x)
if(k.y<f.st[f.top].y)
return 1;
else
return 0;
else
if(k.y>f.st[f.top].y)
return 1;
else
return 0;
if(m>0)
{
line_y=m*(k.x-f.st[f.top].x)+f.st[f.top].y;
if(f.st[f.top].x>f.st[f.top-1].x)
if(k.y<line_y)
return 1;
else
return 0;
else
if(k.y>line_y)
return 1;
else
return 0;
}
if(m<0)
{
line_y=m*(k.x-f.st[f.top].x)+f.st[f.top].y;
if(f.st[f.top].x<f.st[f.top-1].x)
if(k.y>line_y)
return 1;
else
return 0;
else
if(k.y<line_y)
return 1;
else
return 0;
}
}
return 0;
}
///////////right chacker function***************
///////////change function
template<class type>
void change(type &a,type &b)
{
type temp;
temp=a;
a=b;
b=temp;
}
r=sqrt((x-p0_x)*(x-p0_x)+(y-p0_y)*(y-p0_y));
teta=atan2((y-p0_y)/(x-p0_x));
با این اوصاف ، بره نقطهی p0 متغیر های r,teta صفر می شن و برای بقیه نقاط هم بر حسب فاصله و زاویه ای که با p0 دارن ، محاسبه می شه .
دوست عزیز
من کد شما رو در ++ virsual C گذاشتم و الان این قسمت آخر که براوتن مینویسم رو ارور میده :
template<class type>
void change(type &a,type &b)
{
type temp;
temp=a;
a=b;
b=temp;
}
ارورش هم اینه
باید چی کار کنم ؟see reference to function template instantiation 'void __cdecl change(class ghotb &,class ghotb &)' being compiled
اصلا این قسمت از کدتون چیکار میکنه ؟
با سلام
اقا این کدی که در قسمت بالا گذاشتید من خوندم متوجه نشدم این تابع برای چی استفاده شده و قتی هم هم از برنامه حذفش کردم هیچ مشکلی در برنامه بوجود نیومد در کل کاره خاصی که مربوط به برنامه باشه انجام نمیداد
//////////change axis funktion
void change_axis(decart k[],int size,int new_o)
{
double new_x,new_y;
new_x=-1*k[new_o].x;
new_y=-1*k[new_o].y;
for(int i=0;i<size;i++)
k[i].input(k[i].x+new_x,k[i].y+new_y);
}
//////////change axis function**********
ممنون میشم در موردش و کاربردش تو این برنامه توضیح بدید
برنامه مشکلی نداره من امتحان کردم احتمالا مشکل از کتمپیلرتئن هست
با کامپیلر دیگه ای امتحان کنید
این جا ، همون قسمت دوم الگوریتم هست که توی پستای قبلی ، توضیح دادم . با این تابع ، الگوریتم میاد p0 رو با روش انتقال مختصات ، به مرکز مختصات تبدیل می کنه تا تو مرحله ی بعدی ، زاویه ی قطبی بر حسب مرکز مختصات جدید p0 محاسبه بشه . حالا اگه پاک کردین و ارور نداده ، شاید تو شرایط خاص بوده . شما نقطه ها رو طوری قرار بدین که p0 تو محل های مختلفی از صفحه مختصات قرار بگیره .
البته شاید به قول شما این مرحله ، اضافی باشه . ولی از نظر تئوری و منطق ریاضی شخصیم ، چنین مرحله ای بره الگوریتم ، لازم بود .
این قسمت بره جا به جایی مقدار دو متغیری هست که بهش داده شده . این متغیرها هم به روش ارجاعی به تابع داده می شن . در واقع همون کار swap داره انجام می شه . به این دلیل ، template تعریف شده که بره هر دو متغیر با نوع داده های مختلف ، کار یکسانی انجام بده و با همین اسم براشون صدا زده بشه .
تو این برنامه هم بره جا به جایی دو نوع متغیر استفاده می شه : decart و ghotb
سلام
کد ابتکاری خودمه (شبیه روش معروفش ولی بدون پشته و مرتب سازی و اینجور چیزا) و تو C++builder نوشتم.
ابتدا چند تعریف :
#include <math.h>
#include <vector.h>
double atan2_abs(const double y, const double x)
{
#define PI_MULTI_2 6.283185307179586476925286766559
double result = atan2(y, x);
if (result < 0.0)
return PI_MULTI_2 + result;
else
return result;
};
#pragma pack(push, 1)
typedef struct TVec2D
{
public:
float x, y;
TVec2D() {};
TVec2D(float x_, float y_) {x = x_; y = y_;};
} *PVec2D;
#pragma pack(pop)
float V2DDistance(const TVec2D * pV1, const TVec2D * pV2)
{
float x = pV1->x - pV2->x;
float y = pV1->y - pV2->y;
return (float)sqrt(x * x + y * y);
};
و یک تابع کمکی برای ساختن رندم مجموعه ای از نقاط :
void CreateRandomVertex(PVec2D * pOut, int count, float radius, float offsetX, float offsetY)
{
*pOut = (TVec2D *)malloc(count * sizeof(TVec2D));
for (int i = 0; i < count; i++)
{
float angle = (random(LRAND_MAX) * 2.0 * M_PI) / LRAND_MAX;
float length = (random(LRAND_MAX) * radius) / LRAND_MAX;
(*pOut)[i] = TVec2D(
length * cos(angle) + offsetX,
length * sin(angle) + offsetY);
};
};
حالا تابع اصلی :
void convexHull(int ** pOutIndexs, int * pCount, const float * points, const int p2D_count )
{
#define EPSILON_FLOAT 0.00001
if (p2D_count < 3) return;
//------------------------
PVec2D verts = (TVec2D *)points; // converts float pointer to vertex pointer.
vector< int > vIndex; // for write convex hull vertex in vector.
vIndex.resize(1); // resize it for first index.
// find first point2D = min y | min x;
int p0_index = 0; // p0_index = (index of first point). start with : index = 0.
for (int i = 0; i < p2D_count; i++) // check oll verts.
{
if ((verts[i].y) < (verts[p0_index].y))
{
p0_index = i;
}
else if (fabs(verts[i].y - verts[p0_index].y) < EPSILON_FLOAT) // (y - y) == 0
{
if (verts[i].x < verts[p0_index].x) // if (y == y) then (min x)
{
p0_index = i;
};
};
};
vIndex[0] = p0_index; // set first Point.
//-----------------------
float distance = 0.0f;
float lastEdgeAngle = 0.0f;
int lastIndex = vIndex[0];
while ( // find convex hull vertex
(vIndex.size() < p2D_count) && // limited for read of memory
(
(vIndex.size() == 1) || // only in start
(lastIndex != p0_index) // end of cycle
// __
// / \
// | |
// \_p0_/
//
))
{
int localIndex = lastIndex;
float angle2 = 2 * M_PI; // max angle
distance = -1.0f; // set d value only to negative (< 0)
for (int i = 0; i < p2D_count; i++)
{
if (i != lastIndex) // each vert only test with other vertex
{
double at2Y = verts[i].y - verts[lastIndex].y;
double at2X = verts[i].x - verts[lastIndex].x;
if ((at2X == 0) && (at2Y == 0)) // error in atan2
{
MessageBoxW(0, L"x == y == 0", L"", 0);
}
float localAngle = (float)atan2_abs(at2Y, at2X); // angle between 2 vert
if (fabs(localAngle - angle2) < EPSILON_FLOAT) // angle == angle
{
float localDistance = V2DDistance(&verts[i], &verts[lastIndex]);
if ((distance < 0) || (distance > localDistance)) // find nearest verts by min angle
{
distance = localDistance;
localIndex = i;
};
}
else if (
(localAngle >= lastEdgeAngle) && // find min angle that
(localAngle < angle2)) // greater than last angle.
{
angle2 = localAngle;
localIndex = i;
};
};
};
lastEdgeAngle = angle2;
lastIndex = localIndex;
vIndex.resize(vIndex.size() + 1);
vIndex[vIndex.size() - 1] = lastIndex;
};
//------------------------------------
// copy verts data to input pointer and return it for output.
*pCount = vIndex.size();
*pOutIndexs = (int *)malloc(int(*pCount) * sizeof(int));
for (int i = 0; i < (*pCount); i++)
{
(*pOutIndexs)[i] = vIndex[i];
};
};
--------------------------------------
حالا دو تابع برای ترسیم :
void DrawVerts(HDC dc, PVec2D verts, int count, int size,
float scaleX = 1.0f,
float scaleY = 1.0f,
float offsetX = 0.0f,
float offsetY = 0.0f)
{
SelectObject(dc, GetStockObject(DC_BRUSH));
DWORD cl = GetDCBrushColor(dc);
//-----------------
SetDCBrushColor(dc, 0x0000ffff);
int size_2 = size / 2;
float x, y;
for (int i = 0; i < count; i++)
{
x = verts[i].x * scaleX + offsetX;
y = verts[i].y * scaleY + offsetY;
Rectangle(dc,
x - size_2,
y - size_2,
x + size_2,
y + size_2);
};
//-------------
SetDCBrushColor(dc, cl);
};
void DrawEdge(HDC dc, PVec2D verts, int * vertList, int edgeCount,
float scaleX = 1.0f,
float scaleY = 1.0f,
float offsetX = 0.0f,
float offsetY = 0.0f)
{
SelectObject(dc, GetStockObject(DC_PEN));
DWORD cl = GetDCPenColor(dc);
//-----------------
SetDCPenColor(dc, 0x00ffff00);
float x = verts[vertList[0]].x * scaleX + offsetX;
float y = verts[vertList[0]].y * scaleY + offsetY;
MoveToEx(dc, x, y, NULL);
for (int i = 0; i < edgeCount; i++)
{
x = verts[vertList[i]].x * scaleX + offsetX;
y = verts[vertList[i]].y * scaleY + offsetY;
LineTo(dc, x, y);
};
//-------------
SetDCPenColor(dc, cl);
};
و یک نمونه ی استفاده :
HWND hwnd = this->Handle;
tagRECT r; // rect of drawing.
::GetClientRect(hwnd, &r);
//------------------
TVec2D * verts;
int count = 50;
CreateRandomVertex(&verts, count, r.bottom / 2, r.right / 2, r.bottom / 2);
// 0000000000000000000000000 test y == y || x == x
/*
for (int i = 0; i < 10; i++)
{
verts[i].y = 5;
verts[i + 11].x = 20;
}
*/
// 0000000000000000000000000
int * pConvexHull;
int ConvexHull_Count;
convexHull(&pConvexHull, &ConvexHull_Count, (float *)verts, count);
//------- Draw start.
HDC dc = GetDC(hwnd);
Rectangle(dc, 0, 0, r.right, r.bottom); // clear background.
DrawVerts(dc, verts, count, 6);
DrawEdge(dc, verts, pConvexHull, ConvexHull_Count);
ReleaseDC(hwnd, dc);
//------- Draw end.
free(verts);
free(pConvexHull);
با سلتم و تشکر فراوان بابت کمک هاتون
اقا یه سوال دیگه با عرض پوزش
تابع
bool right(stack,decart);
که استفاده کردید
میشه در مورد نحوه کارش و کاری که قراره انجام بده توضیح بدید
ممنون از لطفتون
منتظر جوابتون هستم
این یعنی حتی اگه بعنوان مثال نقطه (4و2)به عنوان p0در نظر گرفته باشه نقاط بعدی مختصاتشون تغییر میکنه؟؟؟
یا حتی اگر x یک نقطه کم تر از p0باشد یعنی xمنفی میشه؟؟؟
حالا که نقاط رو محو مختصاتن اصلان میتونن مقدار منفی داشته باشن؟؟
اگه حالا منفی پیش بیا چی میشه؟؟؟
میشه یکم بیشتر توضیح بدید؟؟؟؟
در هر حالتی ، بره اینکه بتونید مختصات قطبی همه ی نقاط رو نسبت به نقطه p0 به دست بیارید ، باید به نوعی ، ابتدا مختصات نقطه ی مورد نظر رو با در نظر گرفتن p0 به عنوان مرکز مختصات ، به دست بیارید و بعدش با استفاده از 2 فرمول r و teta مختصات دکارتی نقطه نسبت به p0 ( که به دست اوردین ) رو به مختصات قطبی نقطه نسبت به p0 تبدیل کنید . این مختصات قطبی هم به درد جایی می خوره که بخواید نقاط رو به صورت راست گرد بر حسب p0 مرتب کنید .
پس نتیجه می گیریم که در کل p0 هر جایی باشه ( به جز (0و0) ) باید مختصات نقاط رو نسبت به p0 به دست بیاریم تا بتونیم مختصات قطبی هر نقطه رو نسبت به p0 داشته باشیم و بر حسب زاویه teta به صورت راست گرد ، نقاط رو تو لیست ، مرتب کنیم .
در ضمن الگوریتم ذکر شده بره (0و0) هم عملیات رو انجام می ده و تفاوتی قائل نمی شه . البته الگوریتم نوشته شده همون طور که گفتم ، بهتر از این هم میتونه باشه . یعنی بهینه تر بشه .
بچه ها من برنامه رو کامل کردم و بصورت اپن سورس براون میزارم امید وارم که بدردتون بخوره..convex hull1.rar
سلام
من فایل رو دانلود کردم ولی کتابخانه graphic.h رو نمیشناسه
چ کنم؟
اون کدای قبلی رو هم هر کار کردم اجرا نکرد
ممنون میشم کمکم کنید
اگر امکانش هست موازیشم بگین
با openmpو mpi
اینم یه convex hull واسه برو بچه های تیم ملی، البته کد از من نیست، الگوریتمش فکر کنم andrew's monotone chain باشه.
کد تست نشده.
struct Point {
double x, y;
Point(double x=0, double y=0):x(x),y(y) { }
};
typedef Point Vector;
Vector operator - (const Point& A, const Point& B) {
return Vector(A.x-B.x, A.y-B.y);
}
double Cross(const Vector& A, const Vector& B) {
return A.x*B.y - A.y*B.x;
}
bool operator < (const Point& p1, const Point& p2) {
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}
bool operator == (const Point& p1, const Point& p2) {
return p1.x == p2.x && p1.y == p2.y;
}
vector<Point> ConvexHull(vector<Point> p) {
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
int n = p.size();
int m = 0;
vector<Point> ch(n+1);
for(int i = 0; i < n; i++) {
while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
ch[m++] = p[i];
}
int k = m;
for(int i = n-2; i >= 0; i--) {
while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
ch[m++] = p[i];
}
if(n > 1) m--;
ch.resize(m);
return ch;
}
سلام دوست عزیز، نیازی نیست حتما از کتابخونه استفاده کنی از تو برنامه پاک کن و لی در کلgraphic.hرا باید تو محیط 32 بیتی (Win Xp) ازش استفاده کنی و همچنین فایل کتابخانه مورد نظر رو در تو کامپایلری که باهاش کار میکنی لینک کنی.
در مورد قسمت دوم سولات "اگر امکانش هست موازیشم بگین
با openmpو mpi " کمی بیشتر توضیح بده تا بتونم کمکت کنم.
سلام . شما تونستيد الگوريتم convex hull رو پيداكنيد
سلام دوست عزیز
من برنامه رو با الگریتم گراهام نوشتم ،برنامه رو برای دانلود گذاشتم الگرتم رو هم می تونید تو اینترنت پیدا کنید.
موفق باشید
توی لینک زیر توضیحاتی راجب این الگریتم هست.
http://en.wikipedia.org/wiki/Graham_scan
امید وارم بدردتون بخوره
پاسخ با نقل قول
