计算线段之间的交点

math intersection android java

2022-09-02 03:25:24

在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

答案 1

您展示的第一段代码基于向量交叉积，这里已经对此进行了解释如何检测两条线段相交的位置？非常详细。

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

检查是否有任何线条是垂直的（或）。x1 == x2x3 == x4

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

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

c. 如果只有一条是垂直的（例如，第一条线），则构建第二条线的方程（如下所述），找到两条线相交的点（通过代入第二条线的方程），并检查该点是否在两条线内（类似于步骤5）。x1

d. 如果没有，请继续。
使用点坐标构建形式的直线方程（如此处所示）。y = a*x + b
```
a1 = (y2-y1)/(x2-x1)
b1 = y1 - a1*x1 
a2 = (y4-y3)/(x4-x3)
b2 = y3 - a2*x3
```
检查线是否平行（坡度相同）。如果是，请检查它们是否具有相同的截距。如果是，请检查 1D 线段是否重叠。如果是，则您的细分会重叠。线平行的情况可能不明确。如果它们重叠，您可以将其视为交叉点（如果它们的末端接触，它甚至可以是一个点），或者不。注意：如果您正在使用浮点数，那会有点棘手，我认为您会想要忽略这一点。如果您只有整数，请检查是否等效于：ab(x1, x2)(x3, x4)a1 = a2
```
if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3))
```
如果线不平行。交点等效于表示两条线的方程组的解。真的，相交基本上意味着这两个方程都成立。通过相等于两个右侧来解决这个系统，它将为您提供交点。事实上，你只需要交叉点的坐标（画出来，你就会明白为什么）：y = a1*x + b1y = a2*x + b2x
```
x0 = -(b1-b2)/(a1-a2)
```
最后一步是检查交点是否位于两个线段内。即，和。如果是，您的线确实相交！x0min(x1, x2) < x0 < max(x1, x2)min(x3, x4) < x0 < max(x3, x4)

答案 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