6

可能重复：
如何检测两条线段相交的位置？
确定两条线段是否相交？

给定两行 l1=((A0, B0), (A1, B1)) 和 l2=((A2, B2), (A3, B3)); Ax, Bx 是整数，(Ax, Bx) 指定行的开始和结束。

是否有一种仅使用整数算术来确定 l1 和 l2 是否相交的算法？（只需要一个布尔答案。）

我自己的方法是用定点算法计算交点附近的一个点。然后将解 (a, b) 代入以下方程：

I: abs((A0 + a * (A1-A0)) - (A2 + b * (A3-A2))) < 公差
II: abs((B0 + a * (B1-B0)) - (B2 + b * (B3-B2))) < 公差

如果 I 和 II 都评估为 true，我的方法应该返回 true。

我的 C++ 代码：
vec.h：

#ifndef __MY_VECTOR__
#define __MY_VECTOR__
#include <stdarg.h>
template<typename VType, unsigned int dim>
class vec {
private:
    VType data[dim];
public:
    vec(){}
    vec(VType v0, ...){
            data[0] = v0;
            va_list l;
            va_start(l, v0);
            for(unsigned int i=1; i<dim; ++i){
                    data[i] = va_arg(l, VType);
            }
            va_end(l);
    }
    ~vec(){}
    VType& operator[](unsigned int i){
            return data[i];
    }
    VType operator[](unsigned int i) const {
            return data[i];
    }};
    template<typename VType, unsigned int dim, bool doDiv>
    vec<VType, dim> helpArith1(const vec<VType, dim>& A, long delta){
            vec<VType, dim> r(A);
            for(unsigned int i=0; i<dim; ++i){
                    r[i] = doDiv ? (r[i] / delta) : (r[i] * delta);
            }
            return r;
    }
    template<typename VType, unsigned int dim>
    vec<VType, dim> operator*(const vec<VType, dim>& v, long delta) {
        return helpArith1<VType, dim, false>(A, delta);
    }
    template<typename VType, unsigned int dim>
    vec<VType, dim> operator*(long delta, const vec<VType, dim>& v){
        return v * delta;
    }
    template<typename VType,unsigned int dim>
    vec<VType, dim> operator/(const vec<VType, dim>& A, long delta) {
        return helpArith1<VType, dim, true>(A, delta);
    }
    template<typename VType, unsigned int dim, bool doSub>
    vec<VType, dim> helpArith2(const vec<VType, dim>& A, const vec<VType, dim>& B){
        vec<VType, dim> r;
        for(unsigned int i=0; i<dim; ++i){
            r[i] = doSub ? (A[i]-B[i]):(A[i]+B[i]);
        }
        return r;
    }
    template<typename VType, unsigned int dim>
    vec<VType, dim> operator+(const vec<VType, dim>& A, const vec<VType, dim>& B){
        return helpArith2<VType, dim, false>(A, B);
    }
    template<typename VType, unsigned int dim>
    vec<VType, dim> operator-(const vec<VType, dim>& A, const vec<VType, dim>& B){
        return helpArith2<VType, dim, true>(A, B);
    }
    template<typename VType, unsigned int dim>
    bool operator==(const vec<VType, dim>& A, const vec<VType, dim>& B) {
            for(unsigned int i==0; i<dim; ++i){
                if(A[i]!=B[i]){
                            return false;
                    }
            }
            return true;
    }
    template<typename VType, unsigned int dim>
    bool operator!=(const vec<VType, dim>& A, const vec<VType, dim>& B) {
            return !(A==B);
    }
    #endif


线.h：

#ifndef __MY_LINE__
#define __MY_LINE__
#include "vec.h"
unsigned long int ggt(unsigned long int A, unsigned long int B) {
    if(A==0) {
        if(B==0) {
            return 1;
        }
        return B;
    }
    while(B!=0) {
        unsigned long int temp = A % B;
        A = B;
        B = temp;
    }
    return A;
}
#define ABS(n) ( ((n)<0) ? (-n) : (n) )
struct line {
    vec<long int, 2> A, B;
    explicit line(long int iA_0, long int iA_1, long int iB_0, long int iB_1) :
        A(vec<long int, 2>(iA_0<<8, iA_1<<8)),
        B(vec<long int, 2>(iB_0<<8, iB_1<<8)){}
    vec<long int, 2> slope() const{
        vec<long int, 2> temp = A-B;
        if(temp[0]<0) {
            temp[0] = -1 * temp[0];
            temp[1] = -1 * temp[1];
        }
        return temp/ggt(ABS(temp[0]), ABS(temp[1]));
    }
};
bool intersect(line l1, line l2) {
    const long int epsilon = 1<<4;
    vec<long int, 2> sl1 = l1.slope(), sl2 = l2.slope();
    // l2.A + b*sl2 = l1.A + a*sl1
    // <=> l2.A - l1.A = a*sl1 - b*sl2  // = (I, II)^T
    // I': sl2[1] * I; II': sl2[0] * II
    vec<long int, 2> L = l2.A - l1.A, R = sl1;
    L[0] = L[0] * sl2[1];        R[0] = R[0] * sl2[1];
    L[1] = L[1] * sl2[0];        R[1] = R[1] * sl2[0];
    // I' - II'
    long int L_SUB = L[0] - L[1], R_SUB = R[0] - R[1];
    if(ABS(R_SUB) == 0) {
        return ABS(L_SUB) == 0;
    }
    long int temp = ggt(ABS(L_SUB), ABS(R_SUB));
    L_SUB /= temp; R_SUB /= temp;
    // R_SUB * a = L_SUB
    long int a = L_SUB/R_SUB, b = ((l1.A[0] - l2.A[0])*R_SUB + L_SUB * sl1[0])/R_SUB;
    // if the given lines intersect, then {a, b} must be the solution of
    // l2.A - l1.A = a*sl1 - b*sl2
    L = l2.A - l1.A;
    long x = ABS((L[0]- (a*sl1[0]-b*sl2[0]))), y = ABS((L[1]- (a*sl1[1]-b*sl2[1])));
    return x<epsilon && y < epsilon;
}
#endif


