point and line intersection detection

lukasz

sorry, posted this earlier this week but forum got moved and I cannot access old post. I am trying to basically detect if a line intersects a point and how I could do this with simple math. there is a lot of line to line and line to circle detection but i am not seeing simple line and point.

GoToLoop

Old forum snapshot is forum.processing.org/one/
Although it's about 5 days older than the actual closing time! :-@

PhiLho

Technically, you don't "intersect" a line and a point, you see if a point is on a line...

It depends how you define your line.

You have to get the y = a * x + b equation for your line, and see if the coordinates of your point follow this equality. Can be as simple as that...

If the line is defined by two points, the a and b parameters can be computed from them: that's a simple dual equation solving (I know the French term, not how it is named in English).

Mushussu

PVector p1;
PVector p2;
float a;
float b;

void setup() {
  size(400, 400);
  p1 = new PVector(random(200), random(200));
  p2 = new PVector(random(200, 400), random(0, 400));
  PVector sub = PVector.sub(p2, p1);
  // y = a * x + b
  a = sub.y / sub.x;
  b = p1.y - a * p1.x;
  cursor(CROSS);
}

void draw() {
  background(255);
  line(p1.x, p1.y, p2.x, p2.y);
  fill(255);
  ellipse(p1.x, p1.y, 10, 10);
  if ((mouseY > (a * mouseX + b - 0.5)) && (mouseY < (a * mouseX + b + 0.5))) {
    fill(255, 0, 0);
    ellipse(mouseX, mouseY, 20, 20);
  }
}

Mushussu

For lines intersection :

PVector p1;
PVector p2;
PVector p3;
float a;
float b;

void setup() {
  size(400, 400);
  p1 = new PVector(random(200), random(200));
  p2 = new PVector(random(200, 400), random(0, 400));
  p3 = new PVector(random(400), random(400));
  PVector sub = PVector.sub(p2, p1);
  // y = a * x + b
  a = sub.y / sub.x;
  b = p1.y - a * p1.x;
  cursor(CROSS);
}

void draw() {
  background(255);
  PVector mouse = new PVector(mouseX, mouseY);
  line(p1.x, p1.y, p2.x, p2.y);
  line(p3.x, p3.y, mouse.x, mouse.y);
  fill(255);
  ellipse(p1.x, p1.y, 10, 10);
  ellipse(p3.x, p3.y, 10, 10);
  PVector sub1 = PVector.sub(mouse, p3);
  float a1 = sub1.y / sub1.x;
  float b1 = p3.y - a1 * p3.x;

  float x = (b1 - b) / (a - a1);
  float y = a * x + b;

  if ((x > min(p1.x, p2.x)) && (x < max(p1.x, p2.x)) && (y > min(p1.y, p2.y)) && (y < max(p1.y, p2.y))
    && (x > min(p3.x, mouse.x)) && (x < max(p3.x, mouse.x)) && (y > min(p3.y, mouse.y)) && (y < max(p3.y, mouse.y))) {
    fill(255, 0, 0);
    ellipse(x, y, 20, 20);
  }
}

quark

@Mushussu I have deleted your first post because it is redundant because you fixed the code formatting in the next post.

As PhiLho pointed out lines don't intersect with points rather you must calculate how close the point is to the line and decide if that is close enough.

The code below demonstrates what I mean and has a neat method for deciding whether a point is close enough to the line. Since this might be true even if the point is not quite on the line the method also calculates you the nearest point on the line.

