我如何确定两条直线是否相交,如果相交,在x,y点处?
当前回答
问题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相同的逻辑。
其他回答
一个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;
}
我尝试了很多方法,然后我决定自己写。就是这样:
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;
}
根据这两个公式:(由直线方程和其他公式简化而来)
我从《多视图几何》这本书里读到了这些算法
以下文本使用
'作为转置符号
*作为点积
当用作算子时,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是平行的。
只是想提一下,一个很好的解释和明确的解决方案可以在数字食谱系列中找到。我有这本书的第三版,答案在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;
}
许多答案把所有的计算都打包成一个函数。如果您需要计算直线斜率、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
};
}