logo标签列表

2D空间中重叠的线段

language-agnosticgeometryline
14

我需要找出两条线是否重叠。我已经有了交点代码，如果两条线平行则返回0。但是我需要知道这两条平行线是否重叠。

编辑：

A                    C       B                D
-----------------------------------------------

第1行：A-B

第2行：C-D

我需要找出第1行和第2行是否有重叠部分，但两行都可以具有斜率>0。

我认为你可以使用起点和终点以及斜率的数学方法来找到它。 - Jonesopolis
这可能是相关的：https://dev59.com/pHRB5IYBdhLWcg3wpYmo - Matthew
1
知道你的线段是否按照某种方式排序会有所帮助，比如第一个点始终在左侧，还是可以变化的？ - A.R.
检查两条直线是否具有相同的斜率 - 如果是，则它们平行。如果它们平行，请检查任何一个点是否相同。 - Jonesopolis
你的线段是“闭合”的还是“开放”的？也就是说，它们是否包括端点？如果是这样，你是否认为端点相等的线段是有效的？ - jerry
显示剩余3条评论
9个回答
22
您可以进行比较以查找是否存在重叠。这种方式可以减少比较次数，因此非常高效。请执行以下比较：

D < A

B < C

如果任一情况为真，则行不重叠。否则必须存在重叠。 要确定它们是否不重叠，您将进行最少数量的比较。否则，将需要进行更多比较。
1
只适用于一维情况，但这正是我要找的。 - Mikhail
你可以使用德摩根定律将这个转换为检查碰撞，变成 B >= C && A <= D。更多有关德摩根定律的信息，请参阅：https://en.wikipedia.org/wiki/De_Morgan's_laws。 - Caleb Bertrand
2

只需要计算三角形ACB和CBD的面积即可。如果面积为0，则这些点共线，如果两个面积都是0，则这些线重叠。

您可以使用以下公式来计算三角形ABC的面积：

2 * 面积(ABC) = (bx - ax)(cy - ay) - (cx - ax)(by - ay);

2
这不是正确的，例如：A=(0,0)，B=(10,0)，C=(11,0)，D=(20,0)。 - padmalcom
2

既然你知道它们都是平行的，那么只需检查线段CD是否包含第一条线段的任一端点（点A和点B）。

2
这是一个充分但不必要的条件。考虑整个CD线段与AB的一部分重叠的情况（例如区间[0,3]和[1,2]）。有一个足够简单的解决方法，但如果考虑实际构建重叠部分（而不仅仅是确定是否存在），则开始变得有些混乱。 - jerry
1

线性方程是无限线的方向，通过找到斜率或截距，你不能对它们做任何事情（即使水平线没有斜率），我建议使用在线上的点。因此AB是你的线[(x,y),(x,y)]，C是线上的一个点(x,y)，然后你需要检查点是否在线上。
检查点是否在直线上

1

对于不一定轴对齐的两个共线线段：

  1. 按照原点周围的顺时针顺序排序顶点。
  2. 如果有序顶点在两个线段之间交替出现，例如Line1.Point1、Line2.Point1、Line1.Point2、Line2.Point2，则表示这两条线段重叠。
对我来说它不起作用：有很多误报。我从链接中复制了代码并实现了简单的排序和决策代码。 - ceztko
@ceztko - 你能举出两个导致误判的片段的例子吗？给出点的坐标，或者画一张图吗？ - mbeckish
如果我有时间重新设置代码，我会这样做。当然，我的尝试可能存在错误。我点赞你的回答是因为你引导我朝着正确的方向前进：共线性可以非常容易地进行测试，并且需要更少的操作，而我已经有了这方面的代码。请看我的回答。 - ceztko
现在我明白问题所在了：我的理解出现了偏差，因为我认为你也在测试共线性。对于你的重叠测试：我应该按照你所说的将顶点排序到原点周围，还是按照线段端点重心进行排序？另外：这个解决方案是否也适用于竖直/接近竖直的线段？ - ceztko
@ceztko - 无论您选择哪个点作为起点，如果线段与起点共线，此解决方案将失败。除此之外，我认为它对于任何起点的选择都应该是有效的。 - mbeckish
看起来还是有点过于复杂。那么，我们可以考虑一个测试方案：1）确保共线性，2）检查端点是否在另一线段的内部？代码请参考http://pastebin.com/7Cdyeu3N。 - ceztko
0

