hdu 1086 判断两线段是否相交 （线段和直接是否相交

若是判断直线和线段是否有交点，把on_segment去掉就可以了

　　判断两线段是否相交：

　　我们分两步确定两条线段是否相交：

　　(1)快速排斥试验

　　　　设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。

　　(2)跨立试验

　　　　如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0。具体情况如下图所示：

    

　　在相同的原理下，对此算法的具体的实现细节可能会与此有所不同，除了这种过程外，大家也可以参考《算法导论》上的实现。

关于计算几何算法概述网站 http://dev.gameres.com/Program/Abstract/Geometry.htm 一个挺好的网站

 

 

#include<stdio.h>//判断线段相交模版

struct point
{
    double x,y;
};

double direction( point p1,point p2,point p )
{
    //叉乘符号，向量a(x1,y1)×向量b(x2,y2)=x1*y2-x2*y1;
    return ( p1.x -p.x )*( p2.y-p.y) -  ( p2.x -p.x )*( p1.y-p.y)  ;
}

int on_segment( point p1,point p2 ,point p )
{
    double max=p1.x > p2.x ? p1.x : p2.x ;
    double min =p1.x < p2.x ? p1.x : p2.x ;

    if( p.x >=min && p.x <=max )
        return 1;
    else
        return 0;
}

int segments_intersert( point p1,point p2,point p3,point p4 )
{
    double d1,d2,d3,d4;
    //判断p3和p4是否在p1和p2两侧
    d1 = direction ( p1,p2,p3 );
    d2 = direction ( p1,p2,p4 );
    //判断p1和p2是否在p3和p4两侧
    d3 = direction ( p3,p4,p1 );
    d4 = direction ( p3,p4,p2 );
    if( d1*d2<0 && d3*d4<0 )//在两侧，说明p1p2和p3p4相交
        return 1;
    else if( d1==0 && on_segment( p1,p2,p3 ) )
        return 1;
    else if( d2==0 && on_segment( p1,p2,p4 ) )
        return 1;
    else if( d3==0 && on_segment( p3,p4,p1 ) )
        return 1;
    else if( d4==0 && on_segment( p3,p4,p2 ) )
        return 1;

    return 0;
}

int main()
{
    int n,i,j,num;
    point begin[105],end[105];  //结构体数组

    while(scanf("%d",&n)&&n!=0 )
    {
        num=0;
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&begin[i].x ,&begin[i].y ,&end[i].x ,&end[i].y );
        }
        for(i=0;i<n;i++)//线段两两比较
        {
            for(j=i+1;j<n;j++)
            {
                if( segments_intersert( begin[i],end[i],begin[j],end[j] ) )
                    num++;
            }
        }
        printf("%d\n",num);
    }
    return 0;
}

 

 

几何，哥哥要征服你，fighting！