Point inside a triangle or NOT

Problem

Given three corner points of a triangle, and one more point P. Write a function to check whether P lies within the triangle or not.

Example

For example, consider the following program, the function should return true for P(10, 15) and false for P’(30, 15)

              B(10,30)
                / \
               /   \
              /     \
             /   P   \      P'
            /         \
     A(0,0) ----------- C(20,0) 

Solution

Method 1 - Area of triangles made by point and other 2 vertices of triangle
Let the coordinates of three corners be (x1, y1), (x2, y2) and (x3, y3). And coordinates of the given point P be (x, y)

1. Calculate area of the given triangle, i.e., area of the triangle ABC in the above diagram. Area A = [ x1(y2 - y3) + x2(y3 - y1) + x3(y1-y2)]/2
2. Area A1 = Calculate area of the triangle PAB (using the same formula)
3. Area A2 = Calculate area of the triangle PBC
4. Area A3 = Calculate area of the triangle PAC
5. If P lies inside the triangle, then A1 + A2 + A3 must be equal to A.

 Here is the code

float area(int x1, int y1, int x2, int y2, int x3, int y3)
{
   return Math.abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0);
}

boolean isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)
{   
   // Calculate area of triangle ABC 
   float A = area (x1, y1, x2, y2, x3, y3);
 
   // Calculate area of triangle PBC   
   float A1 = area (x, y, x2, y2, x3, y3);
 
   // Calculate area of triangle PAC   
   float A2 = area (x1, y1, x, y, x3, y3);
 
   // Calculate area of triangle PAB    
   float A3 = area (x1, y1, x2, y2, x, y);
   
   // Check if sum of A1, A2 and A3 is same as A 
   return (A == A1 + A2 + A3);
}

But can this differentiate whether the point lies on the edges, I don't thing so. It can only tell whether it is in triangle or not.

Method 2 - Using Barycentric coordinates
Solve the following equation system:

p = p0 + (p1 - p0) * s + (p2 - p0) * t

The point p is inside the triangle if 0 <= s <= 1 and 0 <= t <= 1 and s + t <= 1.
s,t and 1 - s - t are called the barycentric coordinates of the point p.

Now, the barycentric coordinates, generally called alpha, beta, and gamma, are calculated as follows:

float alpha = ((p2.y - p3.y)*(p.x - p3.x) + (p3.x - p2.x)*(p.y - p3.y)) /
        ((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y));
float beta = ((p3.y - p1.y)*(p.x - p3.x) + (p1.x - p3.x)*(p.y - p3.y)) /
       ((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y));
float gamma = 1.0f - alpha - beta;

If all of alpha, beta, and gamma are greater than 0, then the point p lies within the triangle made of points p1, p2, and p3.
The explanation behind this is that a point inside a triangle can be described using the points of the triangle, and three coefficients (one for each point, in the range [0,1]):

p = (alpha)*p1 + (beta)*p2 + (gamma)*p3

Rearranging this function gives you the formula to compute barycentric coordinates, but I feel like the steps to do so might be beyond the scope of the question. They are provided on the Wikipedia page that I linked up top.

References

• http://www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/
• http://stackoverflow.com/questions/13300904/determine-whether-point-lies-inside-triangle

Read More

Point inside a rectangle or not

Problem

Given a 2D point and a rectangle, determine if the point is inside the rectangle.

Solution

Method 1 - Calculate the area of triangles with 2 vertices of rectangle and point
P(x,y), and rectangle A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4)
Calculate the sum of areas of △APD,△DPC,△CPB,△PBA.

1. If this sum is greater than the area of the rectangle, then P(x,y) is outside the rectangle.
2. Else if this sum is equal to the area of the rectangle (observe that this sum can not be less than the later),
   1. if area of any of the triangle is 0, then P(x,y) is on the rectangle (in fact on that line corresponding to the triangle of area=0). Observe that the equality of the sum is necessary, only area=0 is not sufficient),
   2. else P(x,y) is is inside the rectangle.

Acceptably this approach needs substantial amount of computation. This approach can be employed to any irregular polygon, too.

Method 2 - Perpendicular distance of point P to the sides
Another way is to calculate the perpendicular distances of P(x,y) from all the 4 lines AB,CD,AD,BC

To be inside the rectangle, the perpendicular distances from AB,P_AB(say) and from CD,P_CD(say) must be less than |AD|=|BC| and the perpendicular distances from AD,P_AD(say) and from BC,P_BC(say) must be less than |CD|=|AB|. Here , the areas of each of the four triangles < 1/2the area of the rectangle.

