段交集实现

Question

我正在尝试实现 Java 中描述的基于矢量的线段交集算法 here（投票最多的答案），但由于它通常与实现算法一起使用，您并不完全理解，我一直失败。如果有人可以校对我的代码并告诉我我做错了什么，我将不胜感激。

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 将传递到假定并行的第二种情况，即使段不是。

P.S。有没有办法让这段代码更具可读性？

Answer 1

topcoder 上有一个参考描述了如何找到 2 个线段相交的位置。如果您只是想知道这些线是否相交，请检查是否给定 A1*B2 - A2*B1 == 0：

A1 = y2-y1 B1 = x1-x2

A2 = y4-y3 B2 = 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;

如果您想要 "deriving" 上述 x 和 y 方程的粗略方法，您可以从 2 条线段的方程开始求解系统。

A1*x + B1*y = C1 A2*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 得到 link 中给出的等式：

x = (C1*B2 - B1*C2)/(A1*B2 - A2*B1)

Answer 2

此外，这里是 Paul Bourke's Intersection point of two line segments in 2 dimensions 算法的端口，使用 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;  
}

此外，您可能会发现 toxiclibs useful and it's intersectLine Line2D functionality。请注意处理 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>

段交集实现

Segment intersection implementation

algorithm

geometry

processing

collision

segments