我如何确定两条直线是否相交，如果相交，在x,y点处?
如果矩形的每条边都是一条线段，并且用户绘制的部分也是一条线段，那么您只需检查用户绘制的线段是否与四条边线段相交。这应该是一个相当简单的练习，给定每个段的起点和终点。
问题可以简化成这样一个问题:从A到B和从C到D的两条直线相交吗?然后你可以问它四次(在直线和矩形的四条边之间)。
这是做这个的矢量数学。假设A到B的直线就是问题中的直线C到D的直线是其中一条矩形直线。我的表示法是Ax是A的x坐标Cy是c的y坐标“*”表示点积，例如A*B = Ax*Bx + Ay*By。
E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy )
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )
h是键。如果h在0和1之间，两条线相交，否则不相交。如果F*P为零，当然不能进行计算，但在这种情况下，直线是平行的，因此只有在明显的情况下才相交。
交点是C + F*h。
更多的乐趣:
如果h恰好等于0或1，两条直线的端点相交。你可以认为这是一个“交集”，也可以认为不是。
具体来说，h是直线长度乘以多少才能恰好与另一条直线相交。
因此，如果h<0，这意味着矩形线在给定直线的“后面”(“方向”是“从A到B”)，如果h>1，矩形线在给定直线的“前面”。
推导:
A和C是指向直线起点的向量;E和F是由A和C端点组成的直线。
对于平面上任意两条不平行线，必须恰好有一对标量g和h，使得这个方程成立:
A + E*g = C + F*h
为什么?因为两条不平行线必须相交，这意味着你可以将这两条线按一定比例缩放并相互接触。
(起初，这看起来像一个有两个未知数的方程!但当你考虑到这是一个二维矢量方程时，它就不是，这意味着这是一对x和y的方程)
我们必须消去其中一个变量。一个简单的方法是使E项为零。要做到这一点，用一个向量对方程两边做点积这个向量与E点乘到0，我把上面的向量称为P，我做了E的明显变换。
你现在有:
A*P = C*P + F*P*h
(A-C)*P = (F*P)*h
( (A-C)*P ) / (F*P) = h
这对我来说很有效。从这里拍的。
// 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;
}
}
有一个很好的方法来解决这个问题就是用向量叉乘。定义二维向量叉乘v × w为vx wy−vy wx。
假设这两条线段从p到p + r，从q到q + s。那么第一行上的任意点都可以表示为p + t r(对于标量参数t)，第二行上的任意点可以表示为q + u s(对于标量参数u)。
如果t和u满足以下条件，两条直线相交:
P + t r = q + u s
两边叉乘s，得到
(p + r) × s = (q + u s) × s
由于s × s = 0，这意味着
T (r × s) = (q−p) × s
因此，求解t:
T = (q−p) × s / (r × s)
同样地，我们可以解出u:
(p + r) × r = (q + u s) × r U (s × r) = (p−q) × r U = (p−q) × r / (s × r)
为了减少计算步骤，可以方便地将其重写为以下形式(记住s × r =−r × s):
U = q−p × r / (r × s)
现在有四种情况:
If r × s = 0 and (q − p) × r = 0, then the two lines are collinear. In this case, express the endpoints of the second segment (q and q + s) in terms of the equation of the first line segment (p + t r): t0 = (q − p) · r / (r · r) t1 = (q + s − p) · r / (r · r) = t0 + s · r / (r · r) If the interval between t0 and t1 intersects the interval [0, 1] then the line segments are collinear and overlapping; otherwise they are collinear and disjoint. Note that if s and r point in opposite directions, then s · r < 0 and so the interval to be checked is [t1, t0] rather than [t0, t1]. If r × s = 0 and (q − p) × r ≠ 0, then the two lines are parallel and non-intersecting. If r × s ≠ 0 and 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, the two line segments meet at the point p + t r = q + u s. Otherwise, the two line segments are not parallel but do not intersect.
来源:该方法是3D线相交算法的2维专门化，来自Ronald Goldman发表在Graphics Gems，第304页的文章“三条线在三维空间中的相交”。在三维空间中，通常的情况是直线是倾斜的(既不平行也不相交)，在这种情况下，该方法给出了两条直线最接近的点。
曾经在这里被接受的答案是不正确的(它已经被不接受了，所以万岁!)它不能正确地消除所有非交点。简单地说，它可能有效，但也可能失败，特别是在0和1被认为对h有效的情况下。
考虑以下情况:
直线(4,1)-(5,1)和(0,0)-(0,2)
这两条垂线显然不重叠。
= (4,1) B =(5、1) C = (0, 0) D = (0, 2) E = (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)
So, apparently the two line segments meet at (0,0), which is on line CD, but not on line AB. So what is going wrong? The answer is that the values of 0 and 1 are not valid and only sometimes HAPPEN to correctly predict endpoint intersection. When the extension of one line (but not the other) would meet the line segment, the algorithm predicts an intersection of line segments, but this is not correct. I imagine that by testing starting with AB vs CD and then also testing with CD vs AB, this problem would be eliminated. Only if both fall between 0 and 1 inclusively can they be said to intersect.
如果你必须预测端点，我建议使用向量叉乘法。
-Dan
我已经尝试实现上述Jason所描述的算法;不幸的是，虽然在调试数学工作，我发现许多情况下，它不起作用。
例如，考虑点A(10,10) B(20,20) C(10,1) D(1,10) h=。5然而，通过检查可以清楚地看到，这些部分彼此一点也不接近。
将其绘制成图可以清楚地看出，0 < h < 1条件仅表明如果存在截距点，则截距点将位于CD上，而不告诉我们该点是否位于AB上。 为了确保有一个交叉点，你必须对变量g进行对称计算，拦截的要求是: 0 < g < 1 AND 0 < h < 1
FWIW，下面的函数(在C中)既检测线的交点，又确定交点。这是基于Andre LeMothe的“Tricks of the Windows Game Programming Gurus”中的一个算法。这与其他答案(例如Gareth的答案)中的一些算法并没有什么不同。然后LeMothe使用克莱默法则(不要问我)来解这些方程。
我可以证明它在我的小行星克隆中起作用，并且似乎正确地处理了Elemental, Dan和Wodzu在其他答案中描述的边缘情况。它也可能比KingNestor发布的代码快，因为它都是乘法和除法，没有平方根!
我想这里有一些除以0的可能性，尽管在我的例子中这不是问题。很容易修改以避免崩溃。
// 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的书中，虽然他显然得到了正确的算法，但他展示的具体示例插入了错误的数字，并且计算错误。例如:
(4 * (4-1) + 12 * (7-1))/(17 * 4 + 12 * 10) = 844/0.88 = 0.44
这让我困惑了好几个小时。：(
我试过其中一些答案，但它们对我不起作用(对不起伙计们);在网上搜索之后，我找到了这个。
对他的代码做了一点修改，我现在有了这个函数，它将返回交点，如果没有找到交点，它将返回- 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 A-B.
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 C-D doesn't cross line A-B.
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 A-B.
ABpos = dx + (cx - dx) * dy / (dy - cy)
'// Fail if segment C-D crosses line A-B outside of segment A-B.
If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)
'// (4) Apply the discovered position to line A-B 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
只是想提一下，一个很好的解释和明确的解决方案可以在数字食谱系列中找到。我有这本书的第三版，答案在1117页21.4节。另一种不同命名的解决方案可以在玛丽娜·加夫里洛娃(Marina Gavrilova)的论文中找到。在我看来，她的解决办法要简单一些。
我的实现如下:
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;
}
以下是对加文回答的改进。马普的解决方案也类似，但都没有推迟分割。
这实际上也是Gareth Rees的答案的一个实际应用，因为向量积在2D中的等价是补点积，这段代码用了其中的三个。切换到3D并使用叉积，在最后插入s和t，结果是3D中直线之间的两个最近点。 不管怎样，2D解:
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;
}
基本上，它将除法延迟到最后一刻，并将大多数测试移动到某些计算完成之前，从而增加了早期退出。最后，它还避免了直线平行时的除零情况。
您可能还想考虑使用ε检验，而不是与零比较。非常接近平行的线会产生稍微偏离的结果。这不是一个bug，这是浮点数学的一个限制。
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};
}
许多函数和结构都是私有的，但是你应该很容易就能知道发生了什么。 这是公开的在这个回购https://github.com/hfossli/AGGeometryKit/
问题C:如何检测两条线段是否相交?
我也搜索过同样的话题，但我对答案并不满意。所以我写了一篇文章，非常详细地解释了如何检查两条线段是否与大量图像相交。这是完整的(并经过测试的)java代码。
以下是这篇文章，截取了最重要的部分:
检查线段a是否与线段b相交的算法如下所示:
什么是边界框?下面是两个线段的边界框:
如果两个边界框都有交点，则移动线段a，使其中一点在(0|0)处。现在你有了一条经过a定义的原点的直线，现在以同样的方式移动线段b，检查线段b的新点是否在直线a的不同两侧。如果是这样，则反过来检查。如果也是这样，线段相交。如果不相交，它们就不相交。
问题A:两条线段在哪里相交?
你知道两条线段a和b相交。如果你不知道，用我在C题中给你的工具检查一下。
现在你可以通过一些情况，并得到解决与七年级数学(见代码和交互示例)。
问题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相同的逻辑。
我尝试了很多方法，然后我决定自己写。就是这样:
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;
}
根据这两个公式:(由直线方程和其他公式简化而来)
iMalc回答的Python版本:
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
上面有很多解决方案，但我认为下面的解决方案很简单，很容易理解。
矢量AB和矢量CD相交当且仅当
端点a和b在线段CD的两边。 端点c和d在线段AB的对边。
更具体地说，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 第二页
这是基于Gareth Ree的回答。它还返回线段重叠的情况。用c++编写的V是一个简单的向量类。其中二维中两个向量的外积返回一个标量。通过了学校自动测试系统的测试。
//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;
}
这个解决方案可能会有所帮助
public static float GetLineYIntesept(PointF p, float slope)
{
return p.Y - slope * p.X;
}
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);
}
我认为这个问题有一个更简单的解决方案。今天我想到了另一个想法，看起来效果不错(至少在2D中)。你所要做的就是计算两条直线的交点，然后检查计算的交点是否在两条线段的边界框内。如果是，两条线段相交。就是这样。
编辑:
这就是我如何计算交集(我不知道我在哪里找到了这个代码片段)
Point3D
来自
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);
}
这是我的BoundingBox类(为了回答的目的而简化):
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));
}
}
根据t3chb0t的答案:
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);
}
一个c++程序，用于检查两条给定线段是否相交
#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 (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
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 = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
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;
}
我将Kris的答案移植到JavaScript。在尝试了许多不同的答案后，他给出了正确的观点。我以为我要疯了，因为我没有得到我需要的分数。
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;
}
我从《多视图几何》这本书里读到了这些算法
以下文本使用
'作为转置符号
*作为点积
当用作算子时，X作为叉乘
1. 线的定义
点x_vec = (x, y)'在直线ax + by + c = 0上
标记L = (a, b, c)'，点为(x, y, 1)'为齐次坐标
直线方程可以写成
(x, y, 1)(a, b, c)' = 0或x' * L = 0
2. 直线交点
我们有两条直线L1=(a1, b1, c1)'， L2=(a2, b2, c2)'
假设x是一个点，一个向量，x = L1 x L2 (L1叉乘L2)。
注意，x始终是一个二维点，如果你对(L1xL2)是一个三元素向量，x是一个二维坐标感到困惑，请阅读齐次坐标。
根据三重积，我们知道
L1 * (L1 x L2) = 0, L2 * (L1 x L2) = 0，因为L1,L2共平面
我们用向量x代替L1*x，那么L1*x=0, L2*x=0，这意味着x在L1和L2上，x是交点。
注意，这里x是齐次坐标，如果x的最后一个元素是零，这意味着L1和L2是平行的。
人们似乎对Gavin的答案很感兴趣，cortijon在评论中提出了一个javascript版本，iMalc提供了一个计算量略少的版本。一些人指出了各种代码建议的缺点，另一些人则评论了一些代码建议的效率。
iMalc通过Gavin的答案提供的算法是我目前在一个javascript项目中使用的算法，我只是想在这里提供一个清理过的版本，如果它可以帮助到任何人的话。
// 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;
}
}
}
};
基于@Gareth Rees的回答，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 r x s = 0 and (q - p) x r = 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
许多答案把所有的计算都打包成一个函数。如果您需要计算直线斜率、y轴截距或x轴截距，以便在代码的其他地方使用，那么这些计算将是冗余的。我分离出了各自的函数，使用了明显的变量名，并注释了我的代码以使其更易于理解。我需要知道直线是否无限超出它们的端点，所以在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
};
}
下面是一个基本的c#线段实现，并有相应的交点检测代码。它需要一个名为Vector2f的2D向量/点结构，不过你可以用任何其他具有X/Y属性的类型替换它。如果更适合你的需要，你也可以用double替换float。
这段代码用于我的. net物理库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 a.X * b.Y - a.Y * b.X;
}
}
找到两条线段的正确交点是一项具有大量边缘情况的非简单任务。下面是一个用Java编写的、有效的、经过测试的解决方案。
本质上，在求两条线段的交点时，有三种情况会发生:
线段不相交 有一个唯一的交点 交点是另一段
注意:在代码中，我假设x1 = x2和y1 = y2的线段(x1, y1)， (x2, y2)是有效的线段。从数学上讲，线段由不同的点组成，但为了完整起见，我在这个实现中允许线段作为点。
代码是从我的github回购
/**
* This snippet finds the intersection of two line segments.
* The intersection may either be empty, a single point or the
* intersection is a subsegment there's an overlap.
*/
import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;
import java.util.ArrayList;
import java.util.List;
public class LineSegmentLineSegmentIntersection {
// Small epsilon used for double value comparison.
private static final double EPS = 1e-5;
// 2D Point class.
public static class Pt {
double x, y;
public Pt(double x, double y) {
this.x = x;
this.y = y;
}
public boolean equals(Pt pt) {
return abs(x - pt.x) < EPS && abs(y - pt.y) < EPS;
}
}
// Finds the orientation of point 'c' relative to the line segment (a, b)
// Returns 0 if all three points are collinear.
// Returns -1 if 'c' is clockwise to segment (a, b), i.e right of line formed by the segment.
// Returns +1 if 'c' is counter clockwise to segment (a, b), i.e left of line
// formed by the segment.
public static int orientation(Pt a, Pt b, Pt c) {
double value = (b.y - a.y) * (c.x - b.x) -
(b.x - a.x) * (c.y - b.y);
if (abs(value) < EPS) return 0;
return (value > 0) ? -1 : +1;
}
// Tests whether point 'c' is on the line segment (a, b).
// Ensure first that point c is collinear to segment (a, b) and
// then check whether c is within the rectangle formed by (a, b)
public static boolean pointOnLine(Pt a, Pt b, Pt c) {
return orientation(a, b, c) == 0 &&
min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) &&
min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
// Determines whether two segments intersect.
public static boolean segmentsIntersect(Pt p1, Pt p2, Pt p3, Pt p4) {
// Get the orientation of points p3 and p4 in relation
// to the line segment (p1, p2)
int o1 = orientation(p1, p2, p3);
int o2 = orientation(p1, p2, p4);
int o3 = orientation(p3, p4, p1);
int o4 = orientation(p3, p4, p2);
// If the points p1, p2 are on opposite sides of the infinite
// line formed by (p3, p4) and conversly p3, p4 are on opposite
// sides of the infinite line formed by (p1, p2) then there is
// an intersection.
if (o1 != o2 && o3 != o4) return true;
// Collinear special cases (perhaps these if checks can be simplified?)
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;
}
public static List<Pt> getCommonEndpoints(Pt p1, Pt p2, Pt p3, Pt p4) {
List<Pt> points = new ArrayList<>();
if (p1.equals(p3)) {
points.add(p1);
if (p2.equals(p4)) points.add(p2);
} else if (p1.equals(p4)) {
points.add(p1);
if (p2.equals(p3)) points.add(p2);
} else if (p2.equals(p3)) {
points.add(p2);
if (p1.equals(p4)) points.add(p1);
} else if (p2.equals(p4)) {
points.add(p2);
if (p1.equals(p3)) points.add(p1);
}
return points;
}
// Finds the intersection point(s) of two line segments. Unlike regular line
// segments, segments which are points (x1 = x2 and y1 = y2) are allowed.
public static Pt[] lineSegmentLineSegmentIntersection(Pt p1, Pt p2, Pt p3, Pt p4) {
// No intersection.
if (!segmentsIntersect(p1, p2, p3, p4)) return new Pt[]{};
// Both segments are a single point.
if (p1.equals(p2) && p2.equals(p3) && p3.equals(p4))
return new Pt[]{p1};
List<Pt> endpoints = getCommonEndpoints(p1, p2, p3, p4);
int n = endpoints.size();
// One of the line segments is an intersecting single point.
// NOTE: checking only n == 1 is insufficient to return early
// because the solution might be a sub segment.
boolean singleton = p1.equals(p2) || p3.equals(p4);
if (n == 1 && singleton) return new Pt[]{endpoints.get(0)};
// Segments are equal.
if (n == 2) return new Pt[]{endpoints.get(0), endpoints.get(1)};
boolean collinearSegments = (orientation(p1, p2, p3) == 0) &&
(orientation(p1, p2, p4) == 0);
// The intersection will be a sub-segment of the two
// segments since they overlap each other.
if (collinearSegments) {
// Segment #2 is enclosed in segment #1
if (pointOnLine(p1, p2, p3) && pointOnLine(p1, p2, p4))
return new Pt[]{p3, p4};
// Segment #1 is enclosed in segment #2
if (pointOnLine(p3, p4, p1) && pointOnLine(p3, p4, p2))
return new Pt[]{p1, p2};
// The subsegment is part of segment #1 and part of segment #2.
// Find the middle points which correspond to this segment.
Pt midPoint1 = pointOnLine(p1, p2, p3) ? p3 : p4;
Pt midPoint2 = pointOnLine(p3, p4, p1) ? p1 : p2;
// There is actually only one middle point!
if (midPoint1.equals(midPoint2)) return new Pt[]{midPoint1};
return new Pt[]{midPoint1, midPoint2};
}
/* Beyond this point there is a unique intersection point. */
// Segment #1 is a vertical line.
if (abs(p1.x - p2.x) < EPS) {
double m = (p4.y - p3.y) / (p4.x - p3.x);
double b = p3.y - m * p3.x;
return new Pt[]{new Pt(p1.x, m * p1.x + b)};
}
// Segment #2 is a vertical line.
if (abs(p3.x - p4.x) < EPS) {
double m = (p2.y - p1.y) / (p2.x - p1.x);
double b = p1.y - m * p1.x;
return new Pt[]{new Pt(p3.x, m * p3.x + b)};
}
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;
double x = (b2 - b1) / (m1 - m2);
double y = (m1 * b2 - m2 * b1) / (m1 - m2);
return new Pt[]{new Pt(x, y)};
}
}
下面是一个简单的用法示例:
public static void main(String[] args) {
// Segment #1 is (p1, p2), segment #2 is (p3, p4)
Pt p1, p2, p3, p4;
p1 = new Pt(-2, 4); p2 = new Pt(3, 3);
p3 = new Pt(0, 0); p4 = new Pt(2, 4);
Pt[] points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
Pt point = points[0];
// Prints: (1.636, 3.273)
System.out.printf("(%.3f, %.3f)\n", point.x, point.y);
p1 = new Pt(-10, 0); p2 = new Pt(+10, 0);
p3 = new Pt(-5, 0); p4 = new Pt(+5, 0);
points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
Pt point1 = points[0], point2 = points[1];
// Prints: (-5.000, 0.000) (5.000, 0.000)
System.out.printf("(%.3f, %.3f) (%.3f, %.3f)\n", point1.x, point1.y, point2.x, point2.y);
}
