计算线段之间的交点

关于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

来源

2013-05-01 3D-kreativ

是你的点整数或浮点数？ – 2013-05-02 00:02:21

的告诉你第一段代码是基于向量跨产品，已经在一个伟大的详细解释How do you detect where two line segments intersect?。

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

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

a。如果两者都是垂直的并且x1 != x3，那么没有交集。

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

c。如果只有一个是垂直的（比如说第一个），然后建立第二条线的方程（如下所述），找出两条线相交的点（通过将x1代入第二条线的方程）并检查这一点在两个分段内（类似于步骤5）。 d）。如果没有，继续。

使用点坐标来构建y = a*x + b（如here）形式的线方程。

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

检查线平行（相同的斜率a）。如果是，请检查它们是否具有相同的截距b。如果是，请检查1D区段(x1, x2)和(x3, x4)是否重叠。如果是的话，你的部分确实重叠。线条平行的情况可能不明确。如果它们重叠，则可以将其视为交叉点（如果它们的末端触及，它甚至可以是一个点），或者不是。注意：如果你正在使用浮动，它会有点棘手，我估计你会忽略这一点。如果你只有整数检查是否a1 = a2相当于：如果线不平行
```
if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3)) 
```
。交点相当于表示两条线的方程组的解。真的，y = a1*x + b1和y = a2*x + b2相交基本意味着这两个等式都成立。通过将两个右侧等同来解决这个问题，它会给你交点。其实，你只需要交点坐标x（画它，你就会明白为什么）：
```
x0 = -(b1-b2)/(a1-a2) 
```
最后一步是这两个领域内检查交点x0谎言。即，min(x1, x2) < x0 < max(x1, x2)和min(x3, x4) < x0 < max(x3, x4)。如果是的话，你的线条相交！

来源

2013-05-01 07:09:48 sashkello

嗯，只是另一个例子。之前我已经看到过，但与其他所有示例一样，它就像一门外语！我想我的数学能力有点有限，但我不想阻止我学习。 – 2013-05-01 07:15:32

我已将所有位置存储为数组列表中的点，并且需要将它们传递给检查是否存在交集的方法。但我不知道如何开始？我想我只需要检查是否重叠！？ – 2013-05-01 07:16:53

一些示例代码以及一些解释将会得到真正的优化。 – 2013-05-01 07:23:44

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

来源

2016-11-07 15:57:10 user7127290

我真的@ 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-21 19:34:34

计算线段之间的交点

回答

相关问题