你如何检测两条线段相交？
我如何确定两条线是否相交，如果是这样，在x，y点上？
对于使用向量交叉产品的这个问题有一个很好的方法。 定义二维向量叉积v × w为v x w y – v y w x 。
假设两条线段从p到p + r ，从q到q + s 。 那么第一行的任何一点都可以表示为p + t r （对于标量参数t ），第二行上的任意点表示为q + u s （对于标量参数u ）。
这两条线相交，如果我们能findt和u这样的话：
p + t r = q + u s
越过双方，越来越
（ p + t r ）× s =（ q + u s ）× s
而且由于s × s = 0，这意味着
t （ r × s ）=（ q – p ）× s
因此，解决t ：
t =（ q – p ）× s /（ r × s ）
同样的，我们可以解决你的问题 ：
（ p + t r ）× r =（ q + u s ）× r
u （ s × r ）=（ p – q ）× r
u =（ p – q ）× r /（ s × r ）
为了减less计算步骤的数量，可以方便地将其重写如下（记住s × r = – r × s ）：
u =（ q – p ）× r /（ r × s ）
现在有四种情况：
-
如果r × s = 0且（ q – p ）× r = 0，那么两条线是共线的。
在这种情况下，用第一条线段（ p + t r ）的方程表示第二段（ q和q + s ）的端点：
t 0 =（ q – p ）· r /（ r · r ）
t 1 =（ q + s – p ）· r /（ r · r ）= t 0 + s · r /（ r · r ）
如果t 0与t 1之间的间隔与区间[0,1]相交，则线段共线并重叠; 否则它们是共线的，不相交的。
请注意，如果s和r指向相反方向，则s · r <0，因此要检查的区间是[ t 1 ， t 0 ]而不是[ t 0 ， t 1 ]。
-
如果r × s = 0且（ q – p ）× r ≠0，则两条线平行且不相交。
-
如果r × s ≠0且0≤t≤1且0≤u≤1，则两条线段在点p + t r = q + u s处相遇。
-
否则，两条线段不平行但不相交。
学分：这种方法是Ronald Goldman在“ graphicsgem ”第304页上发表的文章“三维空间中的两条线相交”的三维交线algorithm的二维特化 。在三维中，通常情况是线是倾斜的（既不平行也不相交），在这种情况下，该方法给出两条线最接近的点。
FWIW，以下函数（C中）都检测线交点并确定交点。 它基于Andre LeMothe的“ Windows游戏编程大师的技巧 ”中的algorithm。 这与其他答案中的一些algorithm没有什么不同（例如Gareth's）。 然后LeMothe使用克莱默法则（不要问我）来解决方程本身。
我可以certificate它在我的弱小小行星克隆中起作用，似乎正确地处理了Elemental，Dan和Wodzu在其他答案中所描述的边界情况。 这也可能比KingNestor发布的代码更快，因为它们都是乘法和除法，没有平方根！
我想这里有一些零分的潜力，尽pipe这对我来说不是问题。 很容易修改，以避免崩溃无论如何。
// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines // intersect the intersection point may be stored in the floats i_x and i_y. char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y) { float s1_x, s1_y, s2_x, s2_y; s1_x = p1_x - p0_x; s1_y = p1_y - p0_y; s2_x = p3_x - p2_x; s2_y = p3_y - p2_y; float s, t; s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y); t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y); if (s >= 0 && s <= 1 && t >= 0 && t <= 1) { // Collision detected if (i_x != NULL) *i_x = p0_x + (t * s1_x); if (i_y != NULL) *i_y = p0_y + (t * s1_y); return 1; } return 0; // No collision }
顺便说一句，我必须说，在LeMothe的书中，虽然他显然得到了正确的algorithm，但是他具体的例子是插错了数字，计算错误。 例如：
（4 *（4-1）+12 *（7-1））/（17 * 4 + 12 * 10）
= 844 / 0.88
= 0.44
这让我困惑了好几个小时 。 🙁
问题归结为这个问题：从A到B和从C到D的两条线相交？ 然后你可以问四次（在矩形的四边之间的直线和每一边之间）。
这是做这个vectormath。 我假设从A到B的线是所讨论的线，从C到D的线是矩形线之一。 我的符号是Ax是“A的X坐标”， Cy是C的“Y坐标”。 而“ * ”表示点积，所以例如A*B = Ax*Bx + Ay*By 。
E = BA = ( Bx-Ax, By-Ay ) F = DC = ( Dx-Cx, Dy-Cy ) P = ( -Ey, Ex ) h = ( (AC) * P ) / ( F * P )
这个h数是关键。 如果h在0和1之间，这些线相交，否则它们不相交。 如果F*P为零，当然你不能进行计算，但在这种情况下，线是平行的，因此只在明显的情况下相交。
确切的交点是C + F*h 。
更多乐趣：
如果h 正好是 0或1那么这些线就会触及一个终点。 你可以认为这是一个“交集”，或者不是你认为合适的。
具体来说， h是多less，你必须乘以线的长度，以精确触摸另一条线。
因此，如果h<0 ，则表示矩形线在给定线之后（“方向”从“A到B”），并且如果h>1 ，矩形线在给定线的“前方” 。
推导：
A和C是指向行首的向量; E和F是来自A和C末端的形成该线的vector。
对于平面中的任何两条非平行线，必须有一对标量g和h ，这个公式成立：
A + E*g = C + F*h
为什么？ 因为两条不平行的线必须相交，这意味着您可以缩放两条线并相互接触。
（ 起初，这看起来像是一个带有两个未知数的单方程！但是，当你认为这是一个二维向量方程，这意味着这实际上是x和y的一对方程）。
我们必须消除这些variables之一。 一个简单的方法是使E项为零。 要做到这一点，采用等式两边的点积，使用一个向量，它将用点E归零。这个向量我称之为P ，我做了E的明显变换。
你现在有：
A*P = C*P + F*P*h (AC)*P = (F*P)*h ( (AC)*P ) / (F*P) = h
我试图实现这个由Jason精心描述的algorithm。 不幸的是，虽然在debugging中通过math工作，但我发现许多情况下，它不工作。
例如，考虑点A（10,10）B（20,20）C（10,1）D（1,10）给出h = 0.5，然而通过检查可以清楚地看出这些段是没有的，其他。
通过图表可以清楚地看出，0 <h <1的标准仅仅表示如果截取点存在，则截取点将位于CD上，但是不知道该点是否位于AB上。 为了确保存在一个交叉点，必须对variablesg进行对称计算，截取的要求为：0 <g <1 AND 0 <h <1
加文的回答是一个改进。 marcp的解决scheme也是类似的，但是既不推迟分割。
事实上，这也是Gareth Rees的答案的一个实际应用，因为2D中的交叉乘积的等价物是perp-dot乘积，这就是这个代码使用的三个乘积。 切换到3D并使用交叉积，在最后插入s和t，得到3D中线之间的两个最接近的点。 无论如何，2D解决scheme：
int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y) { float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t; s10_x = p1_x - p0_x; s10_y = p1_y - p0_y; s32_x = p3_x - p2_x; s32_y = p3_y - p2_y; denom = s10_x * s32_y - s32_x * s10_y; if (denom == 0) return 0; // Collinear bool denomPositive = denom > 0; s02_x = p0_x - p2_x; s02_y = p0_y - p2_y; s_numer = s10_x * s02_y - s10_y * s02_x; if ((s_numer < 0) == denomPositive) return 0; // No collision t_numer = s32_x * s02_y - s32_y * s02_x; if ((t_numer < 0) == denomPositive) return 0; // No collision if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive)) return 0; // No collision // Collision detected t = t_numer / denom; if (i_x != NULL) *i_x = p0_x + (t * s10_x); if (i_y != NULL) *i_y = p0_y + (t * s10_y); return 1; }
基本上推迟到最后一刻为止，并且移动大部分的testing，直到某些计算完成，从而增加了早期输出。 最后还避免了线条平行时出现的零点划分。
你也可以考虑使用epsilontesting，而不是比较零。 非常接近并行的行可以产生稍微偏离的结果。 这不是一个错误，这是浮点math的一个限制。
问题C：如何检测两条线段是否相交？
我已经find了同样的话题，我对答案并不满意。 所以我写了一篇文章，解释了非常详细的如何检查两个线段是否与很多图像相交 。 有完整的（和testing过的）Java代码。
这里是文章，裁剪到最重要的部分：
检查线段a是否与线段b相交的algorithm如下所示：
什么是边界框？ 这里是两个线段的两个边界框：
如果两个边界框都有交点，则移动线段a，使得一个点位于（0 | 0）处。 现在你有一条由a定义的原点。 现在以相同的方式移动线段b，并检查线段b的新点是否在线a的不同侧。 如果是这种情况，请用相反的方法检查。 如果也是这种情况，则线段相交。 如果不是，他们不相交。
问题A：两条线段相交？
你知道两条线段a和b相交。 如果您不知道，请使用我在“问题C”中提供的工具进行检查。
现在，您可以通过一些案例，并获得7年级math解决scheme（请参阅代码和交互式示例 ）。
问题B：你如何检测两条线是否相交？
假设你的点A = (x1, y1) ，点B = (x2, y2) ， C = (x_3, y_3) ， D = (x_4, y_4) 。 你的第一行由AB（A！= B）定义，第二行由CD（C！= D）定义。
function doLinesIntersect(AB, CD) { if (x1 == x2) { return !(x3 == x4 && x1 != x3); } else if (x3 == x4) { return true; } else { // Both lines are not parallel to the y-axis m1 = (y1-y2)/(x1-x2); m2 = (y3-y4)/(x3-x4); return m1 != m2; } }
问题D：两条线相交？
检查问题B是否相交。
线a和b由每条线的两点定义。 基本上可以应用与问题A相同的逻辑。
曾经在这里接受的答案是不正确的（从那以后，这个答案就不被接受了，所以很快！）。 它不能正确消除所有非交叉点。 平凡它可能似乎工作，但它可以失败，尤其是在0和1被认为是有效的情况下。
考虑以下情况：
（4,1） – （5,1）和（0,0） – （0,2）
这些是明显不重叠的垂直线。
A =（4,1）
B =（5,1）
C =（0,0）
d =（0,2）
E =（5,1） – （4,1）=（ – 1,0）
F =（0,2） – （0,0）=（0，-2）
P =（0,1）
h =（（4,1） – （0,0））点（0,1）/（（0，-2）点（0,1））= 0
根据上面的答案，这两条线段在一个端点（0和1的值）相交。 该端点将是：
（0,0）+（0，-2）* 0 =（0,0）
所以，显然这两条线段在CD上的（0,0）处相遇，但不在AB线上。 那么是怎么回事？ 答案是0和1的值是无效的，有时只有HAPPEN才能正确预测端点的交集。 当一条线（但不是另一条线）的扩展符合线段时，该algorithm预测线段的交集，但这是不正确的。 我想通过testing从AB对CD开始，然后用CD对AB进行testing，这个问题将被消除。 只有在0和1之间都包含的情况下才可以说是相交的。
如果您必须预测终点，我推荐使用向量叉积法。
-担
Python版本的iMalc的答案：
def find_intersection( p0, p1, p2, p3 ) : s10_x = p1[0] - p0[0] s10_y = p1[1] - p0[1] s32_x = p3[0] - p2[0] s32_y = p3[1] - p2[1] denom = s10_x * s32_y - s32_x * s10_y if denom == 0 : return None # collinear denom_is_positive = denom > 0 s02_x = p0[0] - p2[0] s02_y = p0[1] - p2[1] s_numer = s10_x * s02_y - s10_y * s02_x if (s_numer < 0) == denom_is_positive : return None # no collision t_numer = s32_x * s02_y - s32_y * s02_x if (t_numer < 0) == denom_is_positive : return None # no collision if (s_numer > denom) == denom_is_positive or (t_numer > denom) == denom_is_positive : return None # no collision # collision detected t = t_numer / denom intersection_point = [ p0[0] + (t * s10_x), p0[1] + (t * s10_y) ] return intersection_point
只是想提一个很好的解释和明确的解决scheme可以在数字食谱系列中find。 我有第三版，答案见第1117页第21.4节。 Marina Gavrilova Reliable Line Section相交testing的论文中可以find另一个不同命名的解决scheme。 在我看来，她的解决办法是简单一点。
我的实现如下：
bool NuGeometry::IsBetween(const double& x0, const double& x, const double& x1){ return (x >= x0) && (x <= x1); } bool NuGeometry::FindIntersection(const double& x0, const double& y0, const double& x1, const double& y1, const double& a0, const double& b0, const double& a1, const double& b1, double& xy, double& ab) { // four endpoints are x0, y0 & x1,y1 & a0,b0 & a1,b1 // returned values xy and ab are the fractional distance along xy and ab // and are only defined when the result is true bool partial = false; double denom = (b0 - b1) * (x0 - x1) - (y0 - y1) * (a0 - a1); if (denom == 0) { xy = -1; ab = -1; } else { xy = (a0 * (y1 - b1) + a1 * (b0 - y1) + x1 * (b1 - b0)) / denom; partial = NuGeometry::IsBetween(0, xy, 1); if (partial) { // no point calculating this unless xy is between 0 & 1 ab = (y1 * (x0 - a1) + b1 * (x1 - x0) + y0 * (a1 - x1)) / denom; } } if ( partial && NuGeometry::IsBetween(0, ab, 1)) { ab = 1-ab; xy = 1-xy; return true; } else return false; }
C和Objective-C
根据Gareth Rees的回答
const AGKLine AGKLineZero = (AGKLine){(CGPoint){0.0, 0.0}, (CGPoint){0.0, 0.0}}; AGKLine AGKLineMake(CGPoint start, CGPoint end) { return (AGKLine){start, end}; } double AGKLineLength(AGKLine l) { return CGPointLengthBetween_AGK(l.start, l.end); } BOOL AGKLineIntersection(AGKLine l1, AGKLine l2, CGPoint *out_pointOfIntersection) { // http://stackoverflow.com/a/565282/202451 CGPoint p = l1.start; CGPoint q = l2.start; CGPoint r = CGPointSubtract_AGK(l1.end, l1.start); CGPoint s = CGPointSubtract_AGK(l2.end, l2.start); double s_r_crossProduct = CGPointCrossProductZComponent_AGK(r, s); double t = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), s) / s_r_crossProduct; double u = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), r) / s_r_crossProduct; if(t < 0 || t > 1.0 || u < 0 || u > 1.0) { if(out_pointOfIntersection != NULL) { *out_pointOfIntersection = CGPointZero; } return NO; } else { if(out_pointOfIntersection != NULL) { CGPoint i = CGPointAdd_AGK(p, CGPointMultiply_AGK(r, t)); *out_pointOfIntersection = i; } return YES; } } CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2) { return v1.x * v2.y - v1.y * v2.x; } CGPoint CGPointSubtract_AGK(CGPoint p1, CGPoint p2) { return (CGPoint){p1.x - p2.x, p1.y - p2.y}; } CGPoint CGPointAdd_AGK(CGPoint p1, CGPoint p2) { return (CGPoint){p1.x + p2.x, p1.y + p2.y}; } CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2) { return v1.x * v2.y - v1.y * v2.x; } CGPoint CGPointMultiply_AGK(CGPoint p1, CGFloat factor) { return (CGPoint){p1.x * factor, p1.y * factor}; }
许多function和结构都是私有的，但是你应该很容易知道发生了什么。 这是公共的这个回购https://github.com/hfossli/AGGeometryKit/
这对我来说很好。 从这里采取。
// calculates intersection and checks for parallel lines. // also checks that the intersection point is actually on // the line segment p1-p2 Point findIntersection(Point p1,Point p2, Point p3,Point p4) { float xD1,yD1,xD2,yD2,xD3,yD3; float dot,deg,len1,len2; float segmentLen1,segmentLen2; float ua,ub,div; // calculate differences xD1=p2.x-p1.x; xD2=p4.x-p3.x; yD1=p2.y-p1.y; yD2=p4.y-p3.y; xD3=p1.x-p3.x; yD3=p1.y-p3.y; // calculate the lengths of the two lines len1=sqrt(xD1*xD1+yD1*yD1); len2=sqrt(xD2*xD2+yD2*yD2); // calculate angle between the two lines. dot=(xD1*xD2+yD1*yD2); // dot product deg=dot/(len1*len2); // if abs(angle)==1 then the lines are parallell, // so no intersection is possible if(abs(deg)==1) return null; // find intersection Pt between two lines Point pt=new Point(0,0); div=yD2*xD1-xD2*yD1; ua=(xD2*yD3-yD2*xD3)/div; ub=(xD1*yD3-yD1*xD3)/div; pt.x=p1.x+ua*xD1; pt.y=p1.y+ua*yD1; // calculate the combined length of the two segments // between Pt-p1 and Pt-p2 xD1=pt.x-p1.x; xD2=pt.x-p2.x; yD1=pt.y-p1.y; yD2=pt.y-p2.y; segmentLen1=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2); // calculate the combined length of the two segments // between Pt-p3 and Pt-p4 xD1=pt.x-p3.x; xD2=pt.x-p4.x; yD1=pt.y-p3.y; yD2=pt.y-p4.y; segmentLen2=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2); // if the lengths of both sets of segments are the same as // the lenghts of the two lines the point is actually // on the line segment. // if the point isn't on the line, return null if(abs(len1-segmentLen1)>0.01 || abs(len2-segmentLen2)>0.01) return null; // return the valid intersection return pt; } class Point{ float x,y; Point(float x, float y){ this.x = x; this.y = y; } void set(float x, float y){ this.x = x; this.y = y; } }
上面提供了很多解决scheme，但是我认为下面的解决scheme非常简单易懂。
两个分段vectorAB和vectorCD相交当且仅当
- 端点a和b位于分段CD的相反侧。
- 端点c和d位于段AB的相反侧。
更具体地说，当且仅当两个三元组a，c，d和b，c，d中的一个是逆时针顺序时，a和b位于分段CD的相对侧。
Intersect(a, b, c, d) if CCW(a, c, d) == CCW(b, c, d) return false; else if CCW(a, b, c) == CCW(a, b, d) return false; else return true;
这里CCW代表逆时针方向，根据点的方向返回真/假。
资料来源： http : //compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf Page 2
我在这里尝试了很多其他的答案，大部分都是错误的。 下面提供的代码是我用于编程比赛的，这意味着它已经过对裁判数据的testing。 此代码工作 。 是的，这是有点长，但它是有据可查的。
从本质上来说，细分市场可能会发生三件事情：
1）段不相交
2）有一个独特的交点
3）路口是另一段
这个代码将解释所有三种情况。
重要提示 ：此代码仅针对整数坐标进行了testing。 它*应该*为真正的数字工作，但我没有testing过自己。
#include <iostream> #include <cmath> #define EPS 0.00001 // Epsilon using namespace std; struct PT { double x; double y; }; inline bool ptsAreEqual(PT *pt1, PT *pt2) { return fabs(pt1->x-pt2->x) < EPS && fabs(pt1->y - pt2->y) < EPS; } // To find orientation of ordered triplet (a, b, c). // The function returns following values // 0 --> a, b and c are collinear // 1 --> Clockwise (Right of line formed by the segment) // 2 --> Counterclockwise (Left of line formed by the segment) int orientation(PT a, PT b, PT c) { double val = (by - ay) * (cx - bx) - (bx - ax) * (cy - by); if ( fabs(val) < EPS) return 0; // collinear return (val > 0) ? 1: 2; // clock or counterclock wise } // Tests whether or not a point c is on the segment [a, b] bool pointOnLine(PT a, PT b, PT c) { bool is_collinear = orientation(a,b,c); if (is_collinear == 0) { if ( min(ax, bx) <= cx && cx <= max(ax, bx)) { if ( min(ay, by) <= cy && cy <= max(ay, by) ) { return true; } else return false; } else return false; } else return false; } // Test if two line segments [p1, p2] & [p3, p4] intersect bool doIntersect(PT p1, PT p2, PT p3, PT p4) { // find orientations int o1 = orientation(p1, p2, p3); int o2 = orientation(p1, p2, p4); int o3 = orientation(p3, p4, p1); int o4 = orientation(p3, p4, p2); // General case if (o1 != o2 && o3 != o4) return true; // Collinear special cases if (o1 == 0 && pointOnLine(p1, p2, p3)) return true; if (o2 == 0 && pointOnLine(p1, p2, p4)) return true; if (o3 == 0 && pointOnLine(p3, p4, p1)) return true; if (o4 == 0 && pointOnLine(p3, p4, p2)) return true; return false; } /* * Returns the points that the two segments have in common * Returns 0 - No points in common * 1 - One point in common (stored in pt1) * 2 - Two points in common (stored in pt2) * 3 - Both segments are actually the same point */ int segmentCommonEndpoints(PT *p1, PT *p2, PT *p3, PT *p4, PT *pt1, PT *pt2) { int count = 0; // All points are the same if (ptsAreEqual(p1, p2) && ptsAreEqual(p2, p3) && ptsAreEqual(p3, p4)) { *pt1 = *p1; pt2 = nullptr; return 3; } else { if ( ptsAreEqual(p1, p3) ) { *pt1 = *p1; count++; if (ptsAreEqual(p2, p4)) { *pt2 = *p2; count++; } } else if ( ptsAreEqual(p1, p4) ) { *pt1 = *p1; count++; if ( ptsAreEqual(p2, p3) ) { *pt2 = *p2; count++; } } else if (ptsAreEqual(p2, p3)) { *pt1 = *p2; count++; if (ptsAreEqual(p1, p4)) { *pt2 = *p1; count++; } } else if (ptsAreEqual(p2, p4)) { *pt1 = *p2; count++; if (ptsAreEqual(p1, p3)) { *pt2 = *p1; count++; } } } if (count == 0) { pt1 = nullptr; pt2 = nullptr; } else if (count == 1) { pt2 = nullptr; } return count; } /* p1 & p2 are part of the first segment and p3 & p4 are part of the second segment. I0 and I1 are the pointers which get set when intersection point(s) are found. Returns: 0 - No intersection 1 - Unique intersection set in I0 2 - Segment intersection set in [I0, I1] */ int segment_segment_intersection (PT p1, PT p2, PT p3, PT p4, PT *I0, PT *I1 ) { if (doIntersect(p1, p2, p3, p4)) { PT* pt1 = new PT; PT* pt2 = new PT; int num_common_endpoints = segmentCommonEndpoints(&p1, &p2, &p3, &p4, pt1, pt2); bool singleton = ptsAreEqual(&p1, &p2) || ptsAreEqual(&p3, &p4); if (num_common_endpoints == 3) { *I0 = *pt1; I1 = nullptr; return 1; } else if (num_common_endpoints == 2) { *I0 = *pt1; *I1 = *pt2; return 2; // There is a unique singleton } else if (num_common_endpoints == 1 && singleton) { *I0 = *pt1; I1 = nullptr; return 1; } else { bool pts_form_straight_line = (orientation(p1, p2, p3) == 0) && (orientation(p1, p2, p4) == 0); // The intersection will be a 'subsegment' of the two segments because they overlap if ( pts_form_straight_line ) { // Segment #2 is fully enclosed in Segment #1 if ( pointOnLine(p1, p2, p3) && pointOnLine(p1, p2, p4) ) { *I0 = p3; *I1 = p4; // Segment #1 is fully enclosed in Segment #2 } else if ( pointOnLine(p3, p4, p1) && pointOnLine(p3, p4, p2) ) { *I0 = p1; *I1 = p2; // The subsegment is part of segment #1 and part of segment #2 } else { // Find 'middle points' if (pointOnLine(p1, p2, p3)) *I0 = p3; else *I0 = p4; if (pointOnLine(p3, p4, p1)) *I1 = p1; else *I1 = p2; } // There is actually only one middle point if (ptsAreEqual(I0, I1)) { I1 = nullptr; return 1; } return 2; // Unique intersection point } else { // Segment 1 is vertical line if ( fabs(p2.x - p1.x) < EPS) { double m2 = (p4.y - p3.y) / (p4.x - p3.x); double b2 = p3.y - m2*p3.x; I0->x = p1.x; I0->y = m2*p1.x + b2; // Segment 2 is vertical line } else if ( fabs(p4.x - p3.x) < EPS ) { double m1 = (p2.y - p1.y) / (p2.x - p1.x); double b1 = p1.y - m1*p1.x; I0->x = p3.x; I0->y = m1*p3.x + b1; // Sloped line } else { double m1 = (p2.y - p1.y) / (p2.x - p1.x); double m2 = (p4.y - p3.y) / (p4.x - p3.x); double b1 = p1.y - m1*p1.x; double b2 = p3.y - m2*p3.x; I0->x = (b2 - b1) / (m1 - m2); I0->y = (m1*b2 - m2*b1) / (m1 - m2); } I1 = nullptr; return 1; } } // No intersection exists } else { I0 = nullptr; I1 = nullptr; return 0; } }
这是一个简单的用法示例：
int main(int argc, char const *argv[]) { // Segment 1 PT p1 = {x1, y1}; PT p2 = {x2, y2}; // Segment 2 PT p3 = {x3, y3}; PT p4 = {x4, y4}; PT * intersection1 = new PT; PT * intersection2 = new PT; int ret = segment_segment_intersection(p1, p2, p3, p4, intersection1, intersection2); if (ret == 0) { // No intersection } else if (ret == 1) { // Unique Point at // intersection1->x, intersection1->y } else if (ret == 2) { // Intersection is a segment from // [intersection1->x, intersection1->y] to [intersection2->x, intersection2->y] } return 0; }
我尝试了一些这样的答案，但他们没有为我工作（对不起，伙计们）; 经过更多的networkingsearch，我发现这一点 。
稍加修改他的代码，我现在有这个函数将返回交点，或者如果找不到交点，它将返回-1，-1。
Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point '// Determines the intersection point of the line segment defined by points A and B '// with the line segment defined by points C and D. '// '// Returns YES if the intersection point was found, and stores that point in X,Y. '// Returns NO if there is no determinable intersection point, in which case X,Y will '// be unmodified. Dim distAB, theCos, theSin, newX, ABpos As Double '// Fail if either line segment is zero-length. If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1) '// Fail if the segments share an end-point. If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1) '// (1) Translate the system so that point A is on the origin. bx -= ax by -= ay cx -= ax cy -= ay dx -= ax dy -= ay '// Discover the length of segment AB. distAB = Math.Sqrt(bx * bx + by * by) '// (2) Rotate the system so that point B is on the positive X axis. theCos = bx / distAB theSin = by / distAB newX = cx * theCos + cy * theSin cy = cy * theCos - cx * theSin cx = newX newX = dx * theCos + dy * theSin dy = dy * theCos - dx * theSin dx = newX '// Fail if segment CD doesn't cross line AB. If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1) '// (3) Discover the position of the intersection point along line AB. ABpos = dx + (cx - dx) * dy / (dy - cy) '// Fail if segment CD crosses line AB outside of segment AB. If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1) '// (4) Apply the discovered position to line AB in the original coordinate system. '*X=Ax+ABpos*theCos '*Y=Ay+ABpos*theSin '// Success. Return New Point(ax + ABpos * theCos, ay + ABpos * theSin) End Function
I think there is a much much simpler solution for this problem. I came up with another idea today and it seems to work just fine (at least in 2D for now). All you have to do, is to calculate the intersection between two lines, then check if the calculated intersection point is within the boundig boxes of both line segments. If it is, the line segments intersect. 而已。
编辑：
This is how I calculate the intersection (I don't know anymore where I found this code snippet)
Point3D
comes from
System.Windows.Media.Media3D public static Point3D? Intersection(Point3D start1, Point3D end1, Point3D start2, Point3D end2) { double a1 = end1.Y - start1.Y; double b1 = start1.X - end1.X; double c1 = a1 * start1.X + b1 * start1.Y; double a2 = end2.Y - start2.Y; double b2 = start2.X - end2.X; double c2 = a2 * start2.X + b2 * start2.Y; double det = a1 * b2 - a2 * b1; if (det == 0) { // lines are parallel return null; } double x = (b2 * c1 - b1 * c2) / det; double y = (a1 * c2 - a2 * c1) / det; return new Point3D(x, y, 0.0); }
and this is my (simplified for the purpose of the answer) BoundingBox class:
public class BoundingBox { private Point3D min = new Point3D(); private Point3D max = new Point3D(); public BoundingBox(Point3D point) { min = point; max = point; } public Point3D Min { get { return min; } set { min = value; } } public Point3D Max { get { return max; } set { max = value; } } public bool Contains(BoundingBox box) { bool contains = min.X <= box.min.X && max.X >= box.max.X && min.Y <= box.min.Y && max.Y >= box.max.Y && min.Z <= box.min.Z && max.Z >= box.max.Z; return contains; } public bool Contains(Point3D point) { return Contains(new BoundingBox(point)); } }
This solution may help
public static float GetLineYIntesept(PointF p, float slope) { return pY - slope * pX; } public static PointF FindIntersection(PointF line1Start, PointF line1End, PointF line2Start, PointF line2End) { float slope1 = (line1End.Y - line1Start.Y) / (line1End.X - line1Start.X); float slope2 = (line2End.Y - line2Start.Y) / (line2End.X - line2Start.X); float yinter1 = GetLineYIntesept(line1Start, slope1); float yinter2 = GetLineYIntesept(line2Start, slope2); if (slope1 == slope2 && yinter1 != yinter2) return PointF.Empty; float x = (yinter2 - yinter1) / (slope1 - slope2); float y = slope1 * x + yinter1; return new PointF(x, y); }
I ported Kris's above answer to JavaScript. After trying numerous different answers, his provided the correct points. I thought I was going crazy that I wasn't getting the points I needed.
function getLineLineCollision(p0, p1, p2, p3) { var s1, s2; s1 = {x: p1.x - p0.x, y: p1.y - p0.y}; s2 = {x: p3.x - p2.x, y: p3.y - p2.y}; var s10_x = p1.x - p0.x; var s10_y = p1.y - p0.y; var s32_x = p3.x - p2.x; var s32_y = p3.y - p2.y; var denom = s10_x * s32_y - s32_x * s10_y; if(denom == 0) { return false; } var denom_positive = denom > 0; var s02_x = p0.x - p2.x; var s02_y = p0.y - p2.y; var s_numer = s10_x * s02_y - s10_y * s02_x; if((s_numer < 0) == denom_positive) { return false; } var t_numer = s32_x * s02_y - s32_y * s02_x; if((t_numer < 0) == denom_positive) { return false; } if((s_numer > denom) == denom_positive || (t_numer > denom) == denom_positive) { return false; } var t = t_numer / denom; var p = {x: p0.x + (t * s10_x), y: p0.y + (t * s10_y)}; return p; }
I tried lot of ways and then I decided to write my own. 所以这里是：
bool IsBetween (float x, float b1, float b2) { return ( ((x >= (b1 - 0.1f)) && (x <= (b2 + 0.1f))) || ((x >= (b2 - 0.1f)) && (x <= (b1 + 0.1f)))); } bool IsSegmentsColliding( POINTFLOAT lineA, POINTFLOAT lineB, POINTFLOAT line2A, POINTFLOAT line2B) { float deltaX1 = lineB.x - lineA.x; float deltaX2 = line2B.x - line2A.x; float deltaY1 = lineB.y - lineA.y; float deltaY2 = line2B.y - line2A.y; if (abs(deltaX1) < 0.01f && abs(deltaX2) < 0.01f) // Both are vertical lines return false; if (abs((deltaY1 / deltaX1) - (deltaY2 / deltaX2)) < 0.001f) // Two parallel line return false; float xCol = ( ( (deltaX1 * deltaX2) * (line2A.y - lineA.y)) - (line2A.x * deltaY2 * deltaX1) + (lineA.x * deltaY1 * deltaX2)) / ((deltaY1 * deltaX2) - (deltaY2 * deltaX1)); float yCol = 0; if (deltaX1 < 0.01f) // L1 is a vertical line yCol = ((xCol * deltaY2) + (line2A.y * deltaX2) - (line2A.x * deltaY2)) / deltaX2; else // L1 is acceptable yCol = ((xCol * deltaY1) + (lineA.y * deltaX1) - (lineA.x * deltaY1)) / deltaX1; bool isCol = IsBetween(xCol, lineA.x, lineB.x) && IsBetween(yCol, lineA.y, lineB.y) && IsBetween(xCol, line2A.x, line2B.x) && IsBetween(yCol, line2A.y, line2B.y); return isCol; }
Based on these two formulas: (I simplified them from equation of lines and other formulas)
This based on Gareth Ree's answer. It also returns the overlap of the line segments if they do. Coded in C++, V is a simple vector class. Where the cross product of two vectors in 2D returns a single scalar. It was tested and passed by my schools automatic testing system.
//Required input point must be colinear with the line bool on_segment(const V& p, const LineSegment& l) { //If a point is on the line, the sum of the vectors formed by the point to the line endpoints must be equal V va = p - l.pa; V vb = p - l.pb; R ma = va.magnitude(); R mb = vb.magnitude(); R ml = (l.pb - l.pa).magnitude(); R s = ma + mb; bool r = s <= ml + epsilon; return r; } //Compute using vector math // Returns 0 points if the lines do not intersect or overlap // Returns 1 point if the lines intersect // Returns 2 points if the lines overlap, contain the points where overlapping start starts and stop std::vector<V> intersect(const LineSegment& la, const LineSegment& lb) { std::vector<V> r; //http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect V oa, ob, da, db; //Origin and direction vectors R sa, sb; //Scalar values oa = la.pa; da = la.pb - la.pa; ob = lb.pa; db = lb.pb - lb.pa; if (da.cross(db) == 0 && (ob - oa).cross(da) == 0) //If colinear { if (on_segment(lb.pa, la) && on_segment(lb.pb, la)) { r.push_back(lb.pa); r.push_back(lb.pb); dprintf("colinear, overlapping\n"); return r; } if (on_segment(la.pa, lb) && on_segment(la.pb, lb)) { r.push_back(la.pa); r.push_back(la.pb); dprintf("colinear, overlapping\n"); return r; } if (on_segment(la.pa, lb)) r.push_back(la.pa); if (on_segment(la.pb, lb)) r.push_back(la.pb); if (on_segment(lb.pa, la)) r.push_back(lb.pa); if (on_segment(lb.pb, la)) r.push_back(lb.pb); if (r.size() == 0) dprintf("colinear, non-overlapping\n"); else dprintf("colinear, overlapping\n"); return r; } if (da.cross(db) == 0 && (ob - oa).cross(da) != 0) { dprintf("parallel non-intersecting\n"); return r; } //Math trick db cross db == 0, which is a single scalar in 2D. //Crossing both sides with vector db gives: sa = (ob - oa).cross(db) / da.cross(db); //Crossing both sides with vector da gives sb = (oa - ob).cross(da) / db.cross(da); if (0 <= sa && sa <= 1 && 0 <= sb && sb <= 1) { dprintf("intersecting\n"); r.push_back(oa + da * sa); return r; } dprintf("non-intersecting, non-parallel, non-colinear, non-overlapping\n"); return r; }
Here's a basic implementation of a line segment in C#, with corresponding intersection detection code. It requires a 2D vector/point struct called Vector2f , though you can replace this with any other type that has X/Y properties. You could also replace float with double if that suits your needs better.
This code is used in my .NET physics library, Boing .
public struct LineSegment2f { public Vector2f From { get; } public Vector2f To { get; } public LineSegment2f(Vector2f @from, Vector2f to) { From = @from; To = to; } public Vector2f Delta => new Vector2f(To.X - From.X, To.Y - From.Y); /// <summary> /// Attempt to intersect two line segments. /// </summary> /// <remarks> /// Even if the line segments do not intersect, <paramref name="t"/> and <paramref name="u"/> will be set. /// If the lines are parallel, <paramref name="t"/> and <paramref name="u"/> are set to <see cref="float.NaN"/>. /// </remarks> /// <param name="other">The line to attempt intersection of this line with.</param> /// <param name="intersectionPoint">The point of intersection if within the line segments, or empty..</param> /// <param name="t">The distance along this line at which intersection would occur, or NaN if lines are collinear/parallel.</param> /// <param name="u">The distance along the other line at which intersection would occur, or NaN if lines are collinear/parallel.</param> /// <returns><c>true</c> if the line segments intersect, otherwise <c>false</c>.</returns> public bool TryIntersect(LineSegment2f other, out Vector2f intersectionPoint, out float t, out float u) { var p = From; var q = other.From; var r = Delta; var s = other.Delta; // t = (q − p) × s / (r × s) // u = (q − p) × r / (r × s) var denom = Fake2DCross(r, s); if (denom == 0) { // lines are collinear or parallel t = float.NaN; u = float.NaN; intersectionPoint = default(Vector2f); return false; } var tNumer = Fake2DCross(q - p, s); var uNumer = Fake2DCross(q - p, r); t = tNumer / denom; u = uNumer / denom; if (t < 0 || t > 1 || u < 0 || u > 1) { // line segments do not intersect within their ranges intersectionPoint = default(Vector2f); return false; } intersectionPoint = p + r * t; return true; } private static float Fake2DCross(Vector2f a, Vector2f b) { return aX * bY - aY * bX; } }
There seems to be some interest in Gavin's answer for which cortijon proposed a javascript version in the comments and iMalc provided a version with slightly fewer computations . Some have pointed out shortcomings with various code proposals and others have commented on the efficiency of some code proposals.
The algorithm provided by iMalc via Gavin's answer is the one that I am currently using in a javascript project and I just wanted to provide a cleaned up version here if it may help anyone.
// Some variables for reuse, others may do this differently var p0x, p1x, p2x, p3x, ix, p0y, p1y, p2y, p3y, iy, collisionDetected; // do stuff, call other functions, set endpoints... // note: for my purpose I use |t| < |d| as opposed to // |t| <= |d| which is equivalent to 0 <= t < 1 rather than // 0 <= t <= 1 as in Gavin's answer - results may vary var lineSegmentIntersection = function(){ var d, dx1, dx2, dx3, dy1, dy2, dy3, s, t; dx1 = p1x - p0x; dy1 = p1y - p0y; dx2 = p3x - p2x; dy2 = p3y - p2y; dx3 = p0x - p2x; dy3 = p0y - p2y; collisionDetected = 0; d = dx1 * dy2 - dx2 * dy1; if(d !== 0){ s = dx1 * dy3 - dx3 * dy1; if((s <= 0 && d < 0 && s >= d) || (s >= 0 && d > 0 && s <= d)){ t = dx2 * dy3 - dx3 * dy2; if((t <= 0 && d < 0 && t > d) || (t >= 0 && d > 0 && t < d)){ t = t / d; collisionDetected = 1; ix = p0x + t * dx1; iy = p0y + t * dy1; } } } };
If each side of the rectangle is a line segment, and the user drawn portion is a line segment, then you need to just check the user drawn segment for intersection with the four side line segments. This should be a fairly simple exercise given the start and end points of each segment.
A C++ program to check if two given line segments intersect
#include <iostream> using namespace std; struct Point { int x; int y; }; // Given three colinear points p, q, r, the function checks if // point q lies on line segment 'pr' bool onSegment(Point p, Point q, Point r) { if (qx <= max(px, rx) && qx >= min(px, rx) && qy <= max(py, ry) && qy >= min(py, ry)) return true; return false; } // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are colinear // 1 --> Clockwise // 2 --> Counterclockwise int orientation(Point p, Point q, Point r) { // See 10th slides from following link for derivation of the formula // http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf int val = (qy - py) * (rx - qx) - (qx - px) * (ry - qy); if (val == 0) return 0; // colinear return (val > 0)? 1: 2; // clock or counterclock wise } // The main function that returns true if line segment 'p1q1' // and 'p2q2' intersect. bool doIntersect(Point p1, Point q1, Point p2, Point q2) { // Find the four orientations needed for general and // special cases int o1 = orientation(p1, q1, p2); int o2 = orientation(p1, q1, q2); int o3 = orientation(p2, q2, p1); int o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return true; // Special Cases // p1, q1 and p2 are colinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return true; // p1, q1 and p2 are colinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return true; // p2, q2 and p1 are colinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return true; // p2, q2 and q1 are colinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return true; return false; // Doesn't fall in any of the above cases } // Driver program to test above functions int main() { struct Point p1 = {1, 1}, q1 = {10, 1}; struct Point p2 = {1, 2}, q2 = {10, 2}; doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; p1 = {10, 0}, q1 = {0, 10}; p2 = {0, 0}, q2 = {10, 10}; doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; p1 = {-5, -5}, q1 = {0, 0}; p2 = {1, 1}, q2 = {10, 10}; doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; return 0; }
Based on t3chb0t's answer:
int intersezione_linee(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y) { //L1: estremi (x1,y1)(x2,y2) L2: estremi (x3,y3)(x3,y3) int d; d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4); if(!d) return 0; p_x = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d; p_y = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d; return 1; } int in_bounding_box(int x1, int y1, int x2, int y2, int p_x, int p_y) { return p_x>=x1 && p_x<=x2 && p_y>=y1 && p_y<=y2; } int intersezione_segmenti(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y) { if (!intersezione_linee(x1,y1,x2,y2,x3,y3,x4,y4,p_x,p_y)) return 0; return in_bounding_box(x1,y1,x2,y2,p_x,p_y) && in_bounding_box(x3,y3,x4,y4,p_x,p_y); }
I read these algorithm from the book "multiple view geometry"
following text using
' as transpose sign
* as dot product
x as cross product, when using as operator
1. line definition
a point x_vec = (x, y)' lies on the line ax + by + c = 0
we denote L = (a, b, c)', the point as (x, y, 1)' as homogeneous coordinates
the line equation can be written as
(x, y, 1)(a, b, c)' = 0 or x' * L = 0
2. intersection of lines
we have two lines L1=(a1, b1, c1)', L2=(a2, b2, c2)'
assume x is a point, a vector, and x = L1 x L2 (L1 cross product L2).
be careful, x is always a 2D point, please read homogeneous coordinates if you are confused about (L1xL2) is a three elements vector, and x is a 2D coordinates.
according to triple product, we know that
L1 * ( L1 x L2 ) = 0, and L2 * (L1 x L2) = 0, because of L1,L2 co-plane
we substitute (L1xL2) with vector x, then we have L1*x=0, L2*x=0, which means x lie on both L1 and L2, x is the intersection point.
be careful, here x is homogeneous coordinates, if the last element of x is zero, it means L1 and L2 are parallel.
Based on @Gareth Rees answer, version for Python:
import numpy as np def np_perp( a ) : b = np.empty_like(a) b[0] = a[1] b[1] = -a[0] return b def np_cross_product(a, b): return np.dot(a, np_perp(b)) def np_seg_intersect(a, b, considerCollinearOverlapAsIntersect = False): # https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/565282#565282 # http://www.codeproject.com/Tips/862988/Find-the-intersection-point-of-two-line-segments r = a[1] - a[0] s = b[1] - b[0] v = b[0] - a[0] num = np_cross_product(v, r) denom = np_cross_product(r, s) # If rxs = 0 and (q - p) xr = 0, then the two lines are collinear. if np.isclose(denom, 0) and np.isclose(num, 0): # 1. If either 0 <= (q - p) * r <= r * r or 0 <= (p - q) * s <= * s # then the two lines are overlapping, if(considerCollinearOverlapAsIntersect): vDotR = np.dot(v, r) aDotS = np.dot(-v, s) if (0 <= vDotR and vDotR <= np.dot(r,r)) or (0 <= aDotS and aDotS <= np.dot(s,s)): return True # 2. If neither 0 <= (q - p) * r = r * r nor 0 <= (p - q) * s <= s * s # then the two lines are collinear but disjoint. # No need to implement this expression, as it follows from the expression above. return None if np.isclose(denom, 0) and not np.isclose(num, 0): # Parallel and non intersecting return None u = num / denom t = np_cross_product(v, s) / denom if u >= 0 and u <= 1 and t >= 0 and t <= 1: res = b[0] + (s*u) return res # Otherwise, the two line segments are not parallel but do not intersect. return None
Many answers have wrapped up all the calculations into a single function. If you need to calculate the line slopes, y-intercepts, or x-intercepts for use elsewhere in your code, you'll be making those calculations redundantly. I have separated out the respective functions, used obvious variable names, and commented my code to make it easier to follow. I needed to know if lines intersect infinitely beyond their endpoints, so in JavaScript:
http://jsfiddle.net/skibulk/evmqq00u/
var point_a = {x:0, y:10}, point_b = {x:12, y:12}, point_c = {x:10, y:0}, point_d = {x:0, y:0}, slope_ab = slope(point_a, point_b), slope_bc = slope(point_b, point_c), slope_cd = slope(point_c, point_d), slope_da = slope(point_d, point_a), yint_ab = y_intercept(point_a, slope_ab), yint_bc = y_intercept(point_b, slope_bc), yint_cd = y_intercept(point_c, slope_cd), yint_da = y_intercept(point_d, slope_da), xint_ab = x_intercept(point_a, slope_ab, yint_ab), xint_bc = x_intercept(point_b, slope_bc, yint_bc), xint_cd = x_intercept(point_c, slope_cd, yint_cd), xint_da = x_intercept(point_d, slope_da, yint_da), point_aa = intersect(slope_da, yint_da, xint_da, slope_ab, yint_ab, xint_ab), point_bb = intersect(slope_ab, yint_ab, xint_ab, slope_bc, yint_bc, xint_bc), point_cc = intersect(slope_bc, yint_bc, xint_bc, slope_cd, yint_cd, xint_cd), point_dd = intersect(slope_cd, yint_cd, xint_cd, slope_da, yint_da, xint_da); console.log(point_a, point_b, point_c, point_d); console.log(slope_ab, slope_bc, slope_cd, slope_da); console.log(yint_ab, yint_bc, yint_cd, yint_da); console.log(xint_ab, xint_bc, xint_cd, xint_da); console.log(point_aa, point_bb, point_cc, point_dd); function slope(point_a, point_b) { var i = (point_b.y - point_a.y) / (point_b.x - point_a.x); if (i === -Infinity) return Infinity; if (i === -0) return 0; return i; } function y_intercept(point, slope) { // Horizontal Line if (slope == 0) return point.y; // Vertical Line if (slope == Infinity) { // THE Y-Axis if (point.x == 0) return Infinity; // No Intercept return null; } // Angled Line return point.y - (slope * point.x); } function x_intercept(point, slope, yint) { // Vertical Line if (slope == Infinity) return point.x; // Horizontal Line if (slope == 0) { // THE X-Axis if (point.y == 0) return Infinity; // No Intercept return null; } // Angled Line return -yint / slope; } // Intersection of two infinite lines function intersect(slope_a, yint_a, xint_a, slope_b, yint_b, xint_b) { if (slope_a == slope_b) { // Equal Lines if (yint_a == yint_b && xint_a == xint_b) return Infinity; // Parallel Lines return null; } // First Line Vertical if (slope_a == Infinity) { return { x: xint_a, y: (slope_b * xint_a) + yint_b }; } // Second Line Vertical if (slope_b == Infinity) { return { x: xint_b, y: (slope_a * xint_b) + yint_a }; } // Not Equal, Not Parallel, Not Vertical var i = (yint_b - yint_a) / (slope_a - slope_b); return { x: i, y: (slope_a * i) + yint_a }; }
