Sunday, March 24, 2013

Distance between point and the line Part 2

After I published my first solution I got feedback that the same can be achieved calculating other way. So I tried implement another way:
public double distanceBetweenLineAndPoints(Point a, Point b, Point c){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    if(dy == 0){
        //we have vertical line
        return distanceBetweenPoints(new Point(c.x, a.y), c);
    }
    if(dx == 0){
        //we have horizontal line
        return distanceBetweenPoints(new Point(a.x, c.y), c);
    }
    double slope = dy / dx;
    //lets check - may be c point is on the line
    if(c.y - a.y == slope * (c.x - a.x)){
        //yes, it is
        return 0;
    }
    Point aa = new Point();
    Point bb = new Point();
    aa.x = c.x;
    aa.y = slope * (c.x - a.x)+ a.y;
    bb.x = (c.y - a.y)/slope + a.x;
    bb.y = c.y;

    return (distanceBetweenPoints(bb, c) / distanceBetweenPoints(aa, bb)) * 
   distanceBetweenPoints(aa, c);
}

Is it faster?

I did two tests:
1. I took solution 1 and 2 gave them the same data (line is not horizontal/vertical and point is not on the line) - solution 1 was 10-15% faster.
2. I add the same checking (the line is vertical/horizontal or point is on the line) to solution 1 and repeated test - both solution were performing almost identically.

Friday, March 22, 2013

Distance between point and the line


Hei, I got Challenge to my email and I thought - why not :)

Distance:
In 2D coordinate system we have three points A(x,y) B(x,y) C(x,y)
where x,y can be positive and negative integer numbers
If Points A and B define endless line, write function which returns the 
distance between point C and the line defined by point A, B
 
I havn't thought it will be so easy:

public class DistanceCalculator {
    public static double distanceBetweenPoints(Point p1, Point p2){
        int dx = p1.x - p2.x;
        int dy = p1.y - p2.y;
        return Math.sqrt(dx*dx + dy*dy);
    }
    public static double distanceBetweenLineAndPoints(Point a, Point b, Point c){
        //lets find area of triangle
        double ab = distanceBetweenPoints(a, b);
        double bc = distanceBetweenPoints(b, c);
        double ca = distanceBetweenPoints(c, a);
        double p = (ab + bc + ca)/2;

        double area = Math.sqrt(p*(p-ab)*(p-bc)*(p-ca));

        return (area*2)/ab;
    }
}
public class Point {
    public int x;
    public int y;

    public Point (int x, int y){
        this.x = x;
        this.y = y;
    }
}
If you like it - there is also Part2.