21

在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
4

3 回答 3

31

您展示的第一段代码基于矢量叉积,此处已对此进行了解释如何检测两条线段相交的位置?非常详细。

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

  1. 检查是否有任何线条是垂直的(x1 == x2x3 == 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。如果是,请检查一维线段是否(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)。如果是,你的线确实相交!

于 2013-05-01T07:09:48.730 回答
5

我真的@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适合您。:)

于 2016-12-21T19:34:34.537 回答
1
public void fixData()
{
    slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());
    yInt = p1.getY() - slope * p1.getX();
    xInt = (-yInt) / slope;
}
于 2016-11-07T15:57:10.337 回答