我如何确定两条直线是否相交,如果相交,在x,y点处?


当前回答

上面有很多解决方案,但我认为下面的解决方案很简单,很容易理解。

矢量AB和矢量CD相交当且仅当

端点a和b在线段CD的两边。 端点c和d在线段AB的对边。

更具体地说,a和b在线段CD的对面当且仅当两个三元组中有一个是逆时针顺序的。

Intersect(a, b, c, d)
 if CCW(a, c, d) == CCW(b, c, d)
    return false;
 else if CCW(a, b, c) == CCW(a, b, d)
    return false;
 else
    return true;

这里的CCW代表逆时针,根据点的方向返回真/假。

来源:http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf 第二页

其他回答

iMalc回答的Python版本:

def find_intersection( p0, p1, p2, p3 ) :

    s10_x = p1[0] - p0[0]
    s10_y = p1[1] - p0[1]
    s32_x = p3[0] - p2[0]
    s32_y = p3[1] - p2[1]

    denom = s10_x * s32_y - s32_x * s10_y

    if denom == 0 : return None # collinear

    denom_is_positive = denom > 0

    s02_x = p0[0] - p2[0]
    s02_y = p0[1] - p2[1]

    s_numer = s10_x * s02_y - s10_y * s02_x

    if (s_numer < 0) == denom_is_positive : return None # no collision

    t_numer = s32_x * s02_y - s32_y * s02_x

    if (t_numer < 0) == denom_is_positive : return None # no collision

    if (s_numer > denom) == denom_is_positive or (t_numer > denom) == denom_is_positive : return None # no collision


    # collision detected

    t = t_numer / denom

    intersection_point = [ p0[0] + (t * s10_x), p0[1] + (t * s10_y) ]


    return intersection_point

上面有很多解决方案,但我认为下面的解决方案很简单,很容易理解。

矢量AB和矢量CD相交当且仅当

端点a和b在线段CD的两边。 端点c和d在线段AB的对边。

更具体地说,a和b在线段CD的对面当且仅当两个三元组中有一个是逆时针顺序的。

Intersect(a, b, c, d)
 if CCW(a, c, d) == CCW(b, c, d)
    return false;
 else if CCW(a, b, c) == CCW(a, b, d)
    return false;
 else
    return true;

这里的CCW代表逆时针,根据点的方向返回真/假。

来源:http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf 第二页

人们似乎对Gavin的答案很感兴趣,cortijon在评论中提出了一个javascript版本,iMalc提供了一个计算量略少的版本。一些人指出了各种代码建议的缺点,另一些人则评论了一些代码建议的效率。

iMalc通过Gavin的答案提供的算法是我目前在一个javascript项目中使用的算法,我只是想在这里提供一个清理过的版本,如果它可以帮助到任何人的话。

// Some variables for reuse, others may do this differently
var p0x, p1x, p2x, p3x, ix,
    p0y, p1y, p2y, p3y, iy,
    collisionDetected;

// do stuff, call other functions, set endpoints...

// note: for my purpose I use |t| < |d| as opposed to
// |t| <= |d| which is equivalent to 0 <= t < 1 rather than
// 0 <= t <= 1 as in Gavin's answer - results may vary

var lineSegmentIntersection = function(){
    var d, dx1, dx2, dx3, dy1, dy2, dy3, s, t;

    dx1 = p1x - p0x;      dy1 = p1y - p0y;
    dx2 = p3x - p2x;      dy2 = p3y - p2y;
    dx3 = p0x - p2x;      dy3 = p0y - p2y;

    collisionDetected = 0;

    d = dx1 * dy2 - dx2 * dy1;

    if(d !== 0){
        s = dx1 * dy3 - dx3 * dy1;
        if((s <= 0 && d < 0 && s >= d) || (s >= 0 && d > 0 && s <= d)){
            t = dx2 * dy3 - dx3 * dy2;
            if((t <= 0 && d < 0 && t > d) || (t >= 0 && d > 0 && t < d)){
                t = t / d;
                collisionDetected = 1;
                ix = p0x + t * dx1;
                iy = p0y + t * dy1;
            }
        }
    }
};

我从《多视图几何》这本书里读到了这些算法

以下文本使用

'作为转置符号

*作为点积

当用作算子时,X作为叉乘

1. 线的定义

点x_vec = (x, y)'在直线ax + by + c = 0上

标记L = (a, b, c)',点为(x, y, 1)'为齐次坐标

直线方程可以写成

(x, y, 1)(a, b, c)' = 0或x' * L = 0

2. 直线交点

我们有两条直线L1=(a1, b1, c1)', L2=(a2, b2, c2)'

假设x是一个点,一个向量,x = L1 x L2 (L1叉乘L2)。

注意,x始终是一个二维点,如果你对(L1xL2)是一个三元素向量,x是一个二维坐标感到困惑,请阅读齐次坐标。

根据三重积,我们知道

L1 * (L1 x L2) = 0, L2 * (L1 x L2) = 0,因为L1,L2共平面

我们用向量x代替L1*x,那么L1*x=0, L2*x=0,这意味着x在L1和L2上,x是交点。

注意,这里x是齐次坐标,如果x的最后一个元素是零,这意味着L1和L2是平行的。

C和Objective-C

基于Gareth Rees的回答

const AGKLine AGKLineZero = (AGKLine){(CGPoint){0.0, 0.0}, (CGPoint){0.0, 0.0}};

AGKLine AGKLineMake(CGPoint start, CGPoint end)
{
    return (AGKLine){start, end};
}

double AGKLineLength(AGKLine l)
{
    return CGPointLengthBetween_AGK(l.start, l.end);
}

BOOL AGKLineIntersection(AGKLine l1, AGKLine l2, CGPoint *out_pointOfIntersection)
{
    // http://stackoverflow.com/a/565282/202451

    CGPoint p = l1.start;
    CGPoint q = l2.start;
    CGPoint r = CGPointSubtract_AGK(l1.end, l1.start);
    CGPoint s = CGPointSubtract_AGK(l2.end, l2.start);
    
    double s_r_crossProduct = CGPointCrossProductZComponent_AGK(r, s);
    double t = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), s) / s_r_crossProduct;
    double u = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), r) / s_r_crossProduct;
    
    if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
    {
        if(out_pointOfIntersection != NULL)
        {
            *out_pointOfIntersection = CGPointZero;
        }
        return NO;
    }
    else
    {
        if(out_pointOfIntersection != NULL)
        {
            CGPoint i = CGPointAdd_AGK(p, CGPointMultiply_AGK(r, t));
            *out_pointOfIntersection = i;
        }
        return YES;
    }
}

CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

CGPoint CGPointSubtract_AGK(CGPoint p1, CGPoint p2)
{
    return (CGPoint){p1.x - p2.x, p1.y - p2.y};
}

CGPoint CGPointAdd_AGK(CGPoint p1, CGPoint p2)
{
    return (CGPoint){p1.x + p2.x, p1.y + p2.y};
}

CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

CGPoint CGPointMultiply_AGK(CGPoint p1, CGFloat factor)
{
    return (CGPoint){p1.x * factor, p1.y * factor};
}

许多函数和结构都是私有的,但是你应该很容易就能知道发生了什么。 这是公开的在这个回购https://github.com/hfossli/AGGeometryKit/