关于线段的一些算法

2009-02-05 14:54

线段所在直线（ms太简单）：
#include<iostream>
using namespace std;
struct point{
       double x,y;
};
struct line{
       double a,b,c;
};
int main(void){
    point p1,p2;
    line l1;
   
    cout<<"Input p1,p2:";
    cin>>p1.x>>p1.y>>p2.x>>p2.y;
   
    l1.a = p2.y-p1.y;
    l1.b = p1.x-p2.x;
    l1.c = p2.x*p1.y - p1.x*p2.y;
   
    cout<<"l:("<<l1.a<<")x+("<<l1.b<<")y+("<<l1.c<<")=0"<<endl;
   
    system("pause");
    return 0;
}
判断两线段是否相交（用叉积）：
#include<iostream>
using namespace std;
struct point{
       double x,y;
};
point operator-(point a,point b){
      point r;
      r.x = a.x - b.x;
      r.y = a.y - b.y;
     
      return r;
}
bool segment_intersect(point p1,point p2,point p3,point p4);//p1p2 & p3p4

double direction(point p1,point p2,point p);
bool on_segment(point p1,point p2,point p); //p on p1p2

double Max(double a,double b);
double Min(double a,double b);
int main(void){
    point p1,p2,p3,p4;
   
    cout<<"Input p1p2:";
    cin>>p1.x>>p1.y>>p2.x>>p2.y;
    cout<<"Input p3p4:";
    cin>>p3.x>>p3.y>>p4.x>>p4.y;
   
    if(segment_intersect(p1,p2,p3,p4) )
       cout<<"p1p2 intersects p3p4!"<<endl;
    else cout<<"p1p2 doesn't intersect p3p4!"<<endl;
   
    system("pause");
    return 0;
}
bool segment_intersect(point p1,point p2,point p3,point p4){
     double d1 = direction(p1,p2,p3);
     double d2 = direction(p1,p2,p4);
     double d3 = direction(p3,p4,p1);
     double d4 = direction(p3,p4,p2);
    
     if( ( (d1<0&&d2>0)||(d1>0&&d2<0) )&&
         ( (d3<0&&d4>0)||(d3>0&&d4<0) ) )
        return true;
    
     if(d1==0 && on_segment(p1,p2,p3) )
          return true;
     else if(d2==0 && on_segment(p1,p2,p4) )
          return true;
     else if(d3==0 && on_segment(p3,p4,p1) )
          return true;
     else if(d4==0 && on_segment(p3,p4,p2) )
          return true;
    
     return false;
}
double direction(point p1,point p2,point p){
       return (p2-p1).x*(p-p1).y -
              (p-p1).x*(p2-p1).y;
}
bool on_segment(point p1,point p2,point p){
     return 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);
}
double Max(double a,double b){
       return a>b?a:b;
}
   
double Min(double a,double b){
       return a<b?a:b;
}