问题C:如何检测两条线段是否相交?

我也搜索过同样的话题，但我对答案并不满意。所以我写了一篇文章，非常详细地解释了如何检查两条线段是否与大量图像相交。这是完整的(并经过测试的)java代码。

以下是这篇文章，截取了最重要的部分:

检查线段a是否与线段b相交的算法如下所示:

什么是边界框?下面是两个线段的边界框:

如果两个边界框都有交点，则移动线段a，使其中一点在(0|0)处。现在你有了一条经过a定义的原点的直线，现在以同样的方式移动线段b，检查线段b的新点是否在直线a的不同两侧。如果是这样，则反过来检查。如果也是这样，线段相交。如果不相交，它们就不相交。

问题A:两条线段在哪里相交?

你知道两条线段a和b相交。如果你不知道，用我在C题中给你的工具检查一下。

现在你可以通过一些情况，并得到解决与七年级数学(见代码和交互示例)。

问题B:你如何检测两条线是否相交?

假设点A = (x1, y1)点B = (x2, y2) C = (x_3, y_3) D = (x_4, y_4) 第一行由AB定义(A != B)，第二行由CD定义(C != D)。

function doLinesIntersect(AB, CD) {
    if (x1 == x2) {
        return !(x3 == x4 && x1 != x3);
    } else if (x3 == x4) {
        return true;
    } else {
        // Both lines are not parallel to the y-axis
        m1 = (y1-y2)/(x1-x2);
        m2 = (y3-y4)/(x3-x4);
        return m1 != m2;
    }
}

问题D:两条直线在哪里相交?

检查问题B，它们是否相交。

直线a和b由每条直线上的两个点定义。 你基本上可以用和问题A相同的逻辑。

根据t3chb0t的答案:

int intersezione_linee(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
   //L1: estremi (x1,y1)(x2,y2) L2: estremi (x3,y3)(x3,y3)
   int d;
   d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
   if(!d)
       return 0;
   p_x = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d;
   p_y = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d;
   return 1;
}

int in_bounding_box(int x1, int y1, int x2, int y2, int p_x, int p_y)
{
    return p_x>=x1 && p_x<=x2 && p_y>=y1 && p_y<=y2;

}

int intersezione_segmenti(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
    if (!intersezione_linee(x1,y1,x2,y2,x3,y3,x4,y4,p_x,p_y))
        return 0;

    return in_bounding_box(x1,y1,x2,y2,p_x,p_y) && in_bounding_box(x3,y3,x4,y4,p_x,p_y);
}

我认为这个问题有一个更简单的解决方案。今天我想到了另一个想法，看起来效果不错(至少在2D中)。你所要做的就是计算两条直线的交点，然后检查计算的交点是否在两条线段的边界框内。如果是，两条线段相交。就是这样。

编辑:

这就是我如何计算交集(我不知道我在哪里找到了这个代码片段)

Point3D

来自

System.Windows.Media.Media3D

public static Point3D? Intersection(Point3D start1, Point3D end1, Point3D start2, Point3D end2) {

        double a1 = end1.Y - start1.Y;
        double b1 = start1.X - end1.X;
        double c1 = a1 * start1.X + b1 * start1.Y;

        double a2 = end2.Y - start2.Y;
        double b2 = start2.X - end2.X;
        double c2 = a2 * start2.X + b2 * start2.Y;

        double det = a1 * b2 - a2 * b1;
        if (det == 0) { // lines are parallel
            return null;
        }

        double x = (b2 * c1 - b1 * c2) / det;
        double y = (a1 * c2 - a2 * c1) / det;

        return new Point3D(x, y, 0.0);
    }

这是我的BoundingBox类(为了回答的目的而简化):

public class BoundingBox {
    private Point3D min = new Point3D();
    private Point3D max = new Point3D();

    public BoundingBox(Point3D point) {
        min = point;
        max = point;
    }

    public Point3D Min {
        get { return min; }
        set { min = value; }
    }

    public Point3D Max {
        get { return max; }
        set { max = value; }
    }

    public bool Contains(BoundingBox box) {
        bool contains =
            min.X <= box.min.X && max.X >= box.max.X &&
            min.Y <= box.min.Y && max.Y >= box.max.Y &&
            min.Z <= box.min.Z && max.Z >= box.max.Z;
        return contains;
    }

    public bool Contains(Point3D point) {
        return Contains(new BoundingBox(point));
    }

}

