Thursday, April 20, 2023

[Solved] How to check if given point is inside Triangle or not in Java? Example

One of the interesting problem from Java Programming interviews is, "write a program to check if given point lies inside a triangle or not?". You will be given co-ordinates of vertices and the point as part of problem and you need to write a function e.g. isInside() which return true if point is within the triangle and false if it is not. For example, in the triangle specified by vertices (11, 31), (21, 1), and (1, 1) the point (11, 16) are inside the triangle and point (30,17) are outside of the triangle. It's a good coding interview question if you have not heard before, just think about how do you prove if the point lies inside the triangle or not? It's not a difficult algorithm and you can think of it by just trial and error. 

Earlier, I have shared how to check if two rectangles are overlapping with each other or not, How to print a left triangle star pattern, and in this article, I am going to share how to check if a point lies inside a triangle or not. These two triangle based questions are quite popular on coding interviews and I suggest you to practice them not just for interview preparation but also to improve your coding skills. 


How to check if given point is inside Triangle or not?

Well, you can find out if a given point is within the triangle or not by calculating area of main triangle with vertices a, b, and c as well other three triangle formed by joining point P with other two vertices of triangle e.g. PAB, PBC, and PCA. 

[Solved] How to check if given point is inside Triangle or not in Java

If combined area of this triangle is equal to area of ABC than point lies inside the triangle, if not then point is outside the triangle. Interesting right? 

Well, now question comes how do you calculate area of triangle in Java? Well, there are many ways e.g. you can use the approach given here which calculate area of triangle by calculating base and height, but in this case we have co-ordinates of vertices, so we'll use a different formula to calculate area of triangle as shown below

Area A = [ x1(y2 - y3) + x2(y3 - y1) + x3(y1-y2)]/2

How to calculate area of Triangle in Java




Java Program to check if given point is within the triangle or outside

Here is a our complete Java program to find out if given point is within a triangle or not:

*
 * Java Program to check if given point lies inside a triangle or not.
 * A point will lie inside a triangle if area of triangle will be
 * equal to three triangle made by joining given point to other
 * two vertices of triangle.
 * e.g. if triangle is ABC and point is P
 * then point is within the triangle if
 * area of ABC = area of PAB + area of PBC + area of PCA
 */

public class Main {

    public static void main(String[] args) {
        Point A = new Point(11, 31);
        Point B = new Point(21, 1);
        Point C = new Point(1, 1);
        Point in = new Point(11, 16);
        Point out = new Point(30, 17);

        Triangle t = new Triangle(A, B, C);
        printResult(isInsideTriangle(t, in ));
        printResult(isInsideTriangle(t, out));

    }

    /**
     * Java method to check if given point is inside given
     * triangle or not
     * @param t
     * @param p
     * @return true if point p is inside triangle t
     */
    public static boolean isInsideTriangle(Triangle t, Point P) {
        float areaOfABC = t.area();
        float areaOfPAB = new Triangle(P, t.A, t.B).area();
        float areaOfPBC = new Triangle(P, t.B, t.C).area();
        float areaOfPCA = new Triangle(P, t.C, t.A).area();

        return (areaOfABC == areaOfPAB + areaOfPBC + areaOfPCA);
    }

    public static void printResult(boolean result) {
        if (result) {
            System.out.println("Point P is inside triangle");
        } else {
            System.out.println("Point p is ouside of triangle");
        }
    }

}

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

}

class Triangle {
    Point A;
    Point B;
    Point C;

    public Triangle(Point a, Point b, Point c) {
        this.A = a;
        this.B = b;
        this.C = c;
    }

    /**
     * Java method to return area of triangle using vertices
     * as per following formula
     * area = (Ax(By -Cy) + Bx(Cy -Ay) + Cx(Ay - By))/2
     * @return
     */
    public float area() {
        float area = (A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y)) / 2.0 f;
        return Math.abs(area);
    }
}

Output
Point P is inside triangle
Point p is outside of triangle

You can further enhance the program to take input from user for both vertices of triangle and the point which you want to test. that will make the program more interactive. you can use the Scanner class to take user input in Java. 


That's all about how to check if a given point lies within the triangle or not. This is an interesting coding question and you should try to solve by yourself first. The key here is not just to know the formula to calculate the area of triangle using vertices but also how to convert that formula into code, that's why this is also a programming exercise for people who wants to learn coding.

Other Coding Interview Questions  you may like

  • 10 Free Data Structure and Algorithm Courses for Programmers (courses)
  • How to implement Quicksort algorithm without recursion? (tutorial)
  • How to perform a Binary Search Algorithm in Java? (tutorial)
  • How to remove an element from an array in Java? (solution)
  • How to implement the insertion sort algorithm in Java? (tutorial)
  • How to find one missing number in a sorted array? (solution)
  • How to find duplicates from an unsorted array in Java? (solution)
  • Difference between Comparison and Non-Comparison based sorting algorithm? (answer)
  • How to implement the Bubble sort algorithm in Java? (tutorial)
  • How to remove duplicates from an array in Java? (solution)
  • How to find all pairs in an array whose sum is equal to k (solution)
  • How to find a missing value from an array containing 1 to 100? (solution)
  • How to find the most significant and smallest number in an array without sorting? (solution)
  • How to check if an array contains a particular value? (solution)
  • How to implement Bucket Sort in Java? (tutorial)
  • 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article. If you like this Coding problem, then please share it with your friends and colleagues. If you have any questions or feedback, then please drop a note.

No comments :

Post a Comment