我如何检查两段是否相交？

我怎样才能检查2段相交？

我有以下数据：

Segment1 [ {x1,y1}, {x2,y2} ] Segment2 [ {x1,y1}, {x2,y2} ] 

我需要在Python中编写一个小的algorithm来检测2行是否相交。

更新：

Answer 1

线的方程是：

 f(x) = A*x + b = y 

对于一个细分市场来说，它是完全一样的，除了x包含在一个区间I.

如果您有两个细分受众群，定义如下：

 Segment1 = {(X1, Y1), (X2, Y2)} Segment2 = {(X3, Y3), (X4, Y4)} 

交点（Xa，Ya）的交点Xa必须包含在区间I1和I2中，定义如下：

 I1 = [MIN(X1,X2), MAX(X1,X2)] I2 = [MIN(X3,X4), MAX(X3,X4)] 

我们可以说Xa被纳入到：

 Ia = [MAX( MIN(X1,X2), MIN(X3,X4) ), MIN( MAX(X1,X2), MAX(X3,X4)] )] 

现在，您需要检查Ia是否存在：

 if (MAX(X1,X2) < MIN(X3,X4)) return false; // There is no mutual abcisses 

所以，你有两个直线公式，一个相互间隔。 你的线公式是：

 f1(x) = A1*x + b1 = y f2(x) = A2*x + b2 = y 

由于我们得到了两个分段，我们可以确定A1，A2，B1和B2：

 A1 = (Y1-Y2)/(X1-X2) // Pay attention to not dividing by zero A2 = (Y3-Y4)/(X3-X4) // Pay attention to not dividing by zero b1 = Y1-A1*X1 = Y2-A1*X2 b2 = Y3-A2*X3 = Y4-A2*X4 

如果段是平行的，那么A1 == A2：

 if (A1 == A2) return false; // Parallel segments 

站在两条线上的一个点（Xa，Ya）必须validation公式f1和f2：

 Ya = A1 * Xa + b1 Ya = A2 * Xa + b2 A1 * Xa + b1 = A2 * Xa + b2 Xa = (b2 - b1) / (A1 - A2) // Once again, pay attention to not dividing by zero 

最后要做的是检查Xa是否包含在Ia中：

 if ( (Xa < MAX( MIN(X1,X2), MIN(X3,X4) )) || (Xa > MIN( MAX(X1,X2), MAX(X3,X4) )) ) return false; // intersection is out of bound else return true; 

除此之外，您可以在启动时检查四个提供的点中的两个不相等，以避免所有testing。

Answer 2

User @ i_4_got在Python中提供了一个非常有效的解决scheme。 为了方便起见，我在这里重现它（因为它会让我很高兴在这里）：

 def ccw(A,B,C): return (Cy-Ay) * (Bx-Ax) > (By-Ay) * (Cx-Ax) # Return true if line segments AB and CD intersect def intersect(A,B,C,D): return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D) 

Answer 3

您不必精确地计算段在哪里相交，但只能了解它们是否相交。 这将简化解决scheme。

这个想法是把一个细分市场当作“锚点”，把第二个细分市场分成两个点。
现在，你将不得不find每个点到“锚定”段（OnLeft，OnRight或者共线）的相对位置。
在这两点之后，检查其中一个点是OnLeft，另一个是OnRight（或者包括共线位置，如果你希望包含不正确的交点）。

然后您必须重复这个过程，并使用锚点和分隔段的angular色。

如果且仅当其中一个点是OnLeft，另一个是OnRight时，交点才存在。 有关每个可能情况的示例图像，请参阅此链接以获取更详细的解释。

实现这种方法比实际实现一个find交点的方法要容易得多（假设你也必须处理许多angular落情况）。

更新

下面的函数应该说明这个想法（来源： C中的计算几何 ）。
备注：本示例假定使用整数。 如果你使用浮点数表示来代替（这显然可能使事情复杂化），那么你应该确定一些ε值来表示“相等”（主要是用于IsCollinear评估）。

 // points "a" and "b" forms the anchored segment. // point "c" is the evaluated point bool IsOnLeft(Point a, Point b, Point c) { return Area2(a, b, c) > 0; } bool IsOnRight(Point a, Point b, Point c) { return Area2(a, b, c) < 0; } bool IsCollinear(Point a, Point b, Point c) { return Area2(a, b, c) == 0; } // calculates the triangle's size (formed by the "anchor" segment and additional point) int Area2(Point a, Point b, Point c) { return (bX - aX) * (cY - aY) - (cX - aX) * (bY - aY); } 