1. If one of the perpendicular distances is greater than the respective length, then P(x,y) is outside the rectangle.
2. This essentially implies and is implied by the statement : the area of the respective triangle > 12the area of the rectangle (as commented by Ben Voigt) as △APD=1/2*AD⋅P_AD.
3.     Else if P_AB=0 and P_CD=|AD| , then P(x,y) is on AB . So, △PBA=0 and △PCD=12the area of the rectangle.

    Observe that in this case, the rest two perpendicular distances P_AD,P_BC must be ≤ |AB|=|CD|, P_BC=|AB|⟹P(x,y) is lies on AD i.e, P coincides with A as it is already on AB .

Method 3  - Scalar product
The trick is to use dot product to find the projected line from point P onto the rectangle sides, and if its length is shorter than the sides, then the point must be inside the rectangle.
Let P be the point we have to check, then it is inside rectangle iff:

(0<AP⋅AB<AB⋅AB)∧(0<AP⋅AD<AD⋅AD)

References

• http://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle
• http://sudhansu-codezone.blogspot.in/2012/02/point-inside-rectangle-or-not.html

Read More

Form a circle from 3 points

Problem

Given 3 points which are not colinear (all on the same line) those three points uniquely define a circle. But, how do you find the center and radius of that circle?
Propose a simple algorithm for this.

Solution

1. join two pairs of vertices.
2. Form the equations for the two lines.
3. Form the equations of the perpendicular bisectors of each of the equations obtained in step 2.
4. Solve the two equations from step 3. The point of intersection is the centre.
5. calculate the radius.

References

• http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2
• http://sudhansu-codezone.blogspot.in/2012/03/form-circle-from-3-points.html

Read More

Find a line which passes the most number of points

Problem

Given a two dimensional graph with points on it, find a line which passes the most number of points.

Solution
Method 1 - Naive solution
This is the brute force solution. We take point 1, and then point 2 and make a line. Now in the third nested loop, check if point 3 is existing on the same line or not.
Pseudocode

Line findLineWithMaxPoint(Set points){
   foreach Point p1 in points
      foreach Point p2  in (points - {p1}){
         Line l = makeLine(p1,p2);
         int count = 2 //line contains p1 and p2
         foreach(Point p3 in (points-{p1,p2})){
            if(l.contains(p3))
               count++;
         }
         if(maxCount<count){
            count = maxCount;
            resultLine = l;
         }
      }
return resultLine;
}

As we can see there are 3 nested loops, and hence time complexity : O(n^3).

Java code

public class Line {
    private double slope;
    private double intercept;
 
    private final double THRESHOLD = Math.pow(10, -8);
 
    public Line(double slope, double intercept) {
        super();
        this.slope = slope;
        this.intercept = intercept;
    }
 
    public Line(Pair<Double> p1, Pair<Double> p2) {
        this.slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());
        this.intercept = (p2.getX() * p1.getY() - p1.getX() * p2.getY())
                / (p2.getX() - p1.getX());
    }
 
    public boolean contains(Pair<Double> p) {
        double x = p.getX();
        double y = p.getY();
        return Math.abs(y - (slope * x + intercept)) < THRESHOLD;
    }
}
 
public static Line findLine(Set<Pair<Double>> points) {
    int maxNumber = -Integer.MAX_VALUE;
    int number = 0;
    Line result = null;
    for (Pair<Double> p1 : points) {
        for (Pair<Double> p2 : points) {
            if (!p1.equals(p2)) {
                number = 0;
                Line line = new Line(p1, p2);
                for (Pair<Double> p : points) {
                    if (line.contains(p))
                        number++;
                }
                if (number > maxNumber) {
                    maxNumber = number;
                    result = line;
                } 
            }
        }
    }
    return result;
}

Method 2 - Use hashtable
Problem with above approach is that the lines may be duplicate. And if we have points p1, and p2 already covered as part of line, which helped us find p3, when we select p1 and p3, we will again select p2.

We have a bunch of line segments, represented as a slope and y-intercept, and we want to find the most common slope and y-intercept. How can we find the most common one? This is really no different than the old "find the most common number in a list of numbers" problem. We just iterate through the lines segments and use a hash table to count the number of times we've seen each line.

This can be solved in O(n^2) time and O(m) space. where m is the distinct number of lines among all given points.

1. Use a hash table - key is line and number of appearance of line as value.
2. For each pair of points find the line in slope y intercept form
3. if the line is not there in hash table, add it to the hash table with appearance value 1
4. if the line is already in hash table, increment the appearance value
5. line with the max number of appearance in the hash table is the result.

Java code
In java we have to implement a hashCode() method to make the class object uniquely identifiable by the hashtable.

