找到重叠两个共线段的段的算法

更新

• 我在C＃中的原始实现
• 我在C＃中的最终实现，基于我得到的答案。

---

鉴于以下条件，我如何以编程方式找到两条线之间的重叠段？

另外，对于不同的斜率：

对于垂直线：

对于水平线：

注意：对于所有象限！

我开始编写所有可能的条件，但它变得丑陋。

public Line GetOverlap (Line line1, Line line2) { double line1X1 = line1.X1; double line1Y1 = line1.Y1; double line1X2 = line1.X2; double line1Y2 = line1.Y2; double line2X1 = line2.X1; double line2Y1 = line2.Y1; double line2X2 = line2.X2; double line2Y2 = line2.Y2; if (line1X1 > line1X2) { double swap = line1X1; line1X1 = line1X2; line1X2 = swap; swap = line1Y1; line1Y1 = line1Y2; line1Y2 = swap; } else if (line1X1.AlmostEqualTo (line1X2)) { if (line1Y1 > line1Y2) { double swap = line1Y1; line1Y1 = line1Y2; line1Y2 = swap; swap = line1X1; line1X1 = line1X2; line1X2 = swap; } } if (line2X1 > line2X2) { double swap = line2X1; line2X1 = line2X2; line2X2 = swap; swap = line2Y1; line2Y1 = line2Y2; line2Y2 = swap; } else if (line2X1.AlmostEqualTo (line2X2)) { if (line2Y1 > line2Y2) { double swap = line2Y1; line2Y1 = line2Y2; line2Y2 = swap; swap = line2X1; line2X1 = line2X2; line2X2 = swap; } } double line1MinX = Math.Min (line1X1, line1X2); double line2MinX = Math.Min (line2X1, line2X2); double line1MinY = Math.Min (line1Y1, line1Y2); double line2MinY = Math.Min (line2Y1, line2Y2); double line1MaxX = Math.Max (line1X1, line1X2); double line2MaxX = Math.Max (line2X1, line2X2); double line1MaxY = Math.Max (line1Y1, line1Y2); double line2MaxY = Math.Max (line2Y1, line2Y2); double overlap; if (line1MinX < line2MinX) overlap = Math.Max (line1X1, line1X2) - line2MinX; else overlap = Math.Max (line2X1, line2X2) - line1MinX; if (overlap <= 0) return null; double x1; double y1; double x2; double y2; if (line1MinX.AlmostEqualTo (line2MinX)) { x1 = line1X1; x2 = x1; y1 = line1MinY < line2MinY ? line2Y1 : line1Y1; y2 = line1MaxY < line2MaxY ? line1Y2 : line2Y2; } else { if (line1MinX  line2MaxX) { x2 = line2X2; y2 = line2Y2; } else { x2 = line1X2; y2 = line1Y2; } } return new Line (x1, y1, x2, y2); } 

我确定存在一个算法，但我无法在网上找到一个。

---

根据我得到的答案更新解决方案：

这个解决方案解释了我能想到的所有情况（垂直，水平，正斜率，负斜率，不相交）

 public Line GetOverlap (Line line1, Line line2) { double slope = (line1.Y2 - line1.Y1)/(line1.X2 - line1.X1); bool isHorizontal = AlmostZero (slope); bool isDescending = slope < 0 && !isHorizontal; double invertY = isDescending || isHorizontal ? -1 : 1; Point min1 = new Point (Math.Min (line1.X1, line1.X2), Math.Min (line1.Y1*invertY, line1.Y2*invertY)); Point max1 = new Point (Math.Max (line1.X1, line1.X2), Math.Max (line1.Y1*invertY, line1.Y2*invertY)); Point min2 = new Point (Math.Min (line2.X1, line2.X2), Math.Min (line2.Y1*invertY, line2.Y2*invertY)); Point max2 = new Point (Math.Max (line2.X1, line2.X2), Math.Max (line2.Y1*invertY, line2.Y2*invertY)); Point minIntersection; if (isDescending) minIntersection = new Point (Math.Max (min1.X, min2.X), Math.Min (min1.Y*invertY, min2.Y*invertY)); else minIntersection = new Point (Math.Max (min1.X, min2.X), Math.Max (min1.Y*invertY, min2.Y*invertY)); Point maxIntersection; if (isDescending) maxIntersection = new Point (Math.Min (max1.X, max2.X), Math.Max (max1.Y*invertY, max2.Y*invertY)); else maxIntersection = new Point (Math.Min (max1.X, max2.X), Math.Min (max1.Y*invertY, max2.Y*invertY)); bool intersect = minIntersection.X <= maxIntersection.X && (!isDescending && minIntersection.Y = maxIntersection.Y); if (!intersect) return null; return new Line (minIntersection, maxIntersection); } public bool AlmostEqualTo (double value1, double value2) { return Math.Abs (value1 - value2) <= 0.00001; } public bool AlmostZero (double value) { return Math.Abs (value) <= 0.00001; } 

Answer 1

这个问题大致相当于测试两个轴对齐的矩形是否相交：你可以威胁每个段作为轴对齐矩形的对角线，然后你需要找到这两个矩形的交点。 以下是我用于矩形交叉的方法。