当然，使用这些函数时，必须记得检查每个段落在“另一个段落”之间（因为这些是有限的段而不是无限的线段）。

此外，使用这些function，您可以了解您是否有适当的或不正确的交集。

• 适当的 ：没有共线点。 这些分段“从一边到另一边”彼此交叉。
• 不正确 ：一段只有“接触”另一段（至less有一个点与锚定段共线）。

Answer 4

假设两个片段有端点A，B和C，D。 确定相交的数字稳健的方法是检查四个决定因素的符号：

 | Ax-Cx Bx-Cx | | Ax-Dx Bx-Dx | | Ay-Cy By-Cy | | Ay-Dy By-Dy | | Cx-Ax Dx-Ax | | Cx-Bx Dx-Bx | | Cy-Ay Dy-Ay | | Cy-By Dy-By | 

对于交集，左边的每个行列式必须与右边的符号相反，但两行之间不需要有任何关系。 您基本上是检查一个段的每个点与另一个段的相对位置，以确保它们位于另一个段所定义的线的相对两侧。

看到这里： http : //www.cs.cmu.edu/~quake/robust.html

Answer 5

你有两个线段。 由端点A和B定义一个段，由端点C和D定义第二个段。有一个很好的技巧，表明它们必须在段的边界内相交。 （请注意，线条本身可能会超越线段的边界，所以您必须小心，好的代码也会观察平行线。）

诀窍在于testing点A和B必须在线CD的相对侧上排列，并且点C和D必须位于线AB的相对侧上。

既然这是作业，我不会给你明确的解决办法。 但是，一个简单的testing，看看一个点的哪一侧是一个点，是使用点积。 因此，对于给定的行CD，计算该行的法线向量（我将称之为N_C）。现在，简单地testing这两个结果的符号：

 dot(AC,N_C) 

和

 dot(BC,N_C) 

如果这些结果有相反的标志，那么A和B就是CD的两边。 现在对另一行AB做同样的testing。 它具有法向量N_A。 比较的迹象

 dot(CA,N_A) 

和

 dot(DA,N_A) 

我会让你知道如何计algorithm向量。 （在2-d中，这是微不足道的，但是你的代码会担心A和B是否是不同的点？同样，C和D是不同的？）

您仍然需要担心位于相同的无限长线上的线段，或者实际上一个点落在另一个线段上。 好的代码将迎合每一个可能的问题。

Answer 6

这里是C代码来检查两个点是否在线段的相反两侧。 使用这段代码你可以检查两个段是否相交。

 // true if points p1, p2 lie on the opposite sides of segment s1--s2 bool oppositeSide (Point2f s1, Point2f s2, Point2f p1, Point2f p2) { //calculate normal to the segment Point2f vec = s1-s2; Point2f normal(vec.y, -vec.x); // no need to normalize // vectors to the points Point2f v1 = p1-s1; Point2f v2 = p2-s1; // compare signs of the projections of v1, v2 onto the normal float proj1 = v1.dot(normal); float proj2 = v2.dot(normal); if (proj1==0 || proj2==0) cout<<"collinear points"<<endl; return(SIGN(proj1) != SIGN(proj2)); 

}

Answer 7

