We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
Index › Programming Questions & Help › Programs › Point to line distance
‹ Previous Topic | Next Topic ›
Page Index Toggle Pages: 1
Point to line distance (Read 3674 times)
hansi
Point to line distance
Jun 15th, 2010, 4:34pm  
When calculating the point to line distance you'll mostly find equations that give the perpendicular distance to an infinitely long line, like this here: http://www.intmath.com/Plane-analytic-geometry/Perpendicular-distance-point-line...

I really needed to find the distance to a line segment, which involved some matrix fun. Here's my solution, in case anyone needs something similar:

Code:

// press space to reset
// click for randomness
// drag to move

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

int index = 0; 

void setup(){
  size( 600, 600 ); 
  smooth(); 
  textFont( loadFont( "SansSerif-12.vlw" ) ); 
  
  x1 = width/2 - 100;
  y1 = height/2;
  x2 = width/2 + 100;
  y2 = height/2;
}


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

  fill( 255, 255, 0 ); 
  noStroke(); 
  ellipse( mouseX, mouseY, 10, 10 ); 
  
  PVector result = getDistance( x1, y1, x2, y2, mouseX, mouseY ); 
  stroke( 150 ); 
  line( mouseX, mouseY, result.x, result.y ); 
  
  stroke( 255 ); 
  text( "The distance to the line is: " + result.z, 10, 10 ); 
}


void mousePressed(){
  x1 = 100+random(width-200); 
  y1 = 100+random(height-200); 
}

void mouseDragged(){
  x1 = mouseX; 
  y1 = mouseY; 
}

void keyPressed(){
  x1 = width/2-100; 
  y1 = height/2; 
}


/**
 * Returns a point on the line (x1,y1) -> (x2,y2) 
 * that is closest to the point (x,y)
 * 
 * The result is a PVector. 
 * result.x and result.y are points on the line. 
 * The result.z variable contains the distance from (x,y) to the line, 
 * just in case you need it :) 
 */
PVector getDistance( float x1, float y1, float x2, float y2, float x, float y ){
  PVector result = new PVector(); 
  
  float dx = x2 - x1; 
  float dy = y2 - y1; 
  float d = sqrt( dx*dx + dy*dy ); 
  float ca = dx/d; // cosine
  float sa = dy/d; // sine 
  
  float mX = (-x1+x)*ca + (-y1+y)*sa; 
  
  if( mX <= 0 ){
    result.x = x1; 
    result.y = y1; 
  }
  else if( mX >= d ){
    result.x = x2; 
    result.y = y2; 
  }
  else{
    result.x = x1 + mX*ca; 
    result.y = y1 + mX*sa; 
  }
  
  dx = x - result.x; 
  dy = y - result.y; 
  result.z = sqrt( dx*dx + dy*dy ); 
  
  return result;   
}


You'll only need the bottom half of the code, the top is just to illustrate how to use it.


Edited:
code is a little more compact now

Edited:
removed the calculation of mY, it's never used and just wastes time
Back to top
« Last Edit: Jun 18th, 2010, 10:09am by hansi »  
WWW kritzikratzi  
Smitty
Re: Point to line distance
Reply #1 - Jun 15th, 2010, 6:42pm  
Nice work, hansi.  These geometric things are always tricky, and it can be tough to get a good result for something like this when there are multiple cases to consider (e.g., closest point at one end of the segment vs. somewhere in the middle).

A few suggestions for making the code a little smaller and perhaps optimizing a bit:

First, you can make the following changes at the start of getDistance() (old code commented out)
Code:

  //float dx = abs( x1 - x2 ); 
  //float dy = abs( y1 - y2 ); 
  float dx = x2 - x1;
  float dy = y2 - y1;

  float d = sqrt( dx*dx + dy*dy ); 

  //float a = atan2( y2 - y1, x2 - x1 ); 
  //float ca = cos( a ); 
  //float sa = sin( a ); 
  float ca = dx/d;
  float sa = dy/d;

  float mX = (-x1+x)*ca + (-y1+y)*sa; 
  float mY = (-y1+y)*ca + ( x1-x)*sa;


Running dx and dy through abs() is unnecessary, since you're squaring them anyway when you find d.  And calculating them this way lets you skip the trig calls, which will save you a lot of time, and just compute ca and sa in one step.

Second, you can save some space in the if-else tree at the end by taking the distance calculation out, like this:
Code:
  if( mX <= 0 ) {
    result.x = x1; 
    result.y = y1; 
  } 
  else if ( mX >= d ) {
    result.x = x2;
    result.y = y2;
  }
  else {
    result.x = x1 + mX*ca; 
    result.y = y1 + mX*sa;
  }
  
  dx = x - result.x; 
  dy = y - result.y; 
  d = sqrt( dx*dx + dy*dy ); 
  result.z = d;


This might be a little bit slower for the case where the closest point is between the endpoints, since you'll be doing a square-root calculation instead of just an abs(), but I think it's a worthwhile tradeoff to make the code shorter and easier to understand and maintain.
Back to top
 
 
hansi
Re: Point to line distance
Reply #2 - Jun 16th, 2010, 2:16am  
hey smitty!

thanks for the suggestions, i've already updated the code.
it was two in the morning yesterday and i really couldn't be bothered to go through the code again after i had it working ... Smiley


h,-
Back to top
 
WWW kritzikratzi  
Smitty
Re: Point to line distance
Reply #3 - Jun 16th, 2010, 8:12am  
hansi wrote on Jun 16th, 2010, 2:16am:
thanks for the suggestions, i've already updated the code.
it was two in the morning yesterday and i really couldn't be bothered to go through the code again after i had it working ... Smiley

