线段之间的交点的计算

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

您显示的第一段代码基于矢量叉积，已在此处进行了说明。如何检测两条线段相交的位置？非常详细。

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。如果不是，请继续。

1. 使用点坐标以形式构建线方程y = a*x + b（如此处）。

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

1. 检查直线是否平行（斜率相同a）。如果是，请检查它们是否具有相同的intercept b。如果是，检查是否1D段(x1, x2)和(x3, x4)重叠。如果是，则您的细分确实重叠。线平行的情况可能会模棱两可。如果它们重叠，则可以将其视为一个相交（如果它们的端点接触，甚至可以是一个点）。注意：如果使用的是浮点数，则会有些棘手，我认为您可能会忽略此问题。如果您只有整数，则检查if a1 = a2是否等于：

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

2. 如果线不平行。相交点等效于代表两条直线的方程组的解。说真的，y = a1*x + b1和y = a2*x + b2相交的基本意思是，这两个等式的成立。通过等同于两个右侧来解决该系统，它会给您交叉点。实际上，您只需要x交叉点的坐标（将其绘制即可，然后看到原因）：

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

3. 最后一步是检查交点是否x0在两个线段内。即min(x1, x2) < x0 < max(x1, x2)和min(x3, x4) < x0 < max(x3, x4)。如果是，则您的线条确实相交！