基于Liran和Grumdrig的优秀答案，这里是一个完整的Python代码来validation闭合段是否相交。 适用于共线节段，平行于Y轴的节段，退化节段（魔鬼细节）。 假设整数坐标。 浮点坐标需要修改以指向相等testing。

 def side(a,b,c): """ Returns a position of the point c relative to the line going through a and b Points a, b are expected to be different """ d = (c[1]-a[1])*(b[0]-a[0]) - (b[1]-a[1])*(c[0]-a[0]) return 1 if d > 0 else (-1 if d < 0 else 0) def is_point_in_closed_segment(a, b, c): """ Returns True if c is inside closed segment, False otherwise. a, b, c are expected to be collinear """ if a[0] < b[0]: return a[0] <= c[0] and c[0] <= b[0] if b[0] < a[0]: return b[0] <= c[0] and c[0] <= a[0] if a[1] < b[1]: return a[1] <= c[1] and c[1] <= b[1] if b[1] < a[1]: return b[1] <= c[1] and c[1] <= a[1] return a[0] == c[0] and a[1] == c[1] # def closed_segment_intersect(a,b,c,d): """ Verifies if closed segments a, b, c, d do intersect. """ if a == b: return a == c or a == d if c == d: return c == a or c == b s1 = side(a,b,c) s2 = side(a,b,d) # All points are collinear if s1 == 0 and s2 == 0: return \ is_point_in_closed_segment(a, b, c) or is_point_in_closed_segment(a, b, d) or \ is_point_in_closed_segment(c, d, a) or is_point_in_closed_segment(c, d, b) # No touching and on the same side if s1 and s1 == s2: return False s1 = side(c,d,a) s2 = side(c,d,b) # No touching and on the same side if s1 and s1 == s2: return False return True 

Answer 8

既然你没有提到你想find线的交点，那么问题就变得更简单了。 如果你需要交叉点，那么OMG_peanuts的答案是一个更快的方法。 然而，如果你只是想找出是否相交的线，你可以通过使用线方程（ax + by + c = 0）。 方法如下：

1. 我们从两条线段开始：段1和段2。

    segment1 = [[x1,y1], [x2,y2]] segment2 = [[x3,y3], [x4,y4]] 

2. 检查两条线段是否为非零长度线和不同的线段。

3. 从此，我认为这两个部分是非零长度和不同的。 对于每条线段，计算线的斜率，然后以ax + by + c = 0的forms获得一条线的方程。现在，计算f = ax + by + c的值其他线段（对其他线段重复此操作）。

    a2 = (y3-y4)/(x3-x4); b1 = -1; b2 = -1; c1 = y1 - a1*x1; c2 = y3 - a2*x3; // using the sign function from numpy f1_1 = sign(a1*x3 + b1*y3 + c1); f1_2 = sign(a1*x4 + b1*y4 + c1); f2_1 = sign(a2*x1 + b2*y1 + c2); f2_2 = sign(a2*x2 + b2*y2 + c2); 

4. 现在剩下的就是不同的情况。 如果f = 0的任何一点，那么两条线在一点触摸。 如果f1_1和f1_2相等，或者f2_1和f2_2相等，则线不相交。 如果f1_1和f1_2不等， f2_1和f2_2不等，则线段相交。 根据您是否想要将触摸的线条视为“相交”，您可以调整您的条件。

Answer 9

如果你的数据定义了行，你只需certificate它们不是平行的。 要做到这一点，你可以计算

 alpha = float(y2 - y1) / (x2 - x1). 

如果Line1和Line2的系数相等，则表示线是平行的。 如果不是，那就意味着它们会相交。

如果他们是平行的，那么你必须certificate他们是不一样的。 为此，你计算

 beta = y1 - alpha*x1 

如果第一行和第二行的beta相同，则意味着您的行相交，因为它们相等

如果他们是细分市场，你仍然需要按照上面所描述的每条线来计算alpha和beta。 那么你必须检查（beta1-beta2）/（alpha1-alpha2）是否大于Min（x1_line1，x2_line1）并小于Max（x1_line1，x2_line1）

Answer 10

计算铺设在你的线段上的线的交点（这意味着基本上解决一个线性方程系统），然后检查它是否在你的线段的起点和终点之间。

Answer 11

