objective-c判断两条线段相交

参考自：http://zhidao.baidu.com/question/146717333

LineIntersect.h

//
//  LineIntersect.h
//  HungryBear
//
//  Created by Bruce Yang on 12-3-12.
//  Copyright (c) 2012年 EricGameStudio. All rights reserved.
//

#import <cstdio>
#import "Box2D.h"

#define zero(x) (((x)>0?(x):-(x))<b2_epsilon)

@interface LineIntersect : NSObject

#pragma mark-
#pragma mark 适用于 b2Vec2 的版本~


// 判两线段相交,包括端点和部分重合
+(int) intersect_in:(b2Vec2)u1 u2:(b2Vec2)u2 v1:(b2Vec2)v1 v2:(b2Vec2)v2;


// 计算两线段交点,请判线段是否相交(同时还是要判断是否平行!)
+(b2Vec2) intersection:(b2Vec2)u1 u2:(b2Vec2)u2 v1:(b2Vec2)v1 v2:(b2Vec2)v2;

#pragma mark-
#pragma mark 适用于 CGPoint 的版本~


+(int) intersect_in2:(CGPoint)u1 u2:(CGPoint)u2 v1:(CGPoint)v1 v2:(CGPoint)v2;


// 计算两线段交点,请判线段是否相交(同时还是要判断是否平行!)
+(CGPoint) intersection2:(CGPoint)u1 u2:(CGPoint)u2 v1:(CGPoint)v1 v2:(CGPoint)v2;

#pragma mark-
#pragma mark 验证上述几个方法的移植是否存在什么问题~


+(void) validateAlgorithm;

@end

LineIntersect.mm

//
//  LineIntersect.mm
//  HungryBear
//
//  Created by Bruce Yang on 12-3-12.
//  Copyright (c) 2012年 EricGameStudio. All rights reserved.
//

#import "LineIntersect.h"

@implementation LineIntersect


