java - 计算线段之间的交点

Question

在 stackowerflow 上有很多关于线段之间的交叉点的问题，这里还有一个问题!抱歉，但我需要帮助来了解如何计算交叉点。我已经阅读了这里的几个问题并查看了其他网站上的几个示例，但我仍然感到困惑并且不明白!我不喜欢在没有工作原理的情况下复制和粘贴代码。

到目前为止，我知道我将比较每个线段的点，例如 Ax、Ay、Bx、By、Cx、Cy、Dx、Dy。谁能帮我解释一下我要计算什么，如果有交叉点，计算的结果会是什么？

这是我看到的示例代码之一。我想我不需要相交点，只知道线是否相交。

   public static Point lineIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
  double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
  if (denom == 0.0) { // Lines are parallel.
     return null;
  }
  double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))/denom;
  double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))/denom;
    if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) {
        // Get the intersection point.
        return new Point((int) (x1 + ua*(x2 - x1)), (int) (y1 + ua*(y2 - y1)));
    }

  return null;
  }

我是否还需要像此代码示例中那样计算一些中值？

For lines through points (x0,y0) and (x1,y1), let xm = (x0+x1)/2, ym = (y0+y1)/2 (median of line segment). 
Then a = (y1-y0) and b = (x0-x1). 
If you evaluate c = a(x-xm)+b(y-ym), c=0 for (x,y) on the line, and the sign(c) tells you which side a point is on

Answer 1

你展示的第一段代码是基于 vector 叉积的，这里已经解释过 How do you detect where two line segments intersect?非常详细。

IMO，一种更简单的理解方式是通过求解方程组。首先看一般的线条，然后从它们中切出部分。下面我对给定的段使用符号((x1, x2), (y1, y2))和 ((x3, x4), (y3, y4)) .

1. 检查是否有任何行是垂直的( x1 == x2 或 x3 == x4 )。

   一个。如果两者都是垂直的并且 x1 != x3 ，则没有交集。

   b.如果两者都是垂直的并且 x1 == x3 , 检查是否 (y1, y2)和 (y3, y4)重叠。

   c。如果只有一条是垂直的(比如第一条)，则建立第二条线的方程(如下所述)，找到两条线相交的点(通过将 x1 代入第二条线的方程)并检查是否此点在两个段内(类似于第 5 步)。

   d。如果没有，请继续。

2. 使用点坐标建立直线方程，格式为y = a*x + b (如 here )。

   a1 = (y2-y1)/(x2-x1)
   b1 = y1 - a1*x1 
   a2 = (y4-y3)/(x4-x3)
   b2 = y3 - a2*x3
   

3. 检查线是否平行(相同斜率 a )。如果是，请检查它们是否具有相同的截距 b .如果是，检查一维线段是否 (x1, x2)和 (x3, x4)重叠。如果是，则您的分割确实重叠。线平行的情况可能不明确。如果它们重叠，您可以将其视为一个交叉点(如果它们的末端接触，它甚至可以是一个点)，或者不。注意:如果你正在使用 float ，那会有点棘手，我想你会想忽略这个。如果您只有整数检查 a1 = a2相当于:

   if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3))
   

4. 如果线不平行。交点等效于表示两条线的方程组的解。真的，y = a1*x + b1和 y = a2*x + b2相交基本上意味着这两个方程都成立。通过将两个右侧相等来解决这个系统，它会给你交点。其实你只需要x交叉点的坐标(画出来你就会明白):

   x0 = -(b1-b2)/(a1-a2)
   

5. 最后一步是检查交点x0位于两个分割市场中。也就是说，min(x1, x2) < x0 < max(x1, x2)和 min(x3, x4) < x0 < max(x3, x4) .如果是，那么您的线确实相交!