我试图在Java中实现这里描述的基于向量的分段相交算法(最受欢迎的答案)，但由于它通常与实现你不完全理解的算法有关，我一直失败。如果有人能校对我的代码，告诉我我做错了什么，我将非常感激。
boolean intersect(PVector p, PVector r, PVector q, PVector s){
// r x s
double rxs = r.x*s.y + r.y*s.x;
//(q-p) x r
double qpxr = (q.x-p.x)*r.y + (q.y-p.y)*r.x;
PVector qp = q.sub(p).copy(); //q - p
//case one lines parallel might intersect:
if(rxs==0 && qpxr==0){
println("case one: collinear might intersect");
double t0 = qp.dot(r);
double t1 = qp.dot(r)/r.dot(r)+(s.dot(r)/r.dot(r));
return max((float)t0 , 0.f) <= min((float)t1, 1.f);//if ranges intersect the segments intersect
}else if(rxs==0 && qpxr!=0){
println("case two: parallel no intersect");
return false;
}else if(rxs!=0){
println("case three");
double u = qpxr/rxs;
double t = (qp.x*r.y + qp.y*r.x)/rxs;
if((u>=0 && u<=1) && (t<=1 && t>=0)){
PVector intersect = p.copy();
intersect.add(r.copy().mult((float)t));
point(intersect.x, intersect.y);
return true;
}else{
println("no intersect");
print(u);
print(" ");
println(t);
}
}else{
println("case four no intersect");
return false;
}
return false;
}
我也试着用手做一些答案，但似乎仍然失败，所以现在我有点迷路了。例如:
p=(0;0), r=(10;10)
q=(10;0), s=(-10;10)
然后是r x s = 10*10 + (-10*10) = 0，它将传递到假设平行的第二种情况，即使片段不是。
注:是否有一种方法，使这段代码更可读?
有一个关于topcoder的参考，描述了如何得到2段相交的地方。如果你只是想知道这些线是否相交，你检查A1*B2 - A2*B1 == 0是否给定:
A1 = y2-y1B1 = x1-x2
A2 = y4-y3B2 = x3-x4
最基本的直觉就是既然你有关于线段交点的方程
x = (C1*B2 - B1*C2)/(A1*B2 - A2*B1)
y = (A1*C2 - A2*C1)/(A1*B2 - A2*B1)
你不能除以0
如果包含线段的线确实相交于线段范围之外的某处你检查像
这样的内容boolean inRange(double x1,double y1,double x2,double y2,double x3,double y3){
double dx = Math.abs(x3-x2);
double dy = Math.abs(y3-y2);
if (Math.abs(x3-x1)+Math.abs(x2-x1)==dx &&
Math.abs(y3-y1)+Math.abs(y2-y1)==dy){
return true;
}
return false;
}
所以条件应该看起来像
if (!inRange(...) || (A1*B2 - A2*B1 == 0)) return false;
如果你想要一个粗略的方法来"推导"x和y的上述方程，你可以从两个线段的方程开始求解系统。
A1*x + B1*y = C1A2*x + B2*y = C2
解左边的x
x = (C1
-B1*y)/A1
插入右边，求解y
A2*((C1
-B1*y)/A1) + B2*y = C2
y*(B2-(A2*B1/A1)) = C2 - (A2*C1/A1)
使等式看起来像
y = (A1*C2 - A2*C1)/(A1*B2-A2*B1)
分数的上下乘以A1
然后将y代入x (" x = (C1
-B1*y)/A1 ")的上述方程
x = (C1/A1) - (B1*A1*C2-B1*A2*C1)/A1*(A1*B2 - A2*B1)
x = ((C1*A1*B2 - B1*A2*C1)-(B1*A1*C2 - B1*A2*C1))/A1*(A1*B2 - A2*B1)
x = (C1*A1*B2 - B1*A1*C2)/A1*(A1*B2 - A2*B1)
将A1从上相除，得到链接:
x = (C1*B2 - B1*C2)/(A1*B2 - A2*B1)
另外，这里是Paul Bourke的二维两线段交点算法的一个移植，使用Olaf Rabbachin的c#版本:
Line l1 = new Line(new PVector(10,10),new PVector(390,390));
Line l2 = new Line(new PVector(10,390),new PVector(390,10));
void setup(){
size(400,400);
fill(0);
}
void draw(){
//draw background and lines
background(255);
l1.draw();
l2.draw();
text("click and drag",10,15);
//check intersections (and draw)
PVector intersection = doLinesIntersect(l1,l2);
if(intersection != null){
ellipse(intersection.x,intersection.y,15,15);
}
}
void mouseDragged(){
l1.p1.x = mouseX;
l1.p1.y = mouseY;
}
class Line{
PVector p1 = new PVector();
PVector p2 = new PVector();
Line(PVector start,PVector end){
p1 = start;
p2 = end;
}
void draw(){
line(p1.x,p1.y,p2.x,p2.y);
}
}
//port of http://paulbourke.net/geometry/pointlineplane/Helpers.cs
PVector doLinesIntersect(Line l1, Line l2){
// Denominator for ua and ub are the same, so store this calculation
float d =
(l2.p2.y - l2.p1.y) * (l1.p2.x - l1.p1.x)
-
(l2.p2.x - l2.p1.x) * (l1.p2.y - l1.p1.y);
//n_a and n_b are calculated as seperate values for readability
float n_a =
(l2.p2.x - l2.p1.x) * (l1.p1.y - l2.p1.y)
-
(l2.p2.y - l2.p1.y) * (l1.p1.x - l2.p1.x);
float n_b =
(l1.p2.x - l1.p1.x) * (l1.p1.y - l2.p1.y)
-
(l1.p2.y - l1.p1.y) * (l1.p1.x - l2.p1.x);
// Make sure there is not a division by zero - this also indicates that
// the lines are parallel.
// If n_a and n_b were both equal to zero the lines would be on top of each
// other (coincidental). This check is not done because it is not
// necessary for this implementation (the parallel check accounts for this).
if (d == 0)
return null;
// Calculate the intermediate fractional point that the lines potentially intersect.
float ua = n_a / d;
float ub = n_b / d;
// The fractional point will be between 0 and 1 inclusive if the lines
// intersect. If the fractional calculation is larger than 1 or smaller
// than 0 the lines would need to be longer to intersect.
if (ua >= 0d && ua <= 1d && ub >= 0d && ub <= 1d)
{
PVector intersection = new PVector();
intersection.x = l1.p1.x + (ua * (l1.p2.x - l1.p1.x));
intersection.y = l1.p1.y + (ua * (l1.p2.y - l1.p1.y));
return intersection;
}
return null;
}
另外，你可能会发现毒物库很有用，它的intersectLine Line2D功能。注意处理3有一些问题
你可以在下面运行一个演示:
var l1,l2;
function setup() {
createCanvas(400,400);
fill(0);
l1 = new Line();
l2 = new Line();
l1.p1.x = l1.p1.y = 10;
l1.p2.x = l1.p2.y = 390;
l2.p1.x = 10;
l2.p1.y = 390;
l2.p2.x = 390;
l2.p2.y = 10;
}
function draw() {
//draw background and lines
background(255);
l1.draw();
l2.draw();
text("click and drag",10,15);
//check intersections (and draw)
var intersection = doLinesIntersect(l1,l2);
if(intersection != null){
ellipse(intersection.x,intersection.y,15,15);
}
}
function mouseDragged(){
l1.p1.x = mouseX || touchX;
l1.p1.y = mouseY || touchY;
}
//port of http://paulbourke.net/geometry/pointlineplane/Helpers.cs
function doLinesIntersect(l1, l2){
// Denominator for ua and ub are the same, so store this calculation
var d =
(l2.p2.y - l2.p1.y) * (l1.p2.x - l1.p1.x)
-
(l2.p2.x - l2.p1.x) * (l1.p2.y - l1.p1.y);
//n_a and n_b are calculated as seperate values for readability
var n_a =
(l2.p2.x - l2.p1.x) * (l1.p1.y - l2.p1.y)
-
(l2.p2.y - l2.p1.y) * (l1.p1.x - l2.p1.x);
var n_b =
(l1.p2.x - l1.p1.x) * (l1.p1.y - l2.p1.y)
-
(l1.p2.y - l1.p1.y) * (l1.p1.x - l2.p1.x);
// Make sure there is not a division by zero - this also indicates that
// the lines are parallel.
// If n_a and n_b were both equal to zero the lines would be on top of each
// other (coincidental). This check is not done because it is not
// necessary for this implementation (the parallel check accounts for this).
if (d == 0)
return null;
// Calculate the intermediate fractional point that the lines potentially intersect.
var ua = n_a / d;
var ub = n_b / d;
// The fractional point will be between 0 and 1 inclusive if the lines
// intersect. If the fractional calculation is larger than 1 or smaller
// than 0 the lines would need to be longer to intersect.
if (ua >= 0.0 && ua <= 1.0 && ub >= 0.0 && ub <= 1.0)
{
var intersection = createVector();
intersection.x = l1.p1.x + (ua * (l1.p2.x - l1.p1.x));
intersection.y = l1.p1.y + (ua * (l1.p2.y - l1.p1.y));
return intersection;
}
return null;
}
function Line(){
this.p1 = createVector();
this.p2 = createVector();
this.draw = function(){
line(this.p1.x,this.p1.y,this.p2.x,this.p2.y);
}
}<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.5.3/p5.min.js"></script>