Point Base; boolcmp_ang(const Point &a,const Point &b) { int tmp=dcmp(cross(a-Base,b-Base)); if(tmp==0)returndist(Base,a)<dist(Base,b); elsereturn tmp>0; }
intis_in_polygon(Point a) { Line ray;//射线 ray.s=a; ray.e=Vector(-100000000.0,a.y); int ans=0; for(int i=1;i<=cnt;i++) { Point s1=edge[i].s,s2=edge[i].e; if(on_seg(a,edge[i]))return0;//若a在边上返回0 if(dcmp(s1.y-s2.y)==0)continue;//若平行无视这条边 if(on_seg(s1,ray))//若上端点在射线上取上端点 { if(dcmp(s1.y-s2.y)>0)ans++; } elseif(on_seg(s2,ray))//同理 { if(dcmp(s2.y-s1.y)>0)ans++; } elseif(is_cross(ray,edge[i]))ans++;//判断线段与线段是否相交 } if(ans%2==1)return1; return-1; }
里面用到了两个函数现在给出它们的实现方法
判断点是否在线段上,首先判断点是否在直线上,然后判断点的左边范围,是否符合线段的条件
1 2 3 4 5
boolon_seg(Point a,Segment a1) { Point b=a1.s,c=a1.e; returndcmp(cross(b-a,c-a))==0&&min(b.x,c.x)<=a.x&&a.x<=max(b.x,c.x)&&min(b.y,c.y)<=a.y&&a.y<=max(b.y,c.y); }
首先检查点的跨立情况,然后处理特殊情况(两条直线重合)
事实证明快速排斥,只是用来加快判断速度(对正确性并无影响)
如果说是规范相交去掉后面的四个判断(判断两条直线重合)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
boolis_cross(Line a1,Line a2) { Point a=a1.s,b=a1.e,c=a2.s,d=a2.e; int c1=dcmp(cross(b-a,c-a)); int c2=dcmp(cross(b-a,d-a)); int o1=dcmp(cross(d-c,b-c)); int o2=dcmp(cross(d-c,a-c)); if(c1*c2<=0&&o1*o2<=0)returntrue; if(c1==0&&on_seg(c,a1))returntrue; if(c2==0&&on_seg(d,a1))returntrue; if(o1==0&&on_seg(b,a2))returntrue; if(o2==0&&on_seg(a,a2))returntrue; returnfalse; }
⑤判断圆是否在凸包内部
先判断圆心是否在凸包内部,然后判断圆心到凸包每条边的最近点的距离是否小于圆的半径。
1 2 3 4 5 6 7
boolcircle_is_in_convex_hull(Circle a) { if(is_in_polygon(a.O)<0)returnfalse; for(int i=1;i<=cnt;i++) if(dcmp(dist(a.O,get_nearest_point_on_segment(a.O,edge[i]))+eps-a.R)<0)returnfalse; returntrue; }
下面给出求点离线段的最近点的函数
求最近点有三种情况
最近点为左端点
最近点为右端点
最近点在线段中间
我们可以通过点乘,求出交点到左端点的距离,占线段总长度的比例。
dot(a-b,c-b)/dot(c-b,c-b)即为 =
的意义不言而喻。
1 2 3 4 5 6 7 8
Point get_nearest_point_on_segment(Point a,Line a1) { Point b=a1.s,c=a1.e; double t=dot(a-b,c-b)/dot(c-b,c-b); if(dcmp(t)!=-1&&dcmp(1-t)!=-1)returnVector(b.x+(c.x-b.x)*t,b.y+(c.y-b.y)*t); if(dist(a,b)<dist(a,c))return b; return c; }