让我们假设段的斜率是上升的，垂直的或水平的; 如果段正在下降，则否定每个y坐标以使它们上升。

为每个线段定义MinPoint和MaxPoint：

 Point min1 = new Point(Math.Min(line1.X1, line1.X2),Math.Min(line1.Y1,line1.Y2); Point max1 = new Point(Math.Max(line1.X1, line1.X2),Math.Max(line1.Y1,line1.Y2); Point min2 = new Point(Math.Min(line2.X1, line2.X2),Math.Min(line2.Y1,line2.Y2); Point max2 = new Point(Math.Max(line2.X1, line2.X2),Math.Max(line2.Y1,line2.Y2); 

现在交叉点由以下两点给出：两个最小值的最大值，以及两个最大值的最小值

 Point minIntersection = new Point(Math.Max(min1.X, min2.X), Math.Max(min1.Y, min2.Y)); Point maxIntersection = new Point(Math.Min(max1.X, max2.X), Math.Min(max1.Y, max2.Y)); 

就是这样。 要检查两个段是否相交，请检查

 bool intersect = (minIntersection.X< maxIntersection.X) && (minIntersection.Y< maxIntersection.Y); 

如果它们相交，则交点由minIntersection和maxIntersection两个点maxIntersection 。 如果它们不相交，则段的长度(minIntersection, maxIntersection)是两个原始段之间的距离。

（如果在第一步中否定了每个y坐标，则现在否定结果的y坐标）

（您可以轻松扩展此方法以覆盖3维或更多维度的共线段）

Answer 2

变换您的坐标，以便通过您的线段的线是新的x轴。

按从左到右的顺序对点进行排序。

如果段实际上重叠，那么解决方案将始终是第二和第三点。

注意：如果不保证段重叠，则测试很简单 – 如果前两个点属于同一段，则它们不重叠。

Answer 3

按字典顺序对两个段进行排序，然后获取第一个段的最后一个元素和最后一个段的第一个元素（按字典顺序排列的段）。 这为您提供了所需的细分。

然后，如果要进行validation，可以使用交叉产品来确定它们是否形成一条线。 2D交叉积为零表示三个点形成一条线。

例如：

 B = ((0,0),(3,3)) A = ((2,2),(5,5)) 

经过lexigraphic排序：

 [((0,0),(3,3)),((2,2),(5,5))] C = ((3,3),(4,4)) 

然后，您可以通过确保C的第一个元素在图形上大于第二个线段的第一个元素来检查它们是否重叠。 在它的例子中。

而且他们认证的交叉产品重叠。 这是通过使用第一个列表的第一个元素和最后一个段的最后一个元素来完成的。 然后分别检查内部的两个元素中的每个元素，看看它们是否都是通过三个点的交叉积为零线：

 cross((0,0),(1,1),(5,5)) = 0 cross((0,0),(4,4),(5,5)) = 0 

因此，两个输入段确实形成一条线。

我对C＃不太熟悉以确保正确性，但在Python中，算法看起来像：

 def cross(o, a, b): return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) def line_segment_overlap(segment_a,segment_b): segments = [segment_a.sort(),segment_b.sort()] # 2D Lexicographic sort the line segments segments.sort() A = segments[0] B = segments[1] if cross(A[0],A[1],B[1]) == 0 and cross(A[0],B[0],B[1]) == 0: # Segments form a line if A[1] > B[0]: # Segments overlap return (A[1],B[1]) # New line segment return None 

Answer 4

使用将段AB映射到(0, 0):(0, 1)的变换。 与AB共线的任何段对于两个端点都将具有纵坐标0，令(c, 0):(d, 0) 。 重叠由(Max(0, c), 0):(Min(1, d), 0) ，除非Max(0, c) > Min(1, d) 。

令ABx = X1 - X0 ， ABy = Y1 - Y0且AB^2 = ABx^2 + ABy^2 。

 x = ((X-XA) ABx + (Y-YA) ABy) / AB^2 y = ((X-XA) ABy - (Y-YA) ABx) / AB^2 

如果想要2D中的重叠，请应用逆变换（y = 0）。

 X = XA + x ABx Y = YA + x ABy 

Answer 5

我不是百分百肯定这一点，希望社区能够说出来。 我不是仅仅因为我认为一些次要的格式不会受到影响而将其作为评论发布。

我看到它的方式，直线的方程式：

y = mx + c

哪里

• y是给定的y坐标（在xy对中）;
• m是线的梯度（斜率）;
• x是给定的坐标（ xy对的另一部分）;
• c是拦截是关键。

对于任何两个点的集合，您应该能够通过以下方式计算线的等式：

1. 找到m的值（通常的dy/dx ）

2. 找到y=0的值为y=0 。

一旦你计算了它，你可以用字符串的forms生成方程式。

一旦你完成所有的点对，你应该能够通过检查你生成的方程来识别彼此叠加的线段。 然后，您可以使用线上点的坐标来推断2个矩形，并查看哪个矩形适合另一个。 这应该可以帮助您确定哪个行在哪个段内。