我如何确定两条直线是否相交，如果相交，在x,y点处?
当前回答
这是基于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;
}
其他回答
我从《多视图几何》这本书里读到了这些算法
以下文本使用
'作为转置符号
*作为点积
当用作算子时，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是平行的。
我尝试了很多方法，然后我决定自己写。就是这样:
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;
}
根据这两个公式:(由直线方程和其他公式简化而来)
问题可以简化成这样一个问题:从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
找到两条线段的正确交点是一项具有大量边缘情况的非简单任务。下面是一个用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);
}
基于@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