两条线段在同一直线上的特征被称为共线性，可以通过计算一个线段的端点和另一个线段的端点所形成的两个三角形的面积来进行测试。如果该面积接近于零或低于某个阈值，则这两条线段是共线的。

    public static bool AreSegmentsCollinear(Segment a, Segment b, double epsilon)
    {
        return IsPointCollinear(a, b.Left, epsilon) && IsPointCollinear(a, b.Right, epsilon);
    }

    public static bool IsPointCollinear(Segment a, Vector2D p, double epsilon)
    {
        return Math.Abs(GetSignedTriangleArea2(a, p)) <= epsilon;
    }

    /// <returns>The squared signed area of the triangle formed with endpoints
    /// of segment a and point p</returns>
    public static double GetSignedTriangleArea2(Segment a, Vector2D p)
    {
        return (p - a.Left) ^ (a.Right - a.Left);
    }

   /// <summary>Cross product of vectors in 2D space. NB: it returns a
   /// magnitude (scalar), not a vector</summary>
   /// <returns>The area of the parallelogram formed with u, v as the edges</returns>
   public static Double operator ^(Vector2D u, Vector2D v)
   {
       return u.X * v.Y - u.Y * v.X;
   }
检查共线性只是问题的一半（我在回答中忽略了这一点——我误读了问题，认为他已经有了一个共线性测试）。另一半是我的答案——一旦确定它们共线，您需要查看它们是否重叠。 - mbeckish
问题并不是很清楚，事实上：最终我明白他在问共线性。 - ceztko
0

给定以下形式的线段l1和l2[x1，y1，x2，y2]，下面的Python代码将给出任何斜率的共线线段的交点。

intersection = line_intersect(l1, l2)


def line_intersect(l1, l2):
    """Find the intersection of two line segments"""
    
    x1, y1, x2, y2 = l1
    x3, y3, x4, y4 = l2
    
    x_inter = component_intersect(x1, x2, x3, x4)
    y_inter = component_intersect(y1, y2, y3, y4)
    
    return math.sqrt(x_inter**2 + y_inter**2)
    
def component_intersect(c1, c2, c3, c4):
    """Calculate intersection in one dimension/component"""
    
    # find left endpoints
    cl1 = min(c1, c2)
    cl2 = min(c3, c4)
    
    # find right endpoints
    cr1 = max(c1, c2)
    cr2 = max(c3, c4)
    
    # find endpoints of intersection
    c_inter_l = max(cl1, cl2)
    c_inter_r = min(cr1, cr2)
    # calcuate intersection
    c_inter = c_inter_r - c_inter_l
    c_inter = max(c_inter, 0)
    
    return c_inter
0

我们有两条线段：

AB = 从点 (Ax,Ay) 到点 (Bx,By) 的线段
CD = 从点 (Cx,Cy) 到点 (Dx,Dy) 的线段

斜率相同。

  • 将端点 E1、E2、E3、E4排序，使得当 Ei,x = Ei+1,x 时，Ei,x ≤ Ei+1,x 且 Ei,y ≤ Ei+1,y
  • 如果 E1 和 E2 分别属于不同的线段，则它们的重叠部分是从 E2 到 E3 的线段。

还存在一些特殊情况：

  • A < B = C < D
  • A < C = D < B
  • A < B = C = D
  • A = B = C = D

这些结果导致单个交点。我不确定您的系统是否可能出现其中任何一个，但如果是，您必须决定是否将其视为“重叠”，并添加特殊情况检查。

0

为了澄清答案中存在的一些混淆，所提出的问题如下。给定两个二维线段A和B，如何确定以下两个条件是否都成立：

  1. A和B共线。
  2. A和B相交。

请注意，这两个问题都涉及到公差，即A和B需要多接近平行，以及它们需要重叠多少才能被认为是重叠的？

我认为，为了稳健地处理这样的公差，最好的算法是将线段视为薄矩形，其中矩形的厚度是一个公差参数t1。让t2成为另一个被认为是平行的斜率的公差参数。然后算法变为：

  1. 如果A的斜率和B的斜率相差超过t2，则返回false。为了清晰地处理垂直线，可以将斜率表示为单位向量，并测试两个单位向量之间的欧几里得距离是否小于t2。

  2. 将A和B表示为（非轴对齐）矩形R1和R2。其中R1以明显的方式包围A，即它的长度为length(A) + t1个单位，宽度为t1个单位，A居中在其中，类似地，R2包围B。

  3. 确定R1和R2是否相交。这可以通过将每个矩形视为两个三角形的并集，并在所有A三角形和B三角形的组合中测试三角形-三角形相交来相对高效地完成。如果有交点，则返回true；否则返回false。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接