主.cpp：

#include "line.h"
int main(){
    line A(0, 0, 6, 0), B(3, 3, 4, -3);
    bool temp = intersect(A, B);
    return 0;
}

（我不确定我的 intersect 函数是否适用于所有行，但是根据我迄今为止使用的测试数据，它返回了正确的结果。）

4

2 回答 2

18

这个有可能。我们要检查 l1 的两个端点是否在 l2 的不同边上，并且 l2 的两个端点都在 l1 的相对边上。

为了检查点 (A, B) 位于 l1=((A0, B0), (A1, B1)) 的哪一侧，我们采取：

  • 垂直于线的任意法线向量 N；一个这样的向量是 (B1-B0, A1-A0)
  • 从线的起点到点 (A, B) 的向量 P，即 (A-A0, B-B0)

然后我们计算点积：

N · P = (A-A0, B-B0) · (B1-B0, A1-A0) = (A-A0) * (B1-B0) + (B-B0) * (A1-A0)

我们只对符号感兴趣：如果它是正数，则该点位于线的一侧；如果它是负面的，它在另一个。如您所见，不需要浮点运算。

我们可以利用这样一个事实，即具有相反符号的数字在相乘时总是产生负数。所以判断两条线段（（A0，B0），（A1，B1））和（（A2，B2），（A3，B3））是否相交的完整表达式是：

((A2-A0)*(B1-B0) - (B2-B0)*(A1-A0)) * ((A3-A0)*(B1-B0) - (B3-B0)*(A1-A0)) < 0
&&
((A0-A2)*(B3-B2) - (B0-B2)*(A3-A2)) * ((A1-A2)*(B3-B2) - (B1-B2)*(A3-A2)) < 0

测试代码

一些 C++ 代码来测试上述计算：

#include <iostream>
#include <cstdlib>

struct Point {
    int x,y;
};

bool isIntersecting(Point& p1, Point& p2, Point& q1, Point& q2) {
    return (((q1.x-p1.x)*(p2.y-p1.y) - (q1.y-p1.y)*(p2.x-p1.x))
            * ((q2.x-p1.x)*(p2.y-p1.y) - (q2.y-p1.y)*(p2.x-p1.x)) < 0)
            &&
           (((p1.x-q1.x)*(q2.y-q1.y) - (p1.y-q1.y)*(q2.x-q1.x))
            * ((p2.x-q1.x)*(q2.y-q1.y) - (p2.y-q1.y)*(q2.x-q1.x)) < 0);
}

int main(int argc, char* argv[]) {
    if(argc != 9) {
        std::cout << "Call as " << argv[0] << " <p1.x> <p1.y> <p2.x> "
                  << "<p2.y> <q1.x> <q1.y> <q2.x> <q2.y>" << std::endl;
        return -1;
    }

    Point p1 = {.x = atoi(argv[1]), .y = atoi(argv[2])};
    Point p2 = {.x = atoi(argv[3]), .y = atoi(argv[4])};
    Point q1 = {.x = atoi(argv[5]), .y = atoi(argv[6])};
    Point q2 = {.x = atoi(argv[7]), .y = atoi(argv[8])};

    if(isIntersecting(p1,p2,q1,q2)) {
        std::cout << "Segments intersect" << std::endl;
        return 1;
    }
    else {
        std::cout << "Segments do not intersect" << std::endl;
        return 0;
    }
}

结果：

$ ./intersection_test 0 0 10 10 0 10 10 0 # example from the comments
Segments intersect
$ ./intersection_test 0 1 2 1 1 2 1 0
Segments intersect
$ ./intersection_test 0 0 0 1 1 1 1 0
Segments do not intersect
$ ./intersection_test 1 1 5 3 3 4 7 2 # q touches but not intersects at p2
Segments do not intersect                             
$ ./intersection_test 1 1 5 3 3 4 6 2
Segments intersect
于 2013-01-05T22:24:53.727 回答
1

两条线段相交如果它们的线相交并且每条线段的端点在其他线段线的相对侧。至少在 2d 中。

两条线相交是二维中的一个简单问题。

点位于直线的哪一侧也很容易。

两者都不需要非整数数学。

对于一些通用几何代码，我会估计一打或三行，然后是 6 到 10 行的解决方案？加上语言样板。还有一些零长度的极端情况检查。

请注意，我将线与线段区分开来。

于 2013-01-05T22:07:21.357 回答