我如何确定两条直线是否相交，如果相交，在x,y点处?
当前回答
我尝试了很多方法，然后我决定自己写。就是这样:
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;
}
根据这两个公式:(由直线方程和其他公式简化而来)
其他回答
上面有很多解决方案，但我认为下面的解决方案很简单，很容易理解。
矢量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 第二页
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
这让我困惑了好几个小时。：(
根据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);
}
人们似乎对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;
}
}
}
};
找到两条线段的正确交点是一项具有大量边缘情况的非简单任务。下面是一个用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);
}
