计算几何模板之二维点线面模板

#include
#include
#include
using namespace std;
//================= 精度误差 ==============
const double eps = 1e-8;
int dcmp( double x )
{if( fabs(x)}//================= 点结构 ===============
struct pnode
{double x,y;pnode( double a=0.0,double b=0.0):x(a),y(b){}// X乘重载double operator ^ (const pnode &b)const{return x*b.y - b.x*y;}pnode operator - ( const pnode &b)const{return pnode( x-b.x, y-b.y);}pnode operator * (const double p)const{return pnode( x*p, y*p );}pnode operator + (const pnode&b)const{return pnode( x+b.x, y+b.y );}bool operator == (const pnode&b)const{return dcmp( x-b.x )== 0 && dcmp( y-b.y )==0;}bool operator <(const pnode&b)const{return x (const pnode&b)const{return x > b.x || ( dcmp( x-b.x )==0 && y>b.y );}
};
//================ 线结构 ==============
typedef pnode myvec;
struct pline
{pnode st,ed;//st：起始点 ed：终点myvec vec;//向量pline(){}pline(pnode a,pnode b):st(a),ed(b){vec = pnode(b-a);}
};/*x乘:公共起始点p0， V向量p0p1,W向量p0p2cross(v,w) > 0 W向量在 V向量左边
*/
double cross( pnode p0,pnode p1,pnode p2)
{return (p1-p0) ^ (p2-p0);
}
double cross(pline a,pline b)
{return (a.ed-a.st)^(b.ed-b.st);
}/*点乘：dot(v,w) == 二者长度乘积再乘上他们夹角的余弦夹角：从 v 到 w 逆时针旋转的角
*/
double dot( myvec v,myvec w)
{return v.x*w.x + v.y*w.y;
}
double dot( pline a,pline b)
{return a.vec.x * b.vec.x + a.vec.y * b.vec.y;
}//长度
double length( pline a)
{return sqrt(dot(a,a));
}
//返回夹角弧度值 逆时针为正
double angle( pline a,pline b)
{return acos( dot(a,b)/length(a)/length(b) );/*double acos(double x),x范围在 -1~1 之间返回的是一个数值的反余弦弧度值，其范围是 0~ pi 。例如： acos(1) 返回值是 0*/
}
//a向量旋转rad弧度 rad>0逆时针
myvec rotat(myvec a,double rad)
{return myvec( a.x*cos(rad)-a.y*sin(rad) , a.x*sin(rad)+a.y*cos(rad));
}
//矢量三角形面积*2
double area2(pnode p0,pnode p1,pnode p2)
{return cross(p0,p1,p2);
}//============= 直线，线段 ============//给定两条直线，求角平分线
myvec angle_bisector(pnode p, pline v1, pline v2)
{double rad = angle(v1, v2);return rotat(v1.vec, dcmp(cross(v1, v2)) * 0.5 * rad);
}//判断3点共线
bool line_coincide(pnode p1, pnode p2, pnode p3)
{return dcmp(cross(p1,p2,p3)) == 0;
}
//判断直线平行
bool line_parallel(pline v, pline w)
{return cross(v, w) == 0;
}
//判断直线垂直
bool line_vertical(pline v, pline w)
{return dot(v, w) == 0;
}
//点在直线上的投影点
pnode get_line_projection(pnode p, pline line)
{return line.st + line.vec * (dot(line, pline(line.st,p)) / dot(line, line));
}//判断点在线段上, 不包含端点
//dcmp(dot())<=0包含端点
bool on_segment(pnode p, pline line)
{return dcmp(cross(p,line.st, line.ed)) == 0 && dcmp(dot(line.st - p, line.ed - p)) <0;
}
//直线求交点 线判断非平行，非重合
//直线 p+tv ，q+tw 有唯一交点，当且仅当cross(v,w)!=0
pnode get_line_inter_point(pline v,pline w)
{pline u (w.st,v.st);double t = cross( w,u )/cross(v,w);return v.st + (v.ed-v.st) * t;
}//点到直线的距离
//平行四边形面积除以底
double dist_to_line( pnode p,pline line )
{pline v2 (line.st,p);return fabs( cross(line,v2)/length( line));//如果不区绝对值 得到的是有向距离
}//点到线段的距离
double dist_to_seg( pnode p ,pline seg)
{if( seg.st == seg.ed )return length( pline(seg.st,p) );pline v2 (seg.st,p);pline v3 (seg.ed,p);if( dcmp( dot(seg,v2) ) <0)return length( v2 );elseif( dcmp ( dot(seg,v2)) > 0)return length( v3 );elsereturn fabs( cross(seg,v2) )/length( seg );
}
//判断 线段 与 直线相交
bool seg_inter_line(pline line,pline seg)
{return ( dcmp( cross( seg.st,line.st,line.ed ) ) * dcmp( cross( seg.ed,line.st,line.ed) ) )<=0;
}
//判断 线段 与 线段 相交（允许端点在另一条线段上或者重合
bool seg_inter_seg(pline a,pline b)
{returnmax( a.st.x, a.ed.x) >= min( b.st.x, b.ed.x)&&max( b.st.x, b.ed.x) >= min( a.st.x, a.ed.x)&&max( a.st.y, a.ed.y) >= min( b.st.y, b.ed.y)&&max( b.st.y, b.ed.y) >= min( a.st.y, a.ed.y)&&//以上端点判断dcmp(cross( a.st, a.ed, b.st ))*dcmp(cross( a.st, a.ed, b.ed ))<=0&& dcmp(cross( b.st, b.ed, a.st ))*dcmp(cross( b.st, b.ed, a.ed ))<=0;
}
//两条线段有唯一一个不是端点的公共点
//线段规范相交（不允许端点在另一条线段上
bool seg_proper_inter_seg(pline a,pline b)
{double c1 = cross( a.st, a.ed, b.st );double c2 = cross( a.st, a.ed, b.ed );double c3 = cross( b.st, b.ed, a.st );double c4 = cross( b.st, b.ed, a.ed );return dcmp(c1)*dcmp(c2)<0&& dcmp(c3)*dcmp(c4)<0;
}
//判断线段是否在矩形内，允许线段端点再矩形四条边上
//参数（线段，矩形左上角顶点，矩形右下角顶点）
bool seg_in_rec(pline seg,double xl,double xr,double yt,double yb)
{returnseg.st.x >= min(xl,xr) && seg.st.x <= max(xl,xr)&& seg.ed.x >= min(xl,xr) && seg.ed.x <= max(xl,xr)&& seg.st.y >= min(yt,yb) && seg.st.y <= max(yt,yb)&& seg.ed.y >= min(yt,yb) && seg.ed.y <= max(yt,yb);
}
//多边形面积
double polygon_area(pnode*p,int n)
{double area = 0.0;for( int i = 1;i }
int main()
{
}