只是想提一下，一个很好的解释和明确的解决方案可以在数字食谱系列中找到。我有这本书的第三版，答案在1117页21.4节。另一种不同命名的解决方案可以在玛丽娜·加夫里洛娃(Marina Gavrilova)的论文中找到。在我看来，她的解决办法要简单一些。

我的实现如下:

bool NuGeometry::IsBetween(const double& x0, const double& x, const double& x1){
   return (x >= x0) && (x <= x1);
}

bool NuGeometry::FindIntersection(const double& x0, const double& y0, 
     const double& x1, const double& y1,
     const double& a0, const double& b0, 
     const double& a1, const double& b1, 
     double& xy, double& ab) {
   // four endpoints are x0, y0 & x1,y1 & a0,b0 & a1,b1
   // returned values xy and ab are the fractional distance along xy and ab
   // and are only defined when the result is true

   bool partial = false;
   double denom = (b0 - b1) * (x0 - x1) - (y0 - y1) * (a0 - a1);
   if (denom == 0) {
      xy = -1;
      ab = -1;
   } else {
      xy = (a0 * (y1 - b1) + a1 * (b0 - y1) + x1 * (b1 - b0)) / denom;
      partial = NuGeometry::IsBetween(0, xy, 1);
      if (partial) {
         // no point calculating this unless xy is between 0 & 1
         ab = (y1 * (x0 - a1) + b1 * (x1 - x0) + y0 * (a1 - x1)) / denom; 
      }
   }
   if ( partial && NuGeometry::IsBetween(0, ab, 1)) {
      ab = 1-ab;
      xy = 1-xy;
      return true;
   }  else return false;
}

这个解决方案可能会有所帮助

public static float GetLineYIntesept(PointF p, float slope)
    {
        return p.Y - slope * p.X;
    }

    public static PointF FindIntersection(PointF line1Start, PointF line1End, PointF line2Start, PointF line2End)
    {

        float slope1 = (line1End.Y - line1Start.Y) / (line1End.X - line1Start.X);
        float slope2 = (line2End.Y - line2Start.Y) / (line2End.X - line2Start.X);

        float yinter1 = GetLineYIntesept(line1Start, slope1);
        float yinter2 = GetLineYIntesept(line2Start, slope2);

        if (slope1 == slope2 && yinter1 != yinter2)
            return PointF.Empty;

        float x = (yinter2 - yinter1) / (slope1 - slope2);

        float y = slope1 * x + yinter1;

        return new PointF(x, y);
    }

有一个很好的方法来解决这个问题就是用向量叉乘。定义二维向量叉乘v × w为vx wy−vy wx。

假设这两条线段从p到p + r，从q到q + s。那么第一行上的任意点都可以表示为p + t r(对于标量参数t)，第二行上的任意点可以表示为q + u s(对于标量参数u)。

如果t和u满足以下条件，两条直线相交:

P + t r = q + u s

两边叉乘s，得到

(p + r) × s = (q + u s) × s

由于s × s = 0，这意味着

T (r × s) = (q−p) × s

因此，求解t:

T = (q−p) × s / (r × s)

同样地，我们可以解出u:

(p + r) × r = (q + u s) × r U (s × r) = (p−q) × r U = (p−q) × r / (s × r)

为了减少计算步骤，可以方便地将其重写为以下形式(记住s × r =−r × s):

U = q−p × r / (r × s)

现在有四种情况:

If r × s = 0 and (q − p) × r = 0, then the two lines are collinear. In this case, express the endpoints of the second segment (q and q + s) in terms of the equation of the first line segment (p + t r): t0 = (q − p) · r / (r · r) t1 = (q + s − p) · r / (r · r) = t0 + s · r / (r · r) If the interval between t0 and t1 intersects the interval [0, 1] then the line segments are collinear and overlapping; otherwise they are collinear and disjoint. Note that if s and r point in opposite directions, then s · r < 0 and so the interval to be checked is [t1, t0] rather than [t0, t1]. If r × s = 0 and (q − p) × r ≠ 0, then the two lines are parallel and non-intersecting. If r × s ≠ 0 and 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, the two line segments meet at the point p + t r = q + u s. Otherwise, the two line segments are not parallel but do not intersect.

来源:该方法是3D线相交算法的2维专门化，来自Ronald Goldman发表在Graphics Gems，第304页的文章“三条线在三维空间中的相交”。在三维空间中，通常的情况是直线是倾斜的(既不平行也不相交)，在这种情况下，该方法给出了两条直线最接近的点。