tìm 1 điểm có thuộc một đa giác bất kì hay ko ?
ý tưởng :

Với mỗi đỉnh của đa giác ta đánh dấu là 0 hay 1 theo qui ước như sau: nếu là đỉnh cực trị hay đoạn cực trị thì đánh số 0. Nếu là đỉnh đơn điệu hay đoạn đơn điệu thì đánh dấu 1.
- Xét số giao điểm của tia nữa đường thẳng từ P là điểm cần xét với biên của đa giác. Nếu số giao điểm là chẳn thì kết luận điểm không thụôc đa giác. Ngược lại, số giao điểm là lẻ thì điểm thuộc đa giác.
Mình lất ví dụ đa giác có 4 đỉnh 50,60 70,200 120,300 200,200 với điểm xét là 100,150 Điểm nằm trong đa giác mà lại báo nằm ngoài, sửa hoài không thấy lỗi. Các bạn giúp mình với, mình chạy code này trong Dev-C

đây là code của mình!


#include <conio.h>
#include <stdio.h>
#include <graphics.h>


int ktdh()
{
int mode=0, driver=0;
initgraph(&mode,&driver,"c;\\ic\\bgi");
}
int dda(int x1,int y1,int x2,int y2,int color)
{
int dx,dy,k,step;
float x_inc,y_inc,x,y;
dx=x2-x1; dy=y2-y1;
if(abs(dx)>abs(dy))
step = abs(dx);
else step=abs(dy);
x_inc=(float)dx/step;
y_inc=(float)dy/step;
x=x1;y=y1;
putpixel((int)x,(int)y,color);
for(k=1;k<=step;k++)
{
x=x+x_inc;y=y+y_inc;
putpixel((int)x,(int)y,color);
}
}
typedef struct { int x,y; }dinh;
//ve da giac
void dagiac_dda(dinh d[10],int n)
{
int i;
d[n]=d[0];
char *s[10]={"A","B","C","D","E","F","G","H","I","J"};
for(i=0;i<n;i++)
{
dda(d[i].x,d[i].y,d[i+1].x,d[i+1].y,4);
outtextxy(d[i].x,d[i].y,s[i]);
}
}
// xet diem thuoc da giac
int next(int i,int n)
{
return (i+n+1)%n;
}


int prev(int i,int n)
{
return (i+n-1)%n;
}


int inpoly(dinh d[], dinh p,int n)
{
int count=0,i,y;
float x_cut=0;
for (int i=0;i<n-1;i++)
{
if (d[i].y == p.y)
{
if (d[i].x>p.x)
{
if (((d[prev(i,n)].y<p.y)&&(p.y<d[next(i,n)].y))||((d[prev(i,n)].y>p.y)&&(p.y>d[next(i,n)].y)))
count++;
if (d[next(i,n)].y=p.y)
if (((d[prev(i,n)].y<p.y)&&(p.y<d[next(i,n)].y))||((d[prev(i,n)].y>p.y)&&(p.y>d[next(i,n)].y)))
count++;
}
}
else
if (((d[i].y<p.y)&&(p.y<d[next(i,n)].y))||((d[i],y>p.y)&&(p.y>d[next(i,n)].y)))
{
x_cut=d[i].x+float((d[next(i,n)].x-d[i].x)/(d[next(i,n)].y-d[i].y)*(p.y-d[i].y));
if (x_cut>p.x) count++;
}
}
if (count%2==0)
return 0;
else return 1;
}
// to da giac
void todg(dinh d[],int n)
{
int x_max,y_max,x_min,y_min,i;
x_max=d[0].x ; y_max=d[0].y; x_min=d[0].x ; y_min=d[0].y;
for(i=0;i<n;i++)
{
if(x_max < d[i].x) x_max= d[i].x;
if(y_max < d[i].y) y_max= d[i].y;
if(x_min > d[i].x) x_min= d[i].x;
if(y_min > d[i].y) y_min= d[i].y;
}
dinh p;
int y,x;
for (x=x_min;x<x_max;x++)
{
for (y=y_min;y<y_max;y++)
{
p.x=x;
p.y=y;
if (inpoly(d,p,n)==1) putpixel(x,y,4);
}
// delay(10);
}
printf("%d %d %d %d ",x_max,y_max,x_min,y_min);
}
int main()
{
int i,n;
dinh d[10];
printf("nhap so dinh: "); scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("nhap vao toa do dinh thu %d: ",i+1);
scanf("%d%d",&d[i].x,&d[i].y);
}


ktdh();
setcolor(BLACK);
setbkcolor(WHITE);
cleardevice();
dagiac_dda(d,n);
// todg(d,n);
dinh p;
p.x=100;
p.y=150;
outtextxy(100,150,"o");
if(inpoly(d,p,n)==1) outtextxy(100,50,"DIEM THUOC DA GIAC");
else outtextxy(100,50,"DIEM NGOAI DA GIAC");
getch();
closegraph();
}