// 计算交叉乘积 (P1-P0)x(P2-P0)
+(double) xmult:(b2Vec2)p1 p2:(b2Vec2)p2 p3:(b2Vec2)p0 {
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

// 判点是否在线段上,包括端点
+(int) dot_online_in:(b2Vec2)p l1:(b2Vec2)l1 l2:(b2Vec2)l2 {
    return zero([self xmult:p p2:l1 p3:l2]) && 
            (l1.x-p.x)*(l2.x-p.x) < b2_epsilon && 
            (l1.y-p.y)*(l2.y-p.y) < b2_epsilon;
}

// 判两点在线段同侧,点在线段上返回0
+(int) same_side:(b2Vec2)p1 p2:(b2Vec2)p2 l1:(b2Vec2)l1 l2:(b2Vec2)l2 {
    return [self xmult:l1 p2:p1 p3:l2] * [self xmult:l1 p2:p2 p3:l2] > b2_epsilon;
}

// 判两直线平行
+(int) parallel:(b2Vec2)u1 u2:(b2Vec2)u2 v1:(b2Vec2)v1 v2:(b2Vec2)v2 {
    return zero((u1.x-u2.x)*(v1.y-v2.y)-(v1.x-v2.x)*(u1.y-u2.y));
}

// 判三点共线
+(int) dots_inline:(b2Vec2)p1 p2:(b2Vec2)p2 p3:(b2Vec2)p3 {
    return zero([self xmult:p1 p2:p2 p3:p3]);
}

// 判两线段相交,包括端点和部分重合
+(int) intersect_in:(b2Vec2)u1 u2:(b2Vec2)u2 v1:(b2Vec2)v1 v2:(b2Vec2)v2 {
    if (![self dots_inline:u1 p2:u2 p3:v1] || ![self dots_inline:u1 p2:u2 p3:v2]) {
        return ![self same_side:u1 p2:u2 l1:v1 l2:v2] && ![self same_side:v1 p2:v2 l1:u1 l2:u2];
    } else {
        return [self dot_online_in:u1 l1:v1 l2:v2] || 
                [self dot_online_in:u2 l1:v1 l2:v2] || 
                [self dot_online_in:v1 l1:u1 l2:u2] || 
                [self dot_online_in:v2 l1:u1 l2:u2];
    } 
}


// 计算两线段交点,请判线段是否相交(同时还是要判断是否平行!)
+(b2Vec2) intersection:(b2Vec2)u1 u2:(b2Vec2)u2 v1:(b2Vec2)v1 v2:(b2Vec2)v2 {
    b2Vec2 ret=u1;
    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
    /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x+=(u2.x-u1.x)*t;
    ret.y+=(u2.y-u1.y)*t;
    return ret;
}


#pragma mark-
#pragma mark 适用于 CGPoint 的版本~

// 计算交叉乘积 (P1-P0)x(P2-P0)
+(double) xmult2:(CGPoint)p1 p2:(CGPoint)p2 p3:(CGPoint)p0 {
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

// 判点是否在线段上,包括端点
+(int) dot_online_in2:(CGPoint)p l1:(CGPoint)l1 l2:(CGPoint)l2 {
    return zero([self xmult2:p p2:l1 p3:l2]) && 
    (l1.x-p.x)*(l2.x-p.x) < b2_epsilon && 
    (l1.y-p.y)*(l2.y-p.y) < b2_epsilon;
}

// 判两点在线段同侧,点在线段上返回0
+(int) same_side2:(CGPoint)p1 p2:(CGPoint)p2 l1:(CGPoint)l1 l2:(CGPoint)l2 {
    return [self xmult2:l1 p2:p1 p3:l2] * [self xmult2:l1 p2:p2 p3:l2] > b2_epsilon;
}

// 判两直线平行
+(int) parallel2:(CGPoint)u1 u2:(CGPoint)u2 v1:(CGPoint)v1 v2:(CGPoint)v2 {
    return zero((u1.x-u2.x)*(v1.y-v2.y)-(v1.x-v2.x)*(u1.y-u2.y));
}

// 判三点共线
+(int) dots_inline2:(CGPoint)p1 p2:(CGPoint)p2 p3:(CGPoint)p3 {
    return zero([self xmult2:p1 p2:p2 p3:p3]);
}

+(int) intersect_in2:(CGPoint)u1 u2:(CGPoint)u2 v1:(CGPoint)v1 v2:(CGPoint)v2 {
    if (![self dots_inline2:u1 p2:u2 p3:v1] || ![self dots_inline2:u1 p2:u2 p3:v2]) {
        return ![self same_side2:u1 p2:u2 l1:v1 l2:v2] && ![self same_side2:v1 p2:v2 l1:u1 l2:u2];
    } else {
        return [self dot_online_in2:u1 l1:v1 l2:v2] || 
        [self dot_online_in2:u2 l1:v1 l2:v2] || 
        [self dot_online_in2:v1 l1:u1 l2:u2] || 
        [self dot_online_in2:v2 l1:u1 l2:u2];
    } 
}


// 计算两线段交点,请判线段是否相交(同时还是要判断是否平行!)
+(CGPoint) intersection2:(CGPoint)u1 u2:(CGPoint)u2 v1:(CGPoint)v1 v2:(CGPoint)v2 {
    CGPoint ret=u1;
    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
    /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x+=(u2.x-u1.x)*t;
    ret.y+=(u2.y-u1.y)*t;
    return ret;
}


#pragma mark-
#pragma mark 验证上述几个方法的移植是否存在什么问题~

+(void) validateIntersect:(b2Vec2)u1 u2:(b2Vec2)u2 v1:(b2Vec2)v1 v2:(b2Vec2)v2 {
    b2Vec2 answer;
    if ([self parallel:u1 u2:u2 v1:v1 v2:v2] || ![self intersect_in:u1 u2:u2 v1:v1 v2:v2]){
        printf("无交点!\n");
    } else {
        answer = [self intersection:u1 u2:u2 v1:v1 v2:v2];
        printf("交点为:(%lf,%lf)\n", answer.x, answer.y);
    }
}

+(void) validateAlgorithm {
    [LineIntersect validateIntersect:b2Vec2(0, 1) u2:b2Vec2(1, 0) v1:b2Vec2(0, 0) v2:b2Vec2(1, 1)];
    [LineIntersect validateIntersect:b2Vec2(0, 10) u2:b2Vec2(10, 0) v1:b2Vec2(0, 0) v2:b2Vec2(10, 10)];
    [LineIntersect validateIntersect:b2Vec2(-2, 0) u2:b2Vec2(2, 0) v1:b2Vec2(-1, 3) v2:b2Vec2(-1, -1)];
    [LineIntersect validateIntersect:b2Vec2(-2, 0) u2:b2Vec2(2, 0) v1:b2Vec2(-1, 3) v2:b2Vec2(1, -2)];
}


@end

再提供一个判断两直线相交的方法，与上对比貌似更加高效一些~

/**
 * 判断两条线段是否相交，参见如下链接：
 * http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
 */
+(bool) checkLineIntersection:(b2Vec2)p1 :(b2Vec2)p2 :(b2Vec2)p3 :(b2Vec2)p4 {
    CGFloat denominator = (p4.y - p3.y) * (p2.x - p1.x) - (p4.x - p3.x) * (p2.y - p1.y);
    
    // In this case the lines are parallel so we assume they don't intersect~
    if(denominator == 0.0f) {
        return false;
    }
    
    CGFloat ua = ((p4.x - p3.x) * (p1.y - p3.y) - (p4.y - p3.y) * (p1.x - p3.x)) / denominator;
    CGFloat ub = ((p2.x - p1.x) * (p1.y - p3.y) - (p2.y - p1.y) * (p1.x - p3.x)) / denominator;
    
    if(ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) {
        return true;
    }
    return false;
}