Java Program to Count Integral Points Inside a Triangle

In the previous article, we have discussed about Java Program to Find Type of Triangle from Given Coordinates

In this article we are going to see how to count integral points inside a triangle by using Java programming language.

Java Program to Count Integral Points Inside a Triangle

Before Jumping into the program directly let’s see how to count integral points inside a Triangle.

Suppose the 3 coordinates of a triangle are given as Q(x1,y1), R(x2,y2) P(x3,y3)

Now we need to find the number of integral points inside the triangle

Using Pick’s Theorem:

A = I +(B/2) -1

I = A -(B/2) +1

A is Area of triangle

B is Number of integral points on edges of triangle ,I is Number of integral points inside the triangle

Using the above formula, we can deduce,

I = (2A – B + 2) / 2

A =  1/2 * abs(x1(y2 – y3) + x2(y3 – y1) + x3(y1 – y2))

B = GCD(abs(V1.x-V2.x), abs(V1.y-V2.y)) – 1

Where V1 and V2 are any 2 vertices of the triangle I.e P, Q, R

Example:

P(0,0);
Q(25,0);
R(0,20)
Area = 1/2 * abs(x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)) = 250
B = 50
I = A -(B/2) +1 = 226

Let’s see different ways to count integral points inside a triangle.

• By Using Static Input Value
• By Using User Input Value

Method-1: Java Program to Count Integral Points Inside a Triangle By Using Static Input Value

Approach:

• Declare an int variable say ‘x1’ and assign the value to it, which holds the x coordinate of point Q
• Declare an int variable say ‘y1’ and assign the value to it, which holds the y coordinate of point Q
• Declare an int variable say ‘x2’ and assign the value to it, which holds the x coordinate of point R
• Declare an int variable say ‘y2’ and assign the value to it, which holds the y coordinate of point R
• Declare an int variable say ‘x3’ and assign the value to it, which holds the x coordinate of point P
• Declare an int variable say ‘y3’ and assign the value to it, which holds the y coordinate of point P
• Find the interior point of the triangle using the formula A -(B/2) +1
• Print the result.

Program:

public class Main 
{
    public static void main(String [] args)
    {
         Point p = new Point(0, 0);
         Point q = new Point(25, 0);
         Point r = new Point(0, 20);
        int x = interiorPoint(p, q, r);
        System.out.println("Number of total interior integral points " + x );
    }
    static int interiorPoint(Point p, Point q, Point r)
     {
        // total boundary points of 3 sides + 3 extra integral points for the vertices of triangle
        int BoundaryPoints = boundaryPoint(p, q) + boundaryPoint(p, r) + boundaryPoint(q, r) + 3;
        // Calculate 2 times of area of the triangle
        int Area = Math.abs(p.x * (q.y - r.y) + q.x * (r.y - p.y) + r.x * (p.y - q.y));
         // Using Pick's theorem to calculate the no. of total Interior points
        int i = (Area - BoundaryPoints + 2) / 2;
        return i;
    }
     // Finds the no. of boundary integral points between 2 given points.
    static int boundaryPoint(Point p, Point q)
    {
        // Check if line parallel to x-axes
        if (p.x == q.x)
        return Math.abs(p.y - q.y) - 1;
        // Check if line parallel to x-axes
        if (p.y == q.y)
        return Math.abs(p.x - q.x) - 1;
        int gcd = gcd(Math.abs(p.x - q.x),Math.abs(p.y - q.y)) - 1;
        return gcd;
    }
    // GCD of 2 numbers
    static int gcd(int p, int q)
    {
    	int gcd = 1;
    	for (int i = 1; i<=p && i<=q; i++)
    	{
    		if(p%i==0 && q%i==0)
    		gcd = i;
    	}
    	return gcd;
    }
}
class Point
{
    int x, y;
    public Point(int a, int b)
    {
        x = a;
        y = b;
    }
} 

Output:

Number of total interior integral points 226

