Java 计算线段之间的交点

Calculation of intersections between line segments

提问by 3D-kreativ

There's a lot of questions about intersections between line segments here at stackowerflow and here is one more! Sorry, but I need help to understand how to calculate intersections. I have read several of the questions here and looked at several examples on other websites, but I'm still confused and don't get it! I don't like to copy and paste code without how things work.

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

So far I know that I'm going to compare the points of each line segments like Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. Could someone explain for me what I'm going to calculate, what would the result of the calculating be if there is an intersection?

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

This is one of the example code I seen. I guess I don't need the intersecting point, just to know if the lines intersect or not.

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

   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;
  }

Do I also need to calculate some median value like in this code example?

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

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

采纳答案by sashkello

The first piece of code you show is based on vector cross-product, which has been explained here How do you detect where two line segments intersect?in a great detail.

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

IMO, an easier way of understanding it is through solving a system of equations. Firstly look at lines generally and then cut segments from them. Below I use notations for given segments ((x1, x2), (y1, y2))and ((x3, x4), (y3, y4)).

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

1. Check if any of the lines is vertical (x1 == x2or x3 == x4).

   a. If both are vertical and x1 != x3, then no intersection.

   b. If both are vertical and x1 == x3, check if (y1, y2)and (y3, y4)overlap.

   c. If only one is vertical (say, first one), then build the equation of the second line (as outlined below), find the point where two lines intersect (by substituting x1into the equation of the second line) and check if this point is within both segments (similar to step 5).

   d. If not, proceed.

2. Use the points coordinates to build lines equations in form y = a*x + b(like here).

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

3. Check if lines are parallel (same slope a). If yes, check if they have same intercept b. If yes, check if 1D segments (x1, x2)and (x3, x4)overlap. If yes, your segments do overlap. The case when lines are parallel can be ambiguous. If they overlap, you can consider it as an intersection (it even can be one point if their ends are touching), or not. Note: if you are working with floats it would be a bit trickier, I reckon you would want to ignore this. In case you have only integers checking if a1 = a2is equivalent to:

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

4. If lines are not parallel. The point of intersection is equivalent to a solution of a system of equations representing the two lines. Really, y = a1*x + b1and y = a2*x + b2intersecting basically means that both of these equations hold. Solve this system by equating the two right sides and it will give you the intersection point. In fact, you need only xcoordinate of the intersection (draw it and you'll see why):

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

5. Last step is to check if the intersection point x0lies within both segments. That is, min(x1, x2) < x0 < max(x1, x2)and min(x3, x4) < x0 < max(x3, x4). If yes, your lines do intersect!

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)。如果是，您的线确实相交！

回答by user7127290

public void fixData()
{
    slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());
    yInt = p1.getY() - slope * p1.getX();
    xInt = (-yInt) / slope;
}

回答by Kenny Cason

I really @sashkello's answer and find it to be more intuitive and easier to explain than the vector implementation. Particularly when adding this kind of code to a code base.

我真的很喜欢@sashkello 的回答，发现它比向量实现更直观、更容易解释。特别是在将这种代码添加到代码库时。

I'll caveat that with saying that you can make use of Java's Line2D helper method.

我要说明的是，您可以使用 Java 的 Line2D 辅助方法。

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

The only draw back is that it requires you to consider the segments to be intersecting even when they are just touching (on both end points and the line itself).

唯一的缺点是它需要您考虑线段是否相交，即使它们只是接触（在两个端点和线本身上）。

For example, the below lines are considered intersecting because they share point (1,1).

例如，下面的线被认为是相交的，因为它们共享点 (1,1)。

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

If that is a problem you can add 4 checks to see if the points are equal.

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

If you have concerns about a point falling on a point within the line, that takes a bit more work and you're maybe better off implementing it yourself so you can do the checks in the algorithm itself.

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

If none of those edge cases affect you, then Line2D.linesIntersectis for you. :)

如果这些边缘情况都不会影响您，那么Line2D.linesIntersect适合您。:)