Believe me, I know that feeling!  Wink  Glad I could help.

Two other things that occurred to me about this part:

Code:

  float dx = x2 - x1;
  float dy = y2 - y1;

  float d = sqrt( dx*dx + dy*dy ); 

  float ca = dx/d;
  float sa = dy/d;

  float mX = (-x1+x)*ca + (-y1+y)*sa; 
  float mY = (-y1+y)*ca + ( x1-x)*sa;

First, if you made all the changes I suggested, then you no longer need mY, so you can leave that out.

Second, the variables dx, dy, d, ca, and sa depend only on the endpoints of the line (x1, x2, y1, y2), not on the point (x, y), so you can save time by calculating them when you set a new line, and then re-use the same values until you change the location of the endpoints.  So, for example:

Code:

// after setting a new x1, x2, y1, y2:

PVector point1 = new PVector(x1, y1, 0);
PVector lineUnit = new PVector(x2 - x1, y2 - y1, 0);
float d = lineUnit.mag();
lineUnit.normalize();

This uses d to store the length of the line.  The normalize() method shortens or lengthens lineUnit to a length of 1, pointing in the same direction--so afterwards, lineUnit is simply [cos(a), sin(a), 0] where a is the angle the line points (from point 1 to point 2).

Then you can change getDistance() to work something like this:
Code:

PVector getDistance(float x1, float x2, PVector lineUnit, float d, float x, float y) {
  float ca = lineUnit.x;
  float sa = lineUnit.y;

  // proceed as before...
}

Back to top
 
 
hansi
Re: Point to line distance
Reply #4 - Jun 18th, 2010, 10:43am  
hey smitty!

thanks again for suggestions, i removed mY completely.

as for your other suggestion about pre-calculating distance+cos/sin: this definitely makes sense if one always checks against a static set of lines, but also means more work before the function call can happen.
i think the current version is a good trade-off between ease of use and speed.

so for completeness: here's a version that is totally crazy fast as long as your lines rarely change.
i put the whole thing into a class cause i'm not a big fan of having many variables flying around.

Code:

// press space to reset
// click for randomness
// drag to move

Line myLine; 

void setup(){
  size( 600, 600 ); 
  smooth(); 
  textFont( loadFont( "SansSerif-12.vlw" ) ); 
  
  myLine = new Line( width/2 - 100, height/2, width/2 + 100, height/2 ); 
}


void draw(){
  background( 0 ); 
  
  stroke( 255 ); 
  myLine.draw(); 

  fill( 255, 255, 0 ); 
  noStroke(); 
  ellipse( mouseX, mouseY, 10, 10 ); 
  
  PVector result = myLine.getDistance( mouseX, mouseY ); 
  stroke( 150 ); 
  line( mouseX, mouseY, result.x, result.y ); 
  
  fill( 255 ); 
  text( "The distance to the line is: " + result.z, 10, 10 ); 
}


void mousePressed(){
  myLine.x1 = 100+random(width-200); 
  myLine.y1 = 100+random(height-200); 
  myLine.update(); 
}

void mouseDragged(){
  myLine.x1 = mouseX; 
  myLine.y1 = mouseY; 
  myLine.update(); 
}

void keyPressed(){
  myLine.x1 = width/2-100; 
  myLine.y1 = height/2; 
  myLine.update(); 
}

//////////////////////////////////////////////

class Line{
  // where does the line start/end? 
  public float x1, x2, y1, y2; 
  
  // some happy math variables
  private float dx, dy, d, ca, sa, mx, dx2, dy2; 
  
  // we use this to store the result, 
  // so if you want to store the result and calculate again 
  // you should do 
  // PVector mine = new PVector(); 
  // mine.set( line.getDistance( mouseX, mouseY ) ); 
  private PVector result; 
  
  public Line( float x1, float y1, float x2, float y2 ){
    this.x1 = x1; 
    this.y1 = y1; 
    this.x2 = x2; 
    this.y2 = y2; 
    result = new PVector(); 
    update(); 
  }
  
  /**
   * Call this after changing the coordinates!!! 
   */
  public void update(){
    dx = x2 - x1; 
    dy = y2 - y1; 
    d = sqrt( dx*dx + dy*dy ); 
    ca = dx/d; // cosine
    sa = dy/d; // sine 
  }
  
  /**
   * Returns a point on this line
   * that is closest to the point (x,y)
   * 
   * The result is a PVector. 
   * result.x and result.y are points on the line. 
   * The result.z variable contains the distance from (x,y) to the line, just in case you need it :) 
   */
  PVector getDistance( float x, float y ){
    mx = (-x1+x)*ca + (-y1+y)*sa;
    
    if( mx <= 0 ){
      result.x = x1; 
      result.y = y1; 
    }
    else if( mx >= d ){
      result.x = x2; 
      result.y = y2; 
    }
    else{
      result.x = x1 + mx*ca; 
      result.y = y1 + mx*sa; 
    }
    
    dx2 = x - result.x; 
    dy2 = y - result.y; 
    result.z = sqrt( dx2*dx2 + dy2*dy2 ); 
    
    return result;   
  }
  
  /**
   * Draw it! 
   */
  public void draw(){
    line( x1, y1, x2, y2 ); 
  }
}



obviously there are many more optimizations one could go for, e.g. in my own project i don't even need the result.x/result.y variables so i threw them out alltogether and only return the distance.
Back to top
 
WWW kritzikratzi  
Page Index Toggle Pages: 1
‹ Previous Topic | Next Topic ›