检测两个重合线段的重合子集

这个问题与以下内容有关：

• 如何确定GDI +中两条线的交点？ （对代数的很好的解释，但没有代码）
• 如何检测两个线段相交的位置？ （接受的答案实际上不起作用）

但请注意，一个有趣的子问题在大多数解决方案中都被完全掩盖了，即使有三个子案例，它们也只是在重合的情况下返回null：

• 巧合，但不重叠
• 触摸只是点和巧合
• 重叠/重合线子段

例如，我们可以像这样设计一个C＃函数：

public static PointF[] Intersection(PointF a1, PointF a2, PointF b1, PointF b2) 

其中（a1，a2）是一个线段，（b1，b2）是另一个。

此function需要涵盖大多数实现或解释所掩盖的所有奇怪情况。 为了解释重合线的奇怪性，该函数可以返回PointF的数组：

• 如果线条平行或不相交（无限线相交但线段不相交 ，或线条平行 ），则为零结果点（或null）
• 一个结果点（包含交叉点位置），如果它们相交或者它们在一个点上重合
• 如果两条线重合，则两个结果点（对于线段的重叠部分）

Answer 1

听起来你有自己的解决方案，这很棒。 我有一些改进它的建议。

该方法存在一个主要的可用性问题，因为理解（1）参数意味着什么，以及（2）结果出来意味着什么是非常混乱的。 如果你想使用这个方法，你必须弄清楚这两个小难题。

我更倾向于使用类型系统来更清楚地说明这种方法的作用。

我首先定义一个类型 – 也许是一个结构，特别是如果它将是不可变的 – 称为LineSegment。 LineSegment由两个表示结束点的PointF结构组成。

其次，我将定义一个抽象基类型“Locus”，并派生类型EmptyLocus，PointLocus，LineSegmentLocus和UnionLocus，如果您需要表示两个或多个基因座的并集的基因座。 空基因座只是单个基因，点基因座只是一个单点，依此类推。

现在，您的方法签名变得更加清晰：

 static Locus Intersect(LineSegment l1, LineSegment l2) 

此方法采用两个线段并计算作为其交点的点的轨迹 – 空白，单个点或线段。

请注意，您可以概括此方法。 计算线段与线段的交集是很棘手的，但是计算线段与点，或具有点的点或具有空轨迹的任何东西的交点是容易的 。 并且将交叉点扩展到任意的基因座联合并不困难。 因此，您实际上可以写：

 static Locus Intersect(Locus l1, Locus l2) 

嘿，现在很明显，Intersect可能是locus的扩展方法：

 static Locus Intersect(this Locus l1, Locus l2) 

添加从PointF到PointLocus和LineSegment到LineSegmentLocus的隐式转换，您可以这样说

 var point = new PointF(whatever); var lineseg = new LineSegment(somepoint, someotherpoint); var intersection = lineseg.Intersect(point); if (intersection is EmptyLocus) ... 

使用类型系统可以大大提高程序的可读性。

