判断线段相交

刚刚开始接触计算几何.. 之前按自己的思路写了一个线段相交却怎么也过不了某题..

最后发现果然还是自己智商拙计= =..

线段a, b相交的充要条件是:  a 叉积 b 的两个端点之积为负, b 叉积 a 的两个端点之积为负数, 而且两线段不平行.

下面给出部分代码.

bool Parallel(Point a, Point b, Point c, Point d) {return !dcmp(a.cross(b, a + d - c));}

bool SegCross(Point& a, Point& b, Point& c, Point& d)
{
    //一定要判断是否平行!
    if( !Parallel(a, b, c, d) && a.cross(b, c) * a.cross(b, d) <= 0 && c.cross(d, a) * c.cross(d, b) <= 0)
        return true;
    return false;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>