geometry - procom @ ウィキ

• 点クラス　複素平面をイメージ

  class P{
  	static final double EPS=1e-10;
  	static int signum(double x){
  		return x<-EPS?-1:x>EPS?1:0;
  	}
  	static Comparator<P> comp = new Comparator<P>(){
  		public int compare(P p1, P p2) {
  			return signum(p1.x-p2.x)!=0?signum(p1.x-p2.x):signum(p1.y-p2.y);
  		}
  	};
  	public static final P O = new P(0,0);
  	final double x, y;
  	P(double _x,double _y){
  		x=_x;
  		y=_y;
  	}
  	//四則
  	P add(P a){
  		return new P(x+a.x,y+a.y);
  	}
  	P sub(P a){
  		return new P(x-a.x,y-a.y);
  	}
  	P mul(P a){
  		return new P(x*a.x-y*a.y,x*a.y+y*a.x);
  	}
  	P div(P a){
  		double d2=a.dist2(O);
  		return new P(dot(a,this)/d2,cross(a,this)/d2);
  	}
  	//共役
  	P conj(){
  		return new P(x,-y);
  	}
  	//内積　a・b=|a||b|cosθ=a.x*b.x+a.y*b.y
  	static double dot(P a,P b){
  		return  a.x*b.x+a.y*b.y;
  	}
  	//外積　a×b=|a||b|sinθ=a.x*b.y-a.y*b.x
  	static double cross(P a,P b){
  		return  a.x*b.y-a.y*b.x;
  	}
  	//二乗距離
  	double dist2(P p){
  		return (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y);
  	}
  	//a,b間の距離
  	double dist(P p){
  		return sqrt(dist2(p));
  	}
  	public double norm(){
  		return dist(O);
  	}
  	// a→b→cと進むときの向き
  	static int ccw(P a,P b,P c){
  		b = b.sub(a); c = c.sub(a);
  		if(cross(b,c)>EPS) return 1;//counter clockwise
  		if(cross(b,c)<-EPS) return -1;//clockwise
  		if(dot(b,c)<-EPS) return 2;//c--a--b on line
  		if(b.norm()<c.norm()-EPS) return -2;//a--b--c on line
  		return 0;//a--c--b on line (or b==c)
  	}
  	//oからみたaの角度
  	static double arg(P a,P o){
  		P dir=a.sub(o);
  		double s=acos(dir.x/dir.norm());
  		return dir.y>0?s:2*PI-s;
  	}
  	//oを中心に回転
  	P rotate(P o,double arg){
  		return this.add(this.sub(o).mul(new P(cos(arg),sin(arg))));
  	}
  	//→OA,→OBの面積の2倍
  	static double S2(P a,P b,P o){
  		return cross(a.sub(o),b.sub(o));
  	}
  	static double S(P a,P b,P o){
  		return S2(a,b,o)/2;
  	}
  	//絶対値と偏角から座標を取得
  	static P polar(double abs,double arg){
  		return new P(abs*cos(arg),abs*sin(arg));
  	}
  	// ?
  	static P proj(P p,P o){
  		return o.mul(new P(dot(p,o)/o.norm(),0));
  	}
  	public boolean equals(Object obj) {
  		if(obj instanceof P){
  			P p=(P)obj;
  			return signum(x-p.x)==0 && signum(y-p.y)==0;
  		}
  		return false;
  	}
   
  	public String toString(){
  		return "("+x+","+y+")";
  	}
  }