Answer 2

  // port of this JavaScript code with some changes: // http://www.kevlindev.com/gui/math/intersection/Intersection.js // found here: // http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/563240#563240 public class Intersector { static double MyEpsilon = 0.00001; private static float[] OverlapIntervals(float ub1, float ub2) { float l = Math.Min(ub1, ub2); float r = Math.Max(ub1, ub2); float A = Math.Max(0, l); float B = Math.Min(1, r); if (A > B) // no intersection return new float[] { }; else if (A == B) return new float[] { A }; else // if (A < B) return new float[] { A, B }; } // IMPORTANT: a1 and a2 cannot be the same, eg a1--a2 is a true segment, not a point // b1/b2 may be the same (b1--b2 is a point) private static PointF[] OneD_Intersection(PointF a1, PointF a2, PointF b1, PointF b2) { //float ua1 = 0.0f; // by definition //float ua2 = 1.0f; // by definition float ub1, ub2; float denomx = a2.X - a1.X; float denomy = a2.Y - a1.Y; if (Math.Abs(denomx) > Math.Abs(denomy)) { ub1 = (b1.X - a1.X) / denomx; ub2 = (b2.X - a1.X) / denomx; } else { ub1 = (b1.Y - a1.Y) / denomy; ub2 = (b2.Y - a1.Y) / denomy; } List ret = new List(); float[] interval = OverlapIntervals(ub1, ub2); foreach (float f in interval) { float x = a2.X * f + a1.X * (1.0f - f); float y = a2.Y * f + a1.Y * (1.0f - f); PointF p = new PointF(x, y); ret.Add(p); } return ret.ToArray(); } private static bool PointOnLine(PointF p, PointF a1, PointF a2) { float dummyU = 0.0f; double d = DistFromSeg(p, a1, a2, MyEpsilon, ref dummyU); return d < MyEpsilon; } private static double DistFromSeg(PointF p, PointF q0, PointF q1, double radius, ref float u) { // formula here: //http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html // where x0,y0 = p // x1,y1 = q0 // x2,y2 = q1 double dx21 = q1.X - q0.X; double dy21 = q1.Y - q0.Y; double dx10 = q0.X - pX; double dy10 = q0.Y - pY; double segLength = Math.Sqrt(dx21 * dx21 + dy21 * dy21); if (segLength < MyEpsilon) throw new Exception("Expected line segment, not point."); double num = Math.Abs(dx21 * dy10 - dx10 * dy21); double d = num / segLength; return d; } // this is the general case. Really really general public static PointF[] Intersection(PointF a1, PointF a2, PointF b1, PointF b2) { if (a1.Equals(a2) && b1.Equals(b2)) { // both "segments" are points, return either point if (a1.Equals(b1)) return new PointF[] { a1 }; else // both "segments" are different points, return empty set return new PointF[] { }; } else if (b1.Equals(b2)) // b is a point, a is a segment { if (PointOnLine(b1, a1, a2)) return new PointF[] { b1 }; else return new PointF[] { }; } else if (a1.Equals(a2)) // a is a point, b is a segment { if (PointOnLine(a1, b1, b2)) return new PointF[] { a1 }; else return new PointF[] { }; } // at this point we know both a and b are actual segments float ua_t = (b2.X - b1.X) * (a1.Y - b1.Y) - (b2.Y - b1.Y) * (a1.X - b1.X); float ub_t = (a2.X - a1.X) * (a1.Y - b1.Y) - (a2.Y - a1.Y) * (a1.X - b1.X); float u_b = (b2.Y - b1.Y) * (a2.X - a1.X) - (b2.X - b1.X) * (a2.Y - a1.Y); // Infinite lines intersect somewhere if (!(-MyEpsilon < u_b && u_b < MyEpsilon)) // eg u_b != 0.0 { float ua = ua_t / u_b; float ub = ub_t / u_b; if (0.0f <= ua && ua <= 1.0f && 0.0f <= ub && ub <= 1.0f) { // Intersection return new PointF[] { new PointF(a1.X + ua * (a2.X - a1.X), a1.Y + ua * (a2.Y - a1.Y)) }; } else { // No Intersection return new PointF[] { }; } } else // lines (not just segments) are parallel or the same line { // Coincident // find the common overlapping section of the lines // first find the distance (squared) from one point (a1) to each point if ((-MyEpsilon < ua_t && ua_t < MyEpsilon) || (-MyEpsilon < ub_t && ub_t < MyEpsilon)) { if (a1.Equals(a2)) // danger! return OneD_Intersection(b1, b2, a1, a2); else // safe return OneD_Intersection(a1, a2, b1, b2); } else { // Parallel return new PointF[] { }; } } } } 

这是测试代码：

  public class IntersectTest { public static void PrintPoints(PointF[] pf) { if (pf == null || pf.Length < 1) System.Console.WriteLine("Doesn't intersect"); else if (pf.Length == 1) { System.Console.WriteLine(pf[0]); } else if (pf.Length == 2) { System.Console.WriteLine(pf[0] + " -- " + pf[1]); } } public static void TestIntersect(PointF a1, PointF a2, PointF b1, PointF b2) { System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine("Does " + a1 + " -- " + a2); System.Console.WriteLine("intersect " + b1 + " -- " + b2 + " and if so, where?"); System.Console.WriteLine(""); PointF[] result = Intersect.Intersection(a1, a2, b1, b2); PrintPoints(result); } public static void Main() { System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine("line segments intersect"); TestIntersect(new PointF(0, 0), new PointF(100, 100), new PointF(100, 0), new PointF(0, 100)); TestIntersect(new PointF(5, 17), new PointF(100, 100), new PointF(100, 29), new PointF(8, 100)); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine(""); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine("just touching points and lines cross"); TestIntersect(new PointF(0, 0), new PointF(25, 25), new PointF(25, 25), new PointF(100, 75)); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine(""); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine("parallel"); TestIntersect(new PointF(0, 0), new PointF(0, 100), new PointF(100, 0), new PointF(100, 100)); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine(""); System.Console.WriteLine("----"); System.Console.WriteLine("lines cross but segments don't intersect"); TestIntersect(new PointF(50, 50), new PointF(100, 100), new PointF(0, 25), new PointF(25, 0)); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine(""); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine("coincident but do not overlap!"); TestIntersect(new PointF(0, 0), new PointF(25, 25), new PointF(75, 75), new PointF(100, 100)); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine(""); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine("touching points and coincident!"); TestIntersect(new PointF(0, 0), new PointF(25, 25), new PointF(25, 25), new PointF(100, 100)); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine(""); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine("overlap/coincident"); TestIntersect(new PointF(0, 0), new PointF(75, 75), new PointF(25, 25), new PointF(100, 100)); TestIntersect(new PointF(0, 0), new PointF(100, 100), new PointF(0, 0), new PointF(100, 100)); System.Console.WriteLine("----------------------------------------------------------"); System.Console.WriteLine(""); while (!System.Console.KeyAvailable) { } } } 