You can see the sketch in action here

  /**
  Determines whether a point'c' is close to a line from
  'a' to 'b' <br>
  If the point is close enough then the point haloe will be green else it is red. <br>
  It works by calculating the point nearest point (pj)  on the line to the point 'c'.
  It then determoines whether 'pj' is inside the line segment a-->b and that the dist
  c<>pj is less than a closeness value.
  */

  PVector a, b, c, pj;
  float closeness = 1;

  public void setup() {
    size(400, 400);
    // cursor(cross);
    a = new PVector(121, 87);
    b = new PVector(299, 322);
    c = new PVector(160, 410);
    pj = new PVector();
  }

  public void draw() {
    background(255);
    // Offset the cursor so we can see what is happening
    c. set(mouseX - 20, mouseY - 20);
    // Is c on the line a --> b
    // pj is the nearest point on the line
    boolean ol = isOnLine(a, b, c, pj);

    noFill();
    stroke(160);
    strokeWeight(1.1);
    line(a.x, a.y, pj.x, pj.y);
    line(c.x, c.y, pj.x, pj.y);
    stroke(0);
    strokeWeight(1.5);
    line(a.x, a.y, b.x, b.y);
    noStroke();
    ellipse(a.x, a.y, 4, 4);
    ellipse(b.x, b.y, 4, 4);
    // Point halo
    if (ol)
      fill(0, 255, 0, 64);
    else
      fill(255, 0, 0, 64);
    ellipse(c.x, c.y, 20, 20);
    // Point
    fill(0);
    ellipse(c.x, c.y, 4, 4);
  }

  boolean isOnLine(PVector v0, PVector v1, PVector p, PVector vp) {
    // Return minimum distance between line segment vw and point p
    PVector line = PVector.sub(v1, v0);
    float l2 = line.magSq();  // i.e. |w-v|^2 -  avoid a sqrt
    if (l2 == 0.0) {
      vp.set(v0);
      return false;
    }
    PVector pv0_line = PVector.sub(p, v0);
    float t = pv0_line.dot(line)/l2;
    pv0_line.normalize();
    vp.set(line);
    vp.mult(t);
    vp.add(v0);
    float d = PVector.dist(p, vp);
    if (t >= 0 && t <= 1 && d <= closeness)
      return true;
    else
      return false;
  }

Mushussu

Line vs circle :

PVector p;
float x0, y0, radius;

void setup() {
  size(400, 400);
  x0 = random(100, 300);
  y0 = random(100, 300);
  radius = random(50, 100);
  p = new PVector(random(400), random(400));
  cursor(CROSS);
}

void draw() {
  background(255);
  fill(255);

  PVector mouse = new PVector(mouseX, mouseY);
  ellipse(x0, y0, 2 * radius, 2 * radius);
  line(p.x, p.y, mouse.x, mouse.y);
  ellipse(p.x, p.y, 10, 10);
  PVector sub = PVector.sub(mouse, p);
  // y = a * x + b
  float a = sub.y / sub.x;
  float b = p.y - a * p.x;
  // (x - x0)^2 + (y - y0)^2 = radius ^2
  // y = a * x + b
  float A = (1 + a * a);
  float B = (2 * a *( b - y0) - 2 * x0);
  float C = (x0 * x0 + (b - y0) * (b - y0)) - (radius * radius);
  float delta = B * B - 4 * A * C;
  //println(delta);
  if (delta >= 0) {
    fill(255, 0, 0);
    float x1 = (-B - sqrt(delta)) / (2 * A);
    float y1 = a * x1 + b;
    if ((x1 > min(p.x, mouse.x)) && (x1 < max(p.x, mouse.x)) && (y1 > min(p.y, mouse.y)) && (y1 < max(p.y, mouse.y))) {
      ellipse(x1, y1, 20, 20);
    }
    float x2 = (-B + sqrt(delta)) / (2 * A);
    float y2 = a * x2 + b;
    if ((x2 > min(p.x, mouse.x)) && (x2 < max(p.x, mouse.x)) && (y2 > min(p.y, mouse.y)) && (y2 < max(p.y, mouse.y))) {
      ellipse(x2, y2, 20, 20);
    }
  }
}

GoToLoop

I've got an old online "circle - line intersection" example too:
http://studio.processingtogether.com/sp/pad/export/ro.9gGiJpQZIcTte/latest

/**
 * Line vs Circle Intersection (v2.01)
 * by KarlHungus (2013/Apr)
 *
 * forum.processing.org/one/topic/if-touched-send-once
 * studio.processingtogether.com/sp/pad/export/ro.9gGiJpQZIcTte/latest
 */

int circleX, circleY, circleR;
int lineX, lineY;

boolean isIntersecting;

final static String GFX = JAVA2D; // Use JAVA2D or P2D

void setup() {
  size(600, 400, GFX);
  noLoop();  // turn off draw()!;
  smooth();
  ellipseMode(RADIUS);
  strokeWeight(2);

  circleX = width  >> 1;
  circleY = height >> 1;
  circleR = height >> 2;

  lineX = width  - width/8;
  lineY = height - height/8;

  mouseX = mouseY = lineX;
}

