javascript 计算两条线的交点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13937782/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
calculating the point of intersection of two lines
提问by Adam
I have dynamically generated lines that animate and I want to detect when a lines hits another. I'm trying to implement some basic linear algebra to obtain the equation of the lines and then solving for x,y, but the results are erratic. At this point I'm testing only with two lines which means I should be getting one point of intersection, but I get two. I just want to make sure my math is ok and that I should be looking elsewhere for the problem.
我有动态生成的动画线，我想检测一条线何时碰到另一条线。我正在尝试实现一些基本的线性代数以获得直线方程，然后求解 x,y，但结果不稳定。在这一点上，我只用两条线进行测试，这意味着我应该得到一个交点，但我得到了两个。我只是想确保我的数学没问题，并且我应该在别处寻找问题。
function collision(boid1, boid2) {
var x1 = boid1.initialX, y1 = boid1.initialY, x2 = boid1.x, y2 = boid1.y, x3 = boid2.initialX, y3 = boid2.initialY, x4 = boid2.x, y4 = boid2.y;
slope1 = (y1 - y2)/(x1 - x2);
slope2 = (y3 - y4)/(x3- x4);
//console.log("slope1:"+slope1);
//console.log('x2:'+x2+' y2:'+y2);
if(slope1 != slope2){
var b1 = getB(slope1,x1,y1);
var b2 = getB(slope2,x3,y3);
if(slope2 >= 0){
u = slope1 - slope2;
}else{
u = slope1 + slope2;
}
if(b1 >= 0){
z = b2 - b1;
}else{
z = b2 + b1;
}
pointX = z / u;
pointY = (slope1*pointX)+b1;
pointYOther = (slope2*pointX)+b2;
console.log("pointx:"+pointX+" pointy:"+pointY+" othery:"+pointYOther);
//return true;
context.beginPath();
context.arc(pointX, pointY, 2, 0, 2 * Math.PI, false);
context.fillStyle = 'green';
context.fill();
context.lineWidth = 1;
context.strokeStyle = '#003300';
context.stroke();
}
return false;
}
function getB(slope,x,y){
var y = y, x = x, m = slope;
a = m*x;
if(a>=0){
b = y - a;
}else{
b = y + a;
}
return b;
}
EDIT:
编辑：
The problem is that I'm getting two different values for the point of intersection. There should only be one, which leads me to believe my calculations are wrong. Yes, x2,y2,x4,y4 are all moving, but they have a set angle and the consistent slopes confirm that.
问题是我得到了两个不同的交点值。应该只有一个，这让我相信我的计算是错误的。是的，x2,y2,x4,y4 都在移动，但它们有一个固定的角度，并且一致的斜率证实了这一点。
采纳答案by SReject
You don't need to alternate between adding/subtracting y-intersects when plugging 'found-x' back into one of the equations:
将 'found-x' 插入方程之一时，您无需在添加/减去 y 相交之间交替：
(function () {
window.linear = {
slope: function (x1, y1, x2, y2) {
if (x1 == x2) return false;
return (y1 - y2) / (x1 - x2);
},
yInt: function (x1, y1, x2, y2) {
if (x1 === x2) return y1 === 0 ? 0 : false;
if (y1 === y2) return y1;
return y1 - this.slope(x1, y1, x2, y2) * x1 ;
},
getXInt: function (x1, y1, x2, y2) {
var slope;
if (y1 === y2) return x1 == 0 ? 0 : false;
if (x1 === x2) return x1;
return (-1 * ((slope = this.slope(x1, y1, x2, y2)) * x1 - y1)) / slope;
},
getIntersection: function (x11, y11, x12, y12, x21, y21, x22, y22) {
var slope1, slope2, yint1, yint2, intx, inty;
if (x11 == x21 && y11 == y21) return [x11, y11];
if (x12 == x22 && y12 == y22) return [x12, y22];
slope1 = this.slope(x11, y11, x12, y12);
slope2 = this.slope(x21, y21, x22, y22);
if (slope1 === slope2) return false;
yint1 = this.yInt(x11, y11, x12, y12);
yint2 = this.yInt(x21, y21, x22, y22);
if (yint1 === yint2) return yint1 === false ? false : [0, yint1];
if (slope1 === false) return [y21, slope2 * y21 + yint2];
if (slope2 === false) return [y11, slope1 * y11 + yint1];
intx = (slope1 * x11 + yint1 - yint2)/ slope2;
return [intx, slope1 * intx + yint1];
}
}
}());
回答by vbarbarosh
I found a great solution by Paul Bourke. Here it is, implemented in JavaScript:
我找到了Paul Bourke 的一个很好的解决方案。这是用 JavaScript 实现的：
function line_intersect(x1, y1, x2, y2, x3, y3, x4, y4)
{
var ua, ub, denom = (y4 - y3)*(x2 - x1) - (x4 - x3)*(y2 - y1);
if (denom == 0) {
return null;
}
ua = ((x4 - x3)*(y1 - y3) - (y4 - y3)*(x1 - x3))/denom;
ub = ((x2 - x1)*(y1 - y3) - (y2 - y1)*(x1 - x3))/denom;
return {
x: x1 + ua * (x2 - x1),
y: y1 + ua * (y2 - y1),
seg1: ua >= 0 && ua <= 1,
seg2: ub >= 0 && ub <= 1
};
}
回答by Redu
You may do as follows;
您可以按照以下方式进行；
function lineIntersect(a,b){
a.m = (a[0].y-a[1].y)/(a[0].x-a[1].x); // slope of line 1
b.m = (b[0].y-b[1].y)/(b[0].x-b[1].x); // slope of line 2
return a.m - b.m < Number.EPSILON ? undefined
: { x: (a.m * a[0].x - b.m*b[0].x + b[0].y - a[0].y) / (a.m - b.m),
y: (a.m*b.m*(b[0].x-a[0].x) + b.m*a[0].y - a.m*b[0].y) / (b.m - a.m)};
}
var line1 = [{x:3, y:3},{x:17, y:8}],
line2 = [{x:7, y:10},{x:11, y:2}];
console.log(lineIntersect(line1, line2));回答by David Figatner
For line segment-line segment intersections, use Paul Borke's solution:
对于线段与线段的交点，请使用Paul Borke 的解决方案：
// line intercept math by Paul Bourke http://paulbourke.net/geometry/pointlineplane/
// Determine the intersection point of two line segments
// Return FALSE if the lines don't intersect
function intersect(x1, y1, x2, y2, x3, y3, x4, y4) {
// Check if none of the lines are of length 0
if ((x1 === x2 && y1 === y2) || (x3 === x4 && y3 === y4)) {
return false
}
denominator = ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1))
// Lines are parallel
if (denominator === 0) {
return false
}
let ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator
let ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator
// is the intersection along the segments
if (ua < 0 || ua > 1 || ub < 0 || ub > 1) {
return false
}
// Return a object with the x and y coordinates of the intersection
let x = x1 + ua * (x2 - x1)
let y = y1 + ua * (y2 - y1)
return {x, y}
}
For infinite line intersections, use Justin C. Round's algorithm:
对于无限线交点，请使用Justin C. Round 算法：
function checkLineIntersection(line1StartX, line1StartY, line1EndX, line1EndY, line2StartX, line2StartY, line2EndX, line2EndY) {
// if the lines intersect, the result contains the x and y of the intersection (treating the lines as infinite) and booleans for whether line segment 1 or line segment 2 contain the point
var denominator, a, b, numerator1, numerator2, result = {
x: null,
y: null,
onLine1: false,
onLine2: false
};
denominator = ((line2EndY - line2StartY) * (line1EndX - line1StartX)) - ((line2EndX - line2StartX) * (line1EndY - line1StartY));
if (denominator == 0) {
return result;
}
a = line1StartY - line2StartY;
b = line1StartX - line2StartX;
numerator1 = ((line2EndX - line2StartX) * a) - ((line2EndY - line2StartY) * b);
numerator2 = ((line1EndX - line1StartX) * a) - ((line1EndY - line1StartY) * b);
a = numerator1 / denominator;
b = numerator2 / denominator;
// if we cast these lines infinitely in both directions, they intersect here:
result.x = line1StartX + (a * (line1EndX - line1StartX));
result.y = line1StartY + (a * (line1EndY - line1StartY));
// if line1 is a segment and line2 is infinite, they intersect if:
if (a > 0 && a < 1) {
result.onLine1 = true;
}
// if line2 is a segment and line1 is infinite, they intersect if:
if (b > 0 && b < 1) {
result.onLine2 = true;
}
// if line1 and line2 are segments, they intersect if both of the above are true
return result;
};
回答by rzymek
There is an npm module that does just that: line-intersect.
有一个 npm 模块可以做到这一点：line-intersect。
Install it using
安装它使用
npm install --save line-intersect
ES6 usage:
ES6 用法：
import { checkIntersection } from "line-intersect";
const result = lineIntersect.checkIntersection(
line1.start.x, line1.start.y, line1.end.x, line1.end.y,
line2.start.x, line2.start.y, line2.end.x, line2.end.y
);
result.type // any of "none", "parallel", "colinear", "intersecting"
result.point // only exists when result.type == 'intersecting'
If you're using typescript, here are the typings:
如果您使用打字稿，这里是打字：
declare module "line-intersect" {
export function checkIntersection(
x1: number, y1: number,
x2: number, y2: number,
x3: number, y3: number,
x4: number, y4: number): {
type: string,
point: {x:number, y:number}
};
}
Put it in a file and reference if in tsconfig.json's "files"section.
把它放在一个文件中，如果在tsconfig.json's"files"部分，请参考。