• 線クラス

  //(注)
  //dist,isIntersectは擬似的に二項関係の演算子として扱う
  //intersectionはPのコンストラクタとして扱う
  class L extends AL{
  	L(P _p1, P _p2) {super(_p1, _p2);}
   
  	//直線と点の距離
  	double dist(P p){
  		return abs(P.S(p2,p,p1))/p1.sub(p2).norm();
  	}
  	boolean isIntersect(P p){
  		return abs(P.S(p2,p,p1))<EPS;
  	}
  	boolean isIntersect(L l){
  		if(isPoint() && l.isPoint())return p1.equals(l.p1);
  		if(isPoint())return l.isIntersect(p1);
  		if(l.isPoint())return isIntersect(l.p1);
  		return !isParallel(l) || isIntersect(l.p1);
  	}
   
  	//垂線の足
  	static P FootOfLP(L l,P p){
  		return l.p1.add(P.proj(p.sub(l.p1),l.p2.sub(l.p1)));
  	}
   
  	//線対称な点
  	static P LineSymmetricLP(L l,P p){
  		return FootOfLP(l,p).mul(new P(2.0,0)).sub(p);
  	}
   
  	public boolean equals(Object obj) {
  		if(obj instanceof L){
  			L l=(L)obj;
  			return isParallel(l) && isIntersect(l.p1);
  		}
  		return false;
  	}
  }
  //線分
  class S extends AL{
  	S(P _p1, P _p2) {super(_p1, _p2);}
  	boolean isIntersect(P p){//|a-p|+|p-b|<=|a-b|
  		return p1.sub(p).norm()+p2.sub(p).norm()<=p1.sub(p2).norm()+EPS;
  	}
  	boolean isIntersect(L l){//l2の端点がl1の上か下か
  		return P.cross(l.p2.sub(l.p1),p1.sub(l.p1))*
  			P.cross(l.p2.sub(l.p1),p2.sub(l.p1))<EPS;
  	}
  	boolean isIntersect(S l){
  		return P.ccw(p1,p2,l.p1)*P.ccw(p1,p2,l.p2)<=0
  		&& P.ccw(l.p1,l.p2,p1)*P.ccw(l.p1,l.p2,p2)<=0;
  	}
  	//線分と点
  	double dist(P p){
  		if(P.dot(p2.sub(p1),p.sub(p1))<EPS)return p.sub(p1).norm();
  		if(P.dot(p1.sub(p2),p.sub(p2))<EPS)return p.sub(p2).norm();
  		return abs(P.S(p2,p,p1))/p1.sub(p2).norm();
  	}
  	//直線との距離
  	double dist(L l){
  		if(isIntersect(l))return 0;
  		return min(l.dist(p1),l.dist(p2));
  	}
  	//線分と線分
  	double dist(S l){
  		if(isIntersect(l))return 0;
  		return min(min(dist(l.p1),dist(l.p2)),min(l.dist(p1),l.dist(p2)));
  	}
  }
  abstract class AL{
  	//geo
  	static final double EPS=1e-10;
  	static int signum(double x){
  		return x<-EPS?-1:x>EPS?1:0;
  	}
  	public P p1,p2;
  	AL(P _p1,P _p2){
  		p1=_p1;
  		p2=_p2;
  	}
   
  	boolean isPoint(){
  		return p1.equals(p2);
  	}
   
  //	public double a(){
  //		P dir= p2.sub(p1);
  //		return dir.y/dir.x;
  //	}
  //	public double b(){
  //		return P.cross(p1,p2)/(p1.x-p2.x);
  //	}
   
  	//平行
  	boolean isParallel(AL l){
  		return abs(P.cross(p2.sub(p1),l.p2.sub(l.p1)))<EPS;
  	}
  	//直交
  	boolean isOrthogonal(AL l){
  		return abs(P.dot(p2.sub(p1),l.p2.sub(l.p1)))<EPS;
  	}
   
  	//交点 (交差判定なし)
  	static P intersection(AL l1,AL l2){
  		P dl1=l1.p2.sub(l1.p1),dl2=l2.p2.sub(l2.p1);
  		double a=P.cross(dl2,l2.p1.sub(l1.p1));
  		double b=P.cross(dl2,dl1);
  		if(abs(a)<EPS && abs(b) <EPS)return l1.p1;//same
  		return l1.p1.add(dl1.mul(new P(a/b,0.0)));
  	}
   
   
  	public boolean equals(Object obj) {
  		if(obj instanceof L){
  			L l=(L)obj;
  			return this.p1.equals(l.p1) && this.p2.equals(l.p2);
  		}
  		return false;
  	}
  	public String toString(){
  		return p1+"-"+p2;
  	}
  }