这是输出：

 -------------------------------------------------- --------
线段相交
 -------------------------------------------------- --------
 {X = 0，Y = 0}  -  {X = 100，Y = 100}
相交{X = 100，Y = 0}  -  {X = 0，Y = 100}如果是这样，在哪里？

 {X = 50，Y = 50}
 -------------------------------------------------- --------
 {X = 5，Y = 17}  -  {X = 100，Y = 100}
相交{X = 100，Y = 29}  -  {X = 8，Y = 100}如果是这样，在哪里？

 {X = 56.85001，Y = 62.30054}
 -------------------------------------------------- --------

 -------------------------------------------------- --------
只是触摸点和线交叉
 -------------------------------------------------- --------
 {X = 0，Y = 0}  -  {X = 25，Y = 25}
相交{X = 25，Y = 25}  -  {X = 100，Y = 75}如果是这样，在哪里？

 {X = 25，Y = 25}
 -------------------------------------------------- --------

 -------------------------------------------------- --------
平行
 -------------------------------------------------- --------
 {X = 0，Y = 0}  -  {X = 0，Y = 100}
相交{X = 100，Y = 0}  -  {X = 100，Y = 100}如果是这样，在哪里？

不相交
 -------------------------------------------------- --------

 ----
线交叉但段不相交
 -------------------------------------------------- --------
 {X = 50，Y = 50}  -  {X = 100，Y = 100}
相交{X = 0，Y = 25}  -  {X = 25，Y = 0}如果是这样，在哪里？

不相交
 -------------------------------------------------- --------

 -------------------------------------------------- --------
巧合，但不重叠！
 -------------------------------------------------- --------
 {X = 0，Y = 0}  -  {X = 25，Y = 25}
相交{X = 75，Y = 75}  -  {X = 100，Y = 100}如果是这样，在哪里？

不相交
 -------------------------------------------------- --------

 -------------------------------------------------- --------
感动点和巧合！
 -------------------------------------------------- --------
 {X = 0，Y = 0}  -  {X = 25，Y = 25}
相交{X = 25，Y = 25}  -  {X = 100，Y = 100}如果是这样，在哪里？

 {X = 25，Y = 25}
 -------------------------------------------------- --------

 -------------------------------------------------- --------
重叠/一致
 -------------------------------------------------- --------
 {X = 0，Y = 0}  -  {X = 75，Y = 75}
相交{X = 25，Y = 25}  -  {X = 100，Y = 100}如果是这样，在哪里？

 {X = 25，Y = 25}  -  {X = 75，Y = 75}
 -------------------------------------------------- --------
 {X = 0，Y = 0}  -  {X = 100，Y = 100}
相交{X = 0，Y = 0}  -  {X = 100，Y = 100}如果是这样，在哪里？

 {X = 0，Y = 0}  -  {X = 100，Y = 100}
 -------------------------------------------------- --------

Answer 3

@Jared，很棒的问题和很棒的答案。

如Joseph O’Rourke的CGA常见问题解答所述，通过将一个点的位置表示为单个参数的函数，可以简化问题。

令r为参数，表示P沿包含AB的直线的位置，其含义如下：

  r=0 P = A r=1 P = B r<0 P is on the backward extension of AB r>1 P is on the forward extension of AB 0 

按照这些思路，对于任何一点C（cx，cy），我们计算r如下：

 double deltax = bx - ax; double deltay = by - ay; double l2 = deltax * deltax + deltay * deltay; double r = (ay - cy) * (ay - by) - (ax - cx) * (bx - ax) / l2; 

这应该可以更容易地计算重叠段。

请注意，我们避免使用平方根，因为只需要长度的平方。

Answer 4

这真的很简单。 如果你有两条线，你可以找到y = mx + bforms的两个方程。 例如：

 y = 2x + 5 y = x - 3 

所以，当y1 = y2在同一个x坐标时，两条线相交，所以……

 2x + 5 = x - 3 x + 5 = -3 x = -8 

当x = -8 y1 = y2并且您找到了交点。 这应该是非常简单的转换为代码。 如果没有交点，那么每条线的斜率m将相等，在这种情况下，您甚至不需要执行计算。