计算线段之间的交叉点

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,那么就没有交叉点.

   湾 如果两者都垂直和x1 == x3,检查(y1, y2)和(y3, y4)重叠.

   C.如果只有一个是垂直的(比如第一个),那么建立第二行的等式(如下所述),找到两条线相交的点(通过代x1入第二行的等式)并检查这一点是否是在两个部分内(类似于步骤5).

   d.如果没有,继续.

2. 使用点坐标以形式构建线方程y = a*x + b(如此处).

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

3. 检查线是否平行(相同的斜率a).如果是,请检查他们是否有相同的拦截b.如果是,检查是否1D段(x1, x2)和(x3, x4)重叠.如果是,您的细分会确实重叠.线条平行的情况可能不明确.如果它们重叠,您可以将其视为交叉点(如果它们的末端接触,它甚至可以是一个点),或者不是.注意:如果你正在使用浮动它会有点棘手,我想你会想忽略它.如果您只有整数检查是否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).如果是,你的线确实相交!

Answer 2

我真的是@sashkello的答案，并发现它比矢量实现更直观，更易于解释。尤其是在将这种代码添加到代码库中时。

我要说的是，您可以利用Java的Line2D帮助器方法。

Line2D.linesIntersect(double x1, double y1,
                      double x2, double y2,
                      double x3, double y3,
                      double x4, double y4)

唯一的缺点是，即使线段只是在接触（在端点和线本身上），也要求您将线段视为相交。

例如，以下几行被认为是相交的，因为它们共享点（1,1）。

L1 = [(0,0),(1,1)]
L2 = [(1,1),(2,3)]

如果这是一个问题，您可以添加4个检查以查看分数是否相等。

如果您担心某个点落在直线上的某个点上，则需要花费更多的工作，最好自己实施，以便您可以在算法本身中进行检查。

如果所有这些极端情况都没有影响到您，那么Line2D.linesIntersect适合您。:)