Method-2: Java Program to Count Integral Points Inside a Triangle By Using User Input Value

Approach:

• Declare an int variable say ‘x1’ which holds the x coordinate of point Q
• Declare an int variable say ‘y1’ which holds the y coordinate of point Q
• Declare an int variable say ‘x2’ which holds the x coordinate of point R
• Declare an int variable say ‘y2’ which holds the y coordinate of point R
• Declare an int variable say ‘x3’ which holds the x coordinate of point P
• Declare an int variable say ‘y3’ which holds the y coordinate of point P
• Then we will take the value of “x1”, “y1”, “x2”, “y2”, “x3”, “y3” as user input using scanner class.
• Find the interior point of the triangle using the formula A -(B/2) +1
• Print the result.

Program:

import java.util.Scanner;
public class Main 
{
    public static void main(String [] args)
    {
       // Create a Scanner object
       Scanner s = new Scanner(System.in);
        System.out.println("Enter the x coordinate of 1st point Q");
        // Read user input
        int x1 = s.nextInt();
        System.out.println("Enter the y coordinate of 1st point Q");
        int y1 = s.nextInt();
        System.out.println("Enter the x coordinate of 2nd point R");
        int x2 = s.nextInt();
        System.out.println("Enter the y coordinate of 2nd point R");
        int y2 = s.nextInt();
        System.out.println("Enter the x coordinate of 3rd point P");
        int x3 = s.nextInt();
        System.out.println("Enter the y coordinate of 3rd point P");
        int y3 = s.nextInt();
        Point p = new Point(x1,y1);
        Point q = new Point(x2,y2);
        Point r = new Point(x3,y3);	  
         int x = interiorPoint(p, q, r);
        System.out.println("Number of total interior integral points " + x );
    }
    static int interiorPoint(Point p, Point q, Point r)
    {
        // total boundary points of 3 sides + 3 extra integral points for the vertices of triangle
        int BoundaryPoints = boundaryPoint(p, q) + boundaryPoint(p, r) + boundaryPoint(q, r) + 3;
        // Calculate 2 times of area of the triangle
        int Area = Math.abs(p.x * (q.y - r.y) + q.x * (r.y - p.y) + r.x * (p.y - q.y));
        // Using Pick's theorem to calculate the no. of total Interior points
        int i = (Area - BoundaryPoints + 2) / 2;
        return i;
    }
    // Finds the no. of boundary integral points between 2 given points.
    static int boundaryPoint(Point p, Point q)
    {
        // Check if line parallel to x-axes
        if (p.x == q.x)
        return Math.abs(p.y - q.y) - 1;
        // Check if line parallel to x-axes
        if (p.y == q.y)
        return Math.abs(p.x - q.x) - 1;
        int gcd = gcd(Math.abs(p.x - q.x),Math.abs(p.y - q.y)) - 1;
        return gcd;
    }
    // GCD of 2 numbers
    static int gcd(int p, int q)
    {
    	int gcd = 1;
    	for (int i = 1; i<=p && i<=q; i++)
    	{
    		if(p%i==0 && q%i==0)
    		gcd = i;
    	}
    	return gcd;
    }
}
class Point
{
    int x, y;
    public Point(int a, int b)
    {
        x = a;
        y = b;
    }
} 

Output:

Enter the x coordinate of 1st point Q
0
Enter the y coordinate of 1st point Q
0
Enter the x coordinate of 2nd point R
15
Enter the y coordinate of 2nd point R
0
Enter the x coordinate of 3rd point P
0
Enter the y coordinate of 3rd point P
30
Number of total interior integral points 196

Don’t miss the chance of Java programs examples with output pdf free download as it is very essential for all beginners to experienced programmers for cracking the interviews.

Related Java Programs:

• Java Program to Check Orientation of 3 Ordered Points
• Java Program to Find Centroid of a Triangle
• Java Program to Find Number of Angles in N Sided Convex Polygon
• Java Program to Check if Two Convex Regular Polygon Have Same Center or Not