这就是我对AS3的了解，对python不太了解，但概念就在那里

  public function getIntersectingPointF($A:Point, $B:Point, $C:Point, $D:Point):Number { var A:Point = $A.clone(); var B:Point = $B.clone(); var C:Point = $C.clone(); var D:Point = $D.clone(); var f_ab:Number = (Dx - Cx) * (Ay - Cy) - (Dy - Cy) * (Ax - Cx); // are lines parallel if (f_ab == 0) { return Infinity }; var f_cd:Number = (Bx - Ax) * (Ay - Cy) - (By - Ay) * (Ax - Cx); var f_d:Number = (Dy - Cy) * (Bx - Ax) - (Dx - Cx) * (By - Ay); var f1:Number = f_ab/f_d var f2:Number = f_cd / f_d if (f1 == Infinity || f1 <= 0 || f1 >= 1) { return Infinity }; if (f2 == Infinity || f2 <= 0 || f2 >= 1) { return Infinity }; return f1; } public function getIntersectingPoint($A:Point, $B:Point, $C:Point, $D:Point):Point { var f:Number = getIntersectingPointF($A, $B, $C, $D); if (f == Infinity || f <= 0 || f >= 1) { return null }; var retPoint:Point = Point.interpolate($A, $B, 1 - f); return retPoint.clone(); } 

Answer 12

对于段AB和CD，findCD的斜率

 slope=(Dy-Cy)/(Dx-Cx) 

把CD放在A和B上，把CD的距离直接往上

 dist1=slope*(Cx-Ax)+Ay-Cy dist2=slope*(Dx-Ax)+Ay-Dy 

检查他们是否在对面

 return dist1*dist2<0 

Answer 13

在JAVA中实现。 然而，它似乎不适用于共线性线段（又名线段L1（0,0）（10,10）L2（1,1）（2,2）

 public class TestCode { public class Point { public double x = 0; public double y = 0; public Point(){} } public class Line { public Point p1, p2; public Line( double x1, double y1, double x2, double y2) { p1 = new Point(); p2 = new Point(); p1.x = x1; p1.y = y1; p2.x = x2; p2.y = y2; } } //line segments private static Line s1; private static Line s2; public TestCode() { s1 = new Line(0,0,0,10); s2 = new Line(-1,0,0,10); } public TestCode(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) { s1 = new Line(x1,y1, x2,y2); s2 = new Line(x3,y3, x4,y4); } public static void main(String args[]) { TestCode code = null; //////////////////////////// code = new TestCode(0,0,0,10, 0,1,0,5); if( intersect(code) ) { System.out.println( "OK COLINEAR: INTERSECTS" ); } else { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(0,0,0,10, 0,1,0,10); if( intersect(code) ) { System.out.println( "OK COLINEAR: INTERSECTS" ); } else { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(0,0,10,0, 5,0,15,0); if( intersect(code) ) { System.out.println( "OK COLINEAR: INTERSECTS" ); } else { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(0,0,10,0, 0,0,15,0); if( intersect(code) ) { System.out.println( "OK COLINEAR: INTERSECTS" ); } else { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(0,0,10,10, 1,1,5,5); if( intersect(code) ) { System.out.println( "OK COLINEAR: INTERSECTS" ); } else { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(0,0,0,10, -1,-1,0,10); if( intersect(code) ) { System.out.println( "OK SLOPE END: INTERSECTS" ); } else { System.out.println( "ERROR SLOPE END: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(-10,-10,10,10, -10,10,10,-10); if( intersect(code) ) { System.out.println( "OK SLOPE Intersect(0,0): INTERSECTS" ); } else { System.out.println( "ERROR SLOPE Intersect(0,0): DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(-10,-10,10,10, -3,-2,50,-2); if( intersect(code) ) { System.out.println( "OK SLOPE Line2 VERTIAL: INTERSECTS" ); } else { System.out.println( "ERROR SLOPE Line2 VERTICAL: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(-10,-10,10,10, 50,-2,-3,-2); if( intersect(code) ) { System.out.println( "OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS" ); } else { System.out.println( "ERROR SLOPE Line2 (reversed) VERTICAL: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(0,0,0,10, 1,0,1,10); if( intersect(code) ) { System.out.println( "ERROR PARALLEL VERTICAL: INTERSECTS" ); } else { System.out.println( "OK PARALLEL VERTICAL: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(0,2,10,2, 0,10,10,10); if( intersect(code) ) { System.out.println( "ERROR PARALLEL HORIZONTAL: INTERSECTS" ); } else { System.out.println( "OK PARALLEL HORIZONTAL: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(0,10,5,13.75, 0,18.75,10,15); if( intersect(code) ) { System.out.println( "ERROR PARALLEL SLOPE=.75: INTERSECTS" ); } else { System.out.println( "OK PARALLEL SLOPE=.75: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(0,0,1,1, 2,-1,2,10); if( intersect(code) ) { System.out.println( "ERROR SEPERATE SEGMENTS: INTERSECTS" ); } else { System.out.println( "OK SEPERATE SEGMENTS: DO NOT INTERSECT" ); } //////////////////////////// code = new TestCode(0,0,1,1, -1,-10,-5,10); if( intersect(code) ) { System.out.println( "ERROR SEPERATE SEGMENTS 2: INTERSECTS" ); } else { System.out.println( "OK SEPERATE SEGMENTS 2: DO NOT INTERSECT" ); } } public static boolean intersect( TestCode code ) { return intersect( code.s1, code.s2); } public static boolean intersect( Line line1, Line line2 ) { double i1min = Math.min(line1.p1.x, line1.p2.x); double i1max = Math.max(line1.p1.x, line1.p2.x); double i2min = Math.min(line2.p1.x, line2.p2.x); double i2max = Math.max(line2.p1.x, line2.p2.x); double iamax = Math.max(i1min, i2min); double iamin = Math.min(i1max, i2max); if( Math.max(line1.p1.x, line1.p2.x) < Math.min(line2.p1.x, line2.p2.x) ) return false; double m1 = (line1.p2.y - line1.p1.y) / (line1.p2.x - line1.p1.x ); double m2 = (line2.p2.y - line2.p1.y) / (line2.p2.x - line2.p1.x ); if( m1 == m2 ) return false; //b1 = line1[0][1] - m1 * line1[0][0] //b2 = line2[0][1] - m2 * line2[0][0] double b1 = line1.p1.y - m1 * line1.p1.x; double b2 = line2.p1.y - m2 * line2.p1.x; double x1 = (b2 - b1) / (m1 - m2); if( (x1 < Math.max(i1min, i2min)) || (x1 > Math.min(i1max, i2max)) ) return false; return true; } } 

到目前为止的输出是

 ERROR COLINEAR: DO NOT INTERSECT ERROR COLINEAR: DO NOT INTERSECT ERROR COLINEAR: DO NOT INTERSECT ERROR COLINEAR: DO NOT INTERSECT ERROR COLINEAR: DO NOT INTERSECT OK SLOPE END: INTERSECTS OK SLOPE Intersect(0,0): INTERSECTS OK SLOPE Line2 VERTIAL: INTERSECTS OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS OK PARALLEL VERTICAL: DO NOT INTERSECT OK PARALLEL HORIZONTAL: DO NOT INTERSECT OK PARALLEL SLOPE=.75: DO NOT INTERSECT OK SEPERATE SEGMENTS: DO NOT INTERSECT OK SEPERATE SEGMENTS 2: DO NOT INTERSECT 

Answer 14

这里是另一个python代码来检查闭合段是否相交。 它是http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/中; C ++代码的重写版本。 这个实现涵盖了所有的特殊情况（例如所有的共线点）。

 def on_segment(p, q, r): '''Given three colinear points p, q, r, the function checks if point q lies on line segment "pr" ''' if (q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1])): return True return False def orientation(p, q, r): '''Find orientation of ordered triplet (p, q, r). The function returns following values 0 --> p, q and r are colinear 1 --> Clockwise 2 --> Counterclockwise ''' val = ((q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])) if val == 0: return 0 # colinear elif val > 0: return 1 # clockwise else: return 2 # counter-clockwise def do_intersect(p1, q1, p2, q2): '''Main function to check whether the closed line segments p1 - q1 and p2 - q2 intersect''' o1 = orientation(p1, q1, p2) o2 = orientation(p1, q1, q2) o3 = orientation(p2, q2, p1) o4 = orientation(p2, q2, q1) # General case if (o1 != o2 and o3 != o4): return True # Special Cases # p1, q1 and p2 are colinear and p2 lies on segment p1q1 if (o1 == 0 and on_segment(p1, p2, q1)): return True # p1, q1 and p2 are colinear and q2 lies on segment p1q1 if (o2 == 0 and on_segment(p1, q2, q1)): return True # p2, q2 and p1 are colinear and p1 lies on segment p2q2 if (o3 == 0 and on_segment(p2, p1, q2)): return True # p2, q2 and q1 are colinear and q1 lies on segment p2q2 if (o4 == 0 and on_segment(p2, q1, q2)): return True return False # Doesn't fall in any of the above cases 