void mouseMoved() {
  redraw();  // 1 round of draw()!
}

void draw() {
  background(0300);

  if ( checkIntersection(lineX, lineY, mouseX, mouseY, 
  circleX, circleY, circleR) ) {
    if (!isIntersecting)   println("Sending OSC...");
    isIntersecting = true;
  }

  else {
    if (isIntersecting)    println("Stopped intersecting!");
    isIntersecting = false;
  }

  noStroke();
  fill(isIntersecting? 0 : -1);
  ellipse(circleX, circleY, circleR, circleR);

  stroke(#00FF00);
  line(lineX, lineY, mouseX, mouseY);
}

// Code adapted from Paul Bourke:
// local.wasp.uwa.edu.au/~pbourke/geometry/sphereline/raysphere.c

boolean checkIntersection(float x1, float y1, float x2, float y2, 
float cx, float cy, float cr ) {
  float dx = x2 - x1;
  float dy = y2 - y1;

  float a = dx*dx + dy*dy;
  float b = (dx*(x1 - cx) + (y1 - cy)*dy) * 2;
  float c = cx*cx + cy*cy;

  c += x1*x1 + y1*y1;
  c -= (cx*x1 + cy*y1) * 2;
  c -= cr*cr;

  float delta = b*b - 4*a*c;

  if (delta < 0)   return false; // Not intersecting

  delta = sqrt(delta);

  float mu = (-b + delta) / (2*a);
  float ix1 = x1 + mu*dx;
  float iy1 = y1 + mu*dy;

  mu = (b + delta) / (-2*a);
  float ix2 = x1 + mu*dx;
  float iy2 = y1 + mu*dy;

  // Intersection points
  fill(#FF0000);
  ellipse(ix1, iy1, 5, 5);
  ellipse(ix2, iy2, 5, 5);

  // Figure out which point is closer to the circle
  boolean test = dist(x1, y1, cx, cy) < dist(x2, y2, cx, cy);

  float closerX = test? x2:x1;
  float closerY = test? y2:y1;

  return dist(closerX, closerY, ix1, iy1) < dist(x1, y1, x2, y2) || 
    dist(closerX, closerY, ix2, iy2) < dist(x1, y1, x2, y2);
}

lukasz

thanks guys this is awesome! code works well, but are there any places I can read up on the theory behind it? I would hate to implement this without understanding how it works.

thanks for all the great examples!

o, and GoToLoop, that forum link doesn't work (already had found it) it only displays page one of the results of the forums as far as I can tell :(

lukasz

quark, your code seems to throw an error on line 16

lukasz

PhiLho, I tried implementing your code into what I already have and I am not sure what it happening, if its that canvas isnt updating fast enough or the math doesn't work. but my line spins like a clock and I need to test it against a shape I am drawing on the canvas, it seems sometimes they pass, other times they do not, and sometimes the opposite part of the line seems to make it pass the test (does this in the example as well)

I would like it to only pass if it is within the radius of the line/circle

here is my code (this is processing.js by the way:

var shape;
  PVector p1;
  PVector p2;
  float a;
  float b;
  var times = 0;
  void setup(){
    stroke(255);
    smooth();

    shape = {
      coordinates: []
    };
  }
  void draw() {
    background(40, 42, 42);
    var centerX = jQuery(document).height()/2;
    var centerY = jQuery(document).width()/2;
    fill(40);
    float x = width/2;
    float y = height/2;
    float d = width * 0.5;

    fill(80);
    noStroke();
    float s = map(millis(), 0, 6000, 0, TWO_PI) - HALF_PI; 
    stroke(255);
    strokeWeight(1);

    ellipse( centerY,centerX,1,1);
    float y = sin(s) * 402 + centerX;
    float x = cos(s) * 402 + centerY;

    p1 = new PVector(centerX, centerY);
    p2 = new PVector(x, y);
    PVector sub = PVector.sub(p2, p1);

    a = sub.y / sub.x;
    b = p1.y - a * p1.x;

    noStroke();
    ellipse( x,y,5,5)
    stroke(55);
    line(centerY, centerX,x ,y);

    drawShape(228, 44, 136);

    for (var i = 0; i < shape.coordinates.length; i++) {
      if ((shape.coordinates[i].y > (a * shape.coordinates[i].x + b - 0.5)) && (shape.coordinates[i].y < (a * shape.coordinates[i].x + b + 0.5))) {
        fill(0, 255, 0)
        ellipse(shape.coordinates[i].x, shape.coordinates[i].y, 20, 20)
        times++;
        console.log("pass "+times)
      }
    }
  }

  function drawShape(r, g, b) {
    setFillAndStroke(r, g, b)
    beginShape();
      getPoints();
    endShape();
  }

  function setFillAndStroke(r, g, b){
    stroke(r, g, b);
    fill(r, g, b, 100); 
  }

  function getPoints() {
    for (var i = 0; i < shape.coordinates.length; i++) {
      vertex(shape.coordinates[i].x, shape.coordinates[i].y)
    };
  }

  void mouseReleased() {
    shape.coordinates.push({x: mouseX, y: mouseY});
    console.log(shape.coordinates);
  }

I also have the example up here: http://hellowoo.com/apps/soundlasorz/app.html

if you have any idea what I am doing wrong please let me know. even a link to how to learn to implement this would be great, at the moment I am a bit ignorant to how the math works.

you draw by clicking on the canvas by the way, you can see how it passes and other times it opposite side passes.

quark

quark, your code seems to throw an error on line 16

I have just copied the code from above into Processing 2 and it worked fine for me!

PhiLho

Perhaps he was talking about using your program in JS mode. You use a variable named line, that might destroys the line() function.

quark

@PhiLho I tried changed the variable line to the_line still worked in Java mode so I tried it in JS mode - all I got was a blank screen :(

It appears that many of the PVector methods are not implemented in JS mode so I kept hacking at the problem and I eventually got it to work in both Java and JS mode. H =D> here is the code.

  /**
   Determines whether a point'c' is close to a line from
   'a' to 'b' <br>
   If the point is close enough then the point haloe will be green else it is red. <br>
   It works by calculating the point nearest point (pj)  on the line to the point 'c'.
   It then determoines whether 'pj' is inside the line segment a-->b and that the dist
   c<>pj is less than a closeness value.
   */

  PVector a, b, c, pj;
  float closeness;

  public void setup() {
    size(400, 400);
    a = new PVector(121, 87);
    b = new PVector(299, 322);
    c = new PVector(160, 410);
    pj = new PVector();
    closeness = 1;
  }

  public void draw() {
    background(255);
    // Offset the cursor so we can see what is happening
    c.set(mouseX - 20, mouseY - 20);
    // Is c on the line a --> b
    // pj is the nearest point on the line
    boolean ol = isOnLine(a, b, c, pj);

    noFill();
    stroke(160);
    strokeWeight(1.1);
    line(a.x, a.y, pj.x, pj.y);
    line(c.x, c.y, pj.x, pj.y);
    stroke(0);
    strokeWeight(1.5);
    line(a.x, a.y, b.x, b.y);
    noStroke();
    ellipse(a.x, a.y, 4, 4);
    ellipse(b.x, b.y, 4, 4);
    // Point halo
    if (ol)
      fill(0, 255, 0, 64);
    else
      fill(255, 0, 0, 64);
    ellipse(c.x, c.y, 20, 20);
    // Point
    fill(0);
    ellipse(c.x, c.y, 4, 4);
  }

  boolean isOnLine(PVector v0, PVector v1, PVector p, PVector vp) {
    // Return minimum distance between line segment vw and point p
    PVector the_line = PVector.sub(v1, v0);
    float l2 = the_line.mag();
    l2 = l2 * l2;
    if (l2 == 0.0) {
      vp.set(v0);
      return false;
    }
    PVector pv0_line = PVector.sub(p, v0);
    float t = pv0_line.dot(the_line)/l2;
    pv0_line.normalize();
    vp.x = the_line.x * t + v0.x;
    vp.y = the_line.y * t + v0.y;
    float d = sqrt((p.x-vp.x)*(p.x-vp.x) +(p.y-vp.y)*(p.y-vp.y)); 
    if (t >= 0 && t <= 1 && d <= closeness)
      return true;
    else
      return false;
  }

GoToLoop

JS Mode is still pretty much processing 1.5.1! >-)