我如何确定两条直线是否相交，如果相交，在x,y点处?
当前回答
我从《多视图几何》这本书里读到了这些算法
以下文本使用
'作为转置符号
*作为点积
当用作算子时，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是平行的。
其他回答
我从《多视图几何》这本书里读到了这些算法
以下文本使用
'作为转置符号
*作为点积
当用作算子时，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是平行的。
我认为这个问题有一个更简单的解决方案。今天我想到了另一个想法，看起来效果不错(至少在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));
}
}
基于@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
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
这让我困惑了好几个小时。：(
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/
