Реализация пересечения сегментов

Question

Реализация пересечения сегментов

Я пытался реализовать алгоритм пересечения сегментов на основе вектора, описанный здесь (самый популярный ответ) в 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 который перейдем ко второму случаю, где предполагается параллельность, даже если сегменты не являются таковыми.

P.S. Есть ли способ сделать этот код более читаемым?

2 2

algorithm collision geometry

2 ответа:

Кроме того, вот порт точки пересечения поля Бурка двух линейных сегментов в 2-х измерениях алгоритма, использующего версию 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 полезными, и это функциональность 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>

1

Bobas_Pett · Accepted Answer · 2016-09-19 22:34:21

Есть ссылка на 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; 
Если вам нужен грубый способ "выведения" приведенных выше уравнений для 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 сверху, чтобы получить уравнение, приведенное в ссылке:

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