How to Check if a Given Point Lies Inside a Triangle in Java? [solved]

Hello guys, its been long time I shared a coding problem so I thought to share one today and its one of the interesting one, how to check if a give point is inside a triangle or not? Determining whether a point lies inside a triangle is a common problem in computational geometry. It finds applications in various fields, such as computer graphics, robotics, and image processing. In this article, we will delve into the mathematical concepts behind this problem and explore a practical Java implementation. We will examine the algorithm step-by-step and illustrate it with code examples. Additionally, we will provide unit tests to ensure the accuracy and reliability of our implementation.

How to Check if a Given Point Lies Inside a Triangle in Java

Before we jump into the code let's understand the problem and the maths behind the solution, this will help us to code easily.

Understanding the Problem

Given a triangle defined by three vertices (points A, B, and C), our objective is to check if a fourth point lies within this triangle. To achieve this, we will compute the area of both the entire triangle (T) and three sub-triangles (T2, T3, and T4) formed by the fourth point and the original triangle's vertices.

The Barycentric Coordinate System

The Barycentric Coordinate System is a key concept in solving this problem. In this coordinate system, every point inside a triangle can be expressed as a combination of its vertices (A, B, and C) with non-negative weights (λ1, λ2, and λ3) such that λ1 + λ2 + λ3 = 1.

Computing the Area of a Triangle

To compute the area of a triangle, we can use the shoelace formula or the determinant formula. The code snippet provided in the article utilizes the determinant formula to calculate the area of each triangle.

Checking if the Point Lies Inside

Once we have the areas of the original triangle and the sub-triangles formed by the fourth point, we sum up the areas of T2, T3, and T4. If the sum of these areas equals the area of the entire triangle (T), then the fourth point lies inside the triangle.

Implementing the Algorithm in Java

Here is our complete Java program to demonstrate the implementation of the algorithm using a custom Triangle class. The class takes three Point objects as its vertices and calculates the area using the determinant formula. The isPointInsideTriangle() method then checks if the fourth point (represented as another Triangle object) lies inside the original triangle.

class Triangle {  
    private Point pointA;  
    private Point pointB;  
    private Point pointC;  
  
    public Triangle(Point point1, Point point2, Point point3) {  
        this.pointA = point1;  
        this.pointB = point2;  
        this.pointC = point3;  
    }  
  
    public float getArea() {  
        return Math.abs((pointA.X * (pointB.Y-> pointC.Y) + pointB.X  
                * (pointC.Y-> pointA.Y) + pointC.X * (pointA.Y-> pointB.Y))  
                / (float) 2.0);  
    }  
  
}  


 public static boolean isPointInsideTriangle(Triangle triangle1,  
        Triangle triangle2, Triangle triangle3, Triangle triangle4) {  
        float area = triangle2.getArea() + triangle3.getArea()  
                + triangle4.getArea();  
        if (triangle1.getArea() == area) {  
            return true;  
        } else {  
            return false;  
        }  
    }  

Unit Tests

To ensure the correctness of our implementation, we will create unit tests that cover various scenarios, including points inside and outside the triangle. The unit tests will validate the accuracy and reliability of our algorithm.

Here is the unit test for this program which can also run to play with it:

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

public class TriangleTest {

    @Test
    public void testPointInsideTriangle() {
        Point A = new Point(0, 0);
        Point B = new Point(4, 0);
        Point C = new Point(2, 3);
        Triangle triangle1 = new Triangle(A, B, C);

        // Point (2, 1) lies inside the triangle (A, B, C)
        Point P1 = new Point(2, 1);
        assertTrue(isPointInsideTriangle(triangle1, new Triangle(A, B, P1),
                new Triangle(B, C, P1), new Triangle(C, A, P1)));

        // Point (3, 2) lies inside the triangle (A, B, C)
        Point P2 = new Point(3, 2);
        assertTrue(isPointInsideTriangle(triangle1, new Triangle(A, B, P2),
                new Triangle(B, C, P2), new Triangle(C, A, P2)));
    }

    @Test
    public void testPointOutsideTriangle() {
        Point A = new Point(0, 0);
        Point B = new Point(4, 0);
        Point C = new Point(2, 3);
        Triangle triangle1 = new Triangle(A, B, C);

        // Point (1, 1) lies outside the triangle (A, B, C)
        Point P1 = new Point(1, 1);
        assertFalse(isPointInsideTriangle(triangle1, new Triangle(A, B, P1),
                new Triangle(B, C, P1), new Triangle(C, A, P1)));

        // Point (5, 3) lies outside the triangle (A, B, C)
        Point P2 = new Point(5, 3);
        assertFalse(isPointInsideTriangle(triangle1, new Triangle(A, B, P2),
                new Triangle(B, C, P2), new Triangle(C, A, P2)));
    }
}

That's all about how to check if a given point is inside a triangle or not in Java. Understanding the mathematical concepts behind checking if a given point lies inside a triangle makes it easier to code the algorithm in Java and we have created an efficient and reliable solution. Utilizing the Barycentric Coordinate System and calculating triangle areas, we can accurately determine if a point resides within a triangle or not. 

With the aid of comprehensive unit tests, we have validated the correctness of our implementation across various scenarios. This technique is a valuable addition to a Java developer's toolkit for computational geometry problems and can find applications in a wide range of fields, from computer graphics to robotics and beyond.

Other coding interview questions you may like

• How to Print duplicate characters from String? (solution)
• How to return the highest occurred character in a String? (solution)
• How to program to print the first non-repeated character from String? (solution)
• How to reverse words in a sentence without using a library method? (solution)
• How to check if a string contains only digits?  (solution)
• How to find all permutations of String? (solution)
• How to count the number of vowels and consonants in a String? (solution)
• How to convert a numeric string to an int? (solution)
• How to count the occurrence of a given character in String? (solution)
• 10 Algorithms Courses to Crack Programming Job Interviews (courses)
• How to find duplicate characters in a String? (solution)
• How to check if String is Palindrome? (solution)
• How to reverse String in Java using Iteration and Recursion? (solution)
• How to reverse a String in place in Java? (solution)
• How to check if two Strings are anagrams of each other? (solution)
• 50+ Data Structure and Algorithms Interview Questions (questions)