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.
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: