ACM内部函数7

技术2022-05-12 11

6.判断点是否在线段上

语法：

result=Pointonline(Point p1,Point p2,Point p);

参数：

p1、p2：线段的两个端点

p：被判断点

返回值：

0：点在不在线段上；1：点在线段上

注意：

若p线段端点上返回1

需要 math.h

源程序：

#define MIN(x,y) (x < y ? x : y)

#define MAX(x,y) (x > y ? x : y)

typedef struct {

double x,y;

} Point;

int FC(double x1,double x2)

{

if (x1-x2<0.000002&&x1-x2>-0.000002) return 1; else return 0;

}

int Pointonline(Point p1,Point p2,Point p)

{

double x1,y1,x2,y2;

x1=p.x-p1.x;

x2=p2.x-p1.x;

y1=p.y-p1.y;

y2=p2.y-p1.y;

if (FC(x1*y2-x2*y1,0)==0) return 0;

if ((MIN(p1.x,p2.x)<=p.x&&p.x<=MAX(p1.x,p2.x))&&

(MIN(p1.y,p2.y)<=p.y&&p.y<=MAX(p1.y,p2.y)))

return 1; else return 0;

}

7.判断两线段是否相交

语法：

result=sectintersect(Point p1,Point p2,Point p3,Point p4);

参数：

p1～4：两条线段的四个端点

返回值：

0：两线段不相交；1：两线段相交；2两线段首尾相接

注意：

p1!=p2;p3!=p4;

源程序：

#define MIN(x,y) (x < y ? x : y)

#define MAX(x,y) (x > y ? x : y)

typedef struct {

double x,y;

} Point;

int lineintersect(Point p1,Point p2,Point p3,Point p4)

{

Point tp1,tp2,tp3;

if ((p1.x==p3.x&&p1.y==p3.y)||(p1.x==p4.x&&p1.y==p4.y)||(p2.x==p3.x&&p2.y==p3.y)||(p2.x==p4.x&&p2.y==p4.y))

return 2;

//快速排斥试验

if ((MIN(p1.x,p2.x)<p3.x&&p3.x<MAX(p1.x,p2.x)&&MIN(p1.y,p2.y)<p3.y<MAX(p1.y,p2.y))||

(MIN(p1.x,p2.x)<p4.x&&p3.x<MAX(p1.x,p2.x)&&MIN(p1.y,p2.y)<p3.y<MAX(p1.y,p2.y)))

;else return 0;

//跨立试验

tp1.x=p1.x-p3.x;

tp1.y=p1.y-p3.y;

tp2.x=p4.x-p3.x;

tp2.y=p4.y-p3.y;

tp3.x=p2.x-p3.x;

tp3.y=p2.y-p3.y;

if ((tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=0) return 1; else return 0;

}

8.判断线段与直线是否相交

语法：

result=lineintersect(Point p1,Point p2,Point p3,Point p4);

参数：

p1、p2：线段的两个端点

p3、p4：直线上的两个点

返回值：

0：线段直线不相交；1：线段和直线相交

注意：

如线段在直线上，返回 1

源程序：

typedef struct {

double x,y;

} Point;

int lineintersect(Point p1,Point p2,Point p3,Point p4)

{

Point tp1,tp2,tp3;

tp1.x=p1.x-p3.x;

tp1.y=p1.y-p3.y;

tp2.x=p4.x-p3.x;

tp2.y=p4.y-p3.y;

tp3.x=p2.x-p3.x;

tp3.y=p2.y-p3.y;

if ((tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=0) return 1; else return 0;

}

9.点到线段最短距离

语法：

result=mindistance(Point p1,Point p2,Point q);

参数：

p1、p2：线段的两个端点

q：判断点

返回值：

点q到线段p1p2的距离

注意：

需要 math.h

源程序：

#define MIN(x,y) (x < y ? x : y)

#define MAX(x,y) (x > y ? x : y)

typedef struct {

double x,y;

} Point;

double mindistance(Point p1,Point p2,Point q)

{

int flag=1;

double k;

Point s;

if (p1.x==p2.x) {s.x=p1.x;s.y=q.y;flag=0;}

if (p1.y==p2.y) {s.x=q.x;s.y=p1.y;flag=0;}

if (flag)

{

k=(p2.y-p1.y)/(p2.x-p1.x);

s.x=(k*k*p1.x+k*(q.y-p1.y)+q.x)/(k*k+1);

s.y=k*(s.x-p1.x)+p1.y;

}

if (MIN(p1.x,p2.x)<=s.x&&s.x<=MAX(p1.x,p2.x))

return sqrt((q.x-s.x)*(q.x-s.x)+(q.y-s.y)*(q.y-s.y));

else

return MIN(sqrt((q.x-p1.x)*(q.x-p1.x)+(q.y-p1.y)*(q.y-p1.y)),sqrt((q.x-p2.x)*(q.x-p2.x)+(q.y-p2.y)*(q.y-p2.y)));

}

10.求两直线的交点

语法：

result=mindistance(Point p1,Point p2,Point q);

参数：

p1～p4：直线上不相同的两点

*p：通过指针返回结果

返回值：

1：两直线相交；2：两直线平行

注意：

如需要判断两线段交点，检验k和对应k1（注释中）的值是否在0～1之间，用在0～1之间的那个求交点

源程序：

typedef struct {

double x,y;

} Point;

int linecorss(Point p1,Point p2,Point p3,Point p4,Point *p)

{

double k;

//同一直线

if ((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)==0&&

(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)==0) return 2;

//平行，不同一直线

if ((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)==0) return 0;

k=((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y));

//k1=((p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y));

(*p).x=p1.x+k*(p2.x-p1.x);

(*p).y=p1.y+k*(p2.y-p1.y);

return 1;//有交点

}

11.判断一个封闭图形是凹集还是凸集

语法：

result=convex(Point *p,int n);

参数：

*p：封闭曲线顶点数组

n：封闭曲线顶点个数

返回值：

1：凸集；-1：凹集；0：曲线不符合要求无法计算

注意：

默认曲线为简单曲线：无交叉、无圈

源程序：

typedef struct {

double x,y;

} Point;

int convex(Point *p,int n)

{

int i,j,k;

int flag = 0;

double z;

if (n < 3)

return(0);

for (i=0;i<n;i++) {

j = (i + 1) % n;

k = (i + 2) % n;

z = (p[j].x - p[i].x) * (p[k].y - p[j].y);

z -= (p[j].y - p[i].y) * (p[k].x - p[j].x);

if (z < 0)

flag |= 1;

else if (z > 0)

flag |= 2;

if (flag == 3)

return －1; //CONCAVE

}

if (flag != 0)

return 1; //CONVEX

else

return 0;

}

12.Graham扫描法寻找凸包

语法：

Graham_scan(Point PointSet[],Point ch[],int n,int &len);

参数：

PointSet[]：输入的点集

ch[]：输出的凸包上的点集，按照逆时针方向排列

n：PointSet中的点的数目

len：输出的凸包上的点的个数

返回值：

null

源程序：

struct Point{

float x,y;

};

float multiply(Point p1,Point p2,Point p0)

{

return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));

}

float distance(Point p1,Point p2)

{

return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));

}

void Graham_scan(Point PointSet[],Point ch[],int n,int &len)

{

int i,j,k=0,top=2;

Point tmp;

for(i=1;i<n;i++)

if ((PointSet[i].y<PointSet[k].y)||((PointSet[i].y==PointSet[k].y)&&(PointSet[i].x<PointSet[k].x)))

k=i;

tmp=PointSet[0];

PointSet[0]=PointSet[k];

PointSet[k]=tmp;

for (i=1;i<n-1;i++)

{

k=i;

for (j=i+1;j<n;j++)

if ( (multiply(PointSet[j],PointSet[k],PointSet[0])>0) ||

((multiply(PointSet[j],PointSet[k],PointSet[0])==0)

&&(distance(PointSet[0],PointSet[j])<distance(PointSet[0],PointSet[k]))) )

k=j;

tmp=PointSet[i];

PointSet[i]=PointSet[k];

PointSet[k]=tmp;

}

ch[0]=PointSet[0];

ch[1]=PointSet[1];

ch[2]=PointSet[2];

for (i=3;i<n;i++)

{

while (multiply(PointSet[i],ch[top],ch[top-1])>=0) top--;

ch[++top]=PointSet[i];

}

len=top+1;

}

专利

最新回复(0)