Do the lines intersect or not?

djevazi

The little sketch shows two random lines, my question is how to check do the lines intersect or not?

float x1;
float y1;
float x2;
float y2;

float x3;
float y3;
float x4;
float y4;


void setup()
{
  size(800,800);

  x1 = random(100,width-100);
  y1 = random(100,height-100);
  x2 = random(100,width-100);
  y2 = random(100,height-100);

  x3 = random(100,width-100);
  y3 = random(100,height-100);
  x4 = random(100,width-100);
  y4 = random(100,height-100);
}


void draw()
{
  stroke(155,0,0);
  line(x1,y1,x2,y2);

  stroke(0,0,155);
  line(x3,y3,x4,y4);
}

jeremydouglass

@djevazi --

Use line-line collision detection:

• http://www.jeffreythompson.org/collision-detection/line-line.php

  // LINE/LINE
  boolean lineLine(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
    // calculate the distance to intersection point
    float uA = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
    float uB = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
    // if uA and uB are between 0-1, lines are colliding
    if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {
      return true;
    }
    return false;
  }
  

prince_polka

Also checking whether all points are on different sides of the other line works

boolean lineline(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
  boolean a, b, c, d;
  float x, y, z, w;
  x = x1-x2;
  y = y2-y1;
  z = x3-x1;
  w = y3-y1;
  a = x*w+y*z>=0;
  z = x4-x1;
  w = y4-y1;
  b = x*w+y*z>=0;
  if (a==b)return false;
  x = x3-x4;
  y = y4-y3;
  c = x*-w+y*-z>=0;
  z = x2-x3;
  w = y2-y3;
  d = x*w+y*z>=0;
  return c!=d;
}

djevazi

@jeremydouglass , thanks, I almost forgot that you sent me that article about collisions few month ago : )

djevazi

@prince_polka, thank you.