12

我需要找出两条线是否相互重叠。如果两条线平行，我有返回 0 的交集代码。但是我需要知道这两条平行线是否重叠。

编辑：

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

第 1 行：AB

第 2 行：CD

我需要确定第 1 行是否与第 2 行重叠，但两条线的斜率 > 0。

4

9 回答 9

20

你可以比较一下，看看有没有过圈。以这种方式，您将进行较少的比较，因此非常有效。做以下比较

D < A

B < C

如果任一情况为真，则线条不重叠。否则必须有重叠。您将进行最少数量的比较以确定它们是否不重叠。否则会有更多的比较。

于 2014-01-16T17:19:54.893 回答
2

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

于 2013-06-17T15:11:38.357 回答
1

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

  1. 围绕原点按顺时针顺序对顶点进行排序。
  2. 如果有序顶点在两个线段之间交替，则线重叠，例如 Line1.Point1、Line2.Point1、Line1.Point2、Line2.Point2。
于 2013-06-17T15:23:54.390 回答
1

计算三角形 ACB 和 CBD 的面积就足够了。如果面积为 0，则点共线，如果两个面积均为零，则线重叠。

您可以通过以下公式计算三角形 ABC 的面积：

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

于 2014-05-21T12:04:51.160 回答
1

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

于 2016-04-06T03:23:09.853 回答
0

两条线段在同一条线上的特性称为共线性，可以通过计算一条线段端点和另一条线段端点分别形成的 2 个三角形的面积来测试。如果区域在阈值以下为零或接近零，则这些段是共线的。

    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;
   }
于 2014-02-27T22:42:42.803 回答
0

我们有两条线段

AB = 从 (A x ,A y ) 到 (B x ,B y )
的线段 CD = 从 (C x ,C y ) 到 (D x ,D y )的线段

具有相同的斜率。

  • 对端点 E 1 < E 2 < E 3 < E 4排序，使得 E i,x ≤ E i+1,x和 E i,y ≤ E i+1,y如果 E i,x = E i+1， X
  • 如果 E 1和 E 2来自不同的段，则重叠是从 E 2到 E 3的段。

有一些退化的情况：

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

这些导致单个交叉点。我不确定您的系统中是否会出现这些情况，但如果是这样，您必须决定是否考虑“重叠”并添加特殊情况检查。

于 2013-06-17T16:20:45.910 回答
0

为了清楚起见，由于答案似乎有些混乱，因此提出的问题如下。给定两个 2D 线段 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；否则返回假。

于 2020-09-28T22:35:47.983 回答
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
于 2020-10-07T20:18:06.933 回答