public static Line findBestLine(GraphPoint[] points) {
    Line bestLine = null;
    HashMap<Line, Integer> line_count = new HashMap<Line, Integer>();
    for (int i = 0; i < points.length; i++) {
        for (int j = i + 1; j < points.length; j++) {
            Line line = new Line(points[i], points[j]);
            if (!line_count.containsKey(line)) {
                line_count.put(line, 0);
            }
            line_count.put(line, line_count.get(line) + 1);
            if (bestLine == null
                    || line_count.get(line) > line_count.get(bestLine)) {
                bestLine = line;
            }
        }
    }
    return bestLine;
}
 
public class Line {
    private static double epsilon = .0001;
    public double slope;
    public double intercept;
    private boolean infinite_slope = false;
 
    public Line(GraphPoint p, GraphPoint q) {
        if (Math.abs(p.x - q.x) > epsilon) { // if x’s are different
            slope = (p.y - q.y) / (p.x - q.x); // compute slope
            intercept = p.y - slope * p.x; // y intercept from y=mx+b
        } else {
            infinite_slope = true;
            intercept = p.x; // x-intercept, since slope is infinite
        }
    }
 
    public boolean isEqual(double a, double b) {
        return (Math.abs(a - b) < epsilon);
    }
 
    @Override
    public int hashCode() {
        int sl = (int) (slope * 1000);
        int in = (int) (intercept * 1000);
        return sl | in;
    }
 
    @Override
    public boolean equals(Object o) {
        Line l = (Line) o;
        if (isEqual(l.slope, slope) && isEqual(l.intercept, intercept)
                && (infinite_slope == l.infinite_slope)) {
            return true;
        }
        return false;
    }
}

• Be careful about the calculation of the slope of a line. The line might be completely vertical. We can keep track of this in a separate flag (infinite_slope). We need to check this condition in the equals method.
• Remember that when we perform division to calculate the slope, division is not exact. Therefore, rather than checking to see if two slopes are exactly equal, we need to check if they’re different by greater than epsilon, in our case 10^-8.

Method 3 - Hough transform
Not really sure how hough transform works, but you can read more here.

References
http://tianrunhe.wordpress.com/2012/04/03/find-a-line-which-passes-the-most-number-of-points/

Read More

Find a line to cut two squares in half

Problem: 

Given two squares on a two dimensional plane, find a line that would cut these two squares in half.

Solution:

Any Line passing the centers of the two squares will cut them in halves. So, we have to connect the lines between the center of the 2 squares. The straight line that connects the two centers of the two squares will cut both of them into half.

Code in java

public class Square {
   public double left;
   public double top;
   public double bottom;
   public double right;
   public Square(double left, double top, double size) {
          this.left = left;
          this.top = top;
          this.bottom = top + size;
          this.right = left + size;
   }

   public Point middle() {
          return new Point((this.left + this.right) / 2,
                                       (this.top + this.bottom) / 2);
   }

   public Line cut(Square other) {
          Point middle_s = this.middle();
          Point middle_t = other.middle();
          if (middle_s == middle_t) {
                 return new Line(new Point(left, top),
                 new Point(right, bottom));
          } else {
                 return new Line(middle_s, middle_t);
          }
   }
}

Note specific to java  - If == operator between the 2 point objects in cut method. I am not sure if it will work, as == operator in java compares references. So, better approach is Point should implement equals() method and compare the 2 point object like this:

if(middle_s.equals(middle_t)){
    ....
}

Thanks.
References :
http://tianrunhe.wordpress.com/2012/04/02/find-a-line-to-cut-two-squares-in-half/
http://stackoverflow.com/questions/6886836/can-i-use-the-operator-to-compare-point-objects-in-java 

Read More

Determine whether two lines would intersect on a Cartesian plane

Problem

Given two lines on a Cartesian plane, determine whether the two lines would intersect.

Solution
 On a Cartesian plane, if two lines do not intersect, they must be parallel with each other. Hence, their slopes must be the same. If their slopes are different, they would intersect. A line is represented as ax+by+c=0 on a Cartesian plane and the slope is given by -\frac{a}{b}. Therefore if -\frac{a_{0}}{b_{0}} \neq -\frac{a_{1}}{b_{1}} for two lines, they will intersect.

public class Line {
    static final double epsilon = 0.000001;
    public double slope;
    public double yintercept;
 
    public Line(double s, double y) {
        slope = s;
        yintercept = y;
    }
 
    public boolean intersect(Line line2) {
        return Math.abs(slope - line2.slope) > epsilon
                || Math.abs(yintercept - line2.yintercept) < epsilon;
    }
}

Two lines can be the same. In that case, we assume they intersects (overlap). We need to consider the floating system in a computer. Never use == to compare two floating numbers in java.

Read More