下面是一个testing函数来validation它的工作。

 import matplotlib.pyplot as plt def test_intersect_func(): p1 = (1, 1) q1 = (10, 1) p2 = (1, 2) q2 = (10, 2) fig, ax = plt.subplots() ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-') ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-') print(do_intersect(p1, q1, p2, q2)) print(closed_segment_intersect(p1, q1, p2, q2)) p1 = (10, 0) q1 = (0, 10) p2 = (0, 0) q2 = (10, 10) fig, ax = plt.subplots() ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-') ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-') print(do_intersect(p1, q1, p2, q2)) print(closed_segment_intersect(p1, q1, p2, q2)) p1 = (-5, -5) q1 = (0, 0) p2 = (1, 1) q2 = (10, 10) fig, ax = plt.subplots() ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-') ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-') print(do_intersect(p1, q1, p2, q2)) print(closed_segment_intersect(p1, q1, p2, q2)) p1 = (0, 0) q1 = (1, 1) p2 = (1, 1) q2 = (10, 10) fig, ax = plt.subplots() ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-') ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-') print(do_intersect(p1, q1, p2, q2)) print(closed_segment_intersect(p1, q1, p2, q2)) 

Answer 15

我以为我会提供一个很好的Swift解决scheme：

 struct Pt { var x: Double var y: Double } struct LineSegment { var p1: Pt var p2: Pt } func doLineSegmentsIntersect(ls1: LineSegment, ls2: LineSegment) -> Bool { if (ls1.p2.x-ls1.p1.x == 0) { //handle vertical segment1 if (ls2.p2.x-ls2.p1.x == 0) { //both lines are vertical and parallel return false } let x = ls1.p1.x let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x) let c2 = ls2.p1.y-slope2*ls2.p1.x let y = x*slope2+c2 // y intersection point return (y > ls1.p1.y && x < ls1.p2.y) || (y > ls1.p2.y && y < ls1.p1.y) // check if y is between y1,y2 in segment1 } if (ls2.p2.x-ls2.p1.x == 0) { //handle vertical segment2 let x = ls2.p1.x let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x) let c1 = ls1.p1.y-slope1*ls1.p1.x let y = x*slope1+c1 // y intersection point return (y > ls2.p1.y && x < ls2.p2.y) || (y > ls2.p2.y && y < ls2.p1.y) // validate that y is between y1,y2 in segment2 } let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x) let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x) if (slope1 == slope2) { //segments are parallel return false } let c1 = ls1.p1.y-slope1*ls1.p1.x let c2 = ls2.p1.y-slope2*ls2.p1.x let x = (c2-c1)/(slope1-slope2) return (((x > ls1.p1.x && x < ls1.p2.x) || (x > ls1.p2.x && x < ls1.p1.x)) && ((x > ls2.p1.x && x < ls2.p2.x) || (x > ls2.p2.x && x < ls2.p1.x))) //validate that x is between x1,x2 in both segments } 

Answer 16

解决但仍然为什么不与python … 🙂

 def islineintersect(line1, line2): i1 = [min(line1[0][0], line1[1][0]), max(line1[0][0], line1[1][0])] i2 = [min(line2[0][0], line2[1][0]), max(line2[0][0], line2[1][0])] ia = [max(i1[0], i2[0]), min(i1[1], i2[1])] if max(line1[0][0], line1[1][0]) < min(line2[0][0], line2[1][0]): return False m1 = (line1[1][1] - line1[0][1]) * 1. / (line1[1][0] - line1[0][0]) * 1. m2 = (line2[1][1] - line2[0][1]) * 1. / (line2[1][0] - line2[0][0]) * 1. if m1 == m2: return False b1 = line1[0][1] - m1 * line1[0][0] b2 = line2[0][1] - m2 * line2[0][0] x1 = (b2 - b1) / (m1 - m2) if (x1 < max(i1[0], i2[0])) or (x1 > min(i1[1], i2[1])): return False return True 

这个：

 print islineintersect([(15, 20), (100, 200)], [(210, 5), (23, 119)]) 

输出：

 True 

和这个：

 print islineintersect([(15, 20), (100, 200)], [(-1, -5), (-5, -5)]) 

输出：

 False