## Saturday, January 23, 2016

### Count Integral points inside a Triangle - GeeksforGeeks

Count Integral points inside a Triangle - GeeksforGeeks
Given three non-collinear integral points in XY plane, find the number of integral points inside the triangle formed by the three points. (A point in XY plane is said to be integral/lattice point if both its co-ordinates are integral).
```Input: p = (0, 0), q = (0, 5) and r = (5,0)

Output: 6

Explanation: The points (1,1) (1,2) (1,3) (2,1)
(2,2) and (3,1) are the integral
points inside the triangle.

```
We can use the Pick’s theorem, which states that the following equation holds true for a simple Polygon.
```Pick's Theeorem:
A = I + (B/2) -1

A ==> Area of Polygon
B ==> Number of integral points on edges of polygon
I ==> Number of integral points inside the polygon

Using the above formula, we can deduce,
I = (2A - B + 2) / 2 ```
We can find A (area of triangle) using below Shoelace formula.
`A =  1/2 * abs(x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)) `
How to find B (number of integral points on edges of a triangle)?
We can find the number of integral points between any two vertex (V1, V2) of the triangle using the following algorithm.
```1. If the edge formed by joining V1 and V2 is parallel
to the X-axis, then the number of integral points
between the vertices is :
abs(V1.y - V2.y)-1

2. Similarly if edge is parallel to the Y-axis, then
the number of integral points in between is :
abs(V1.x - V2.y)-1

3. Else, we can find the integral points between the
vertices using below formula:
GCD(abs(V1.x-V2.x), abs(V1.y-V2.y)) - 1
The above formula is a well known fact and can be
verified using simple geometry. (Hint: Shift the
edge such that one of the vertex lies at the Origin.) ```
Below is C++ implementation of the above algorithm.
 `// C++ program to find Integral points inside a triangle` `#include` `using` `namespace` `std;`   `// Class to represent an Integral point on XY plane.` `class` `Point` `{` `public``:` `    ``int` `x, y;` `    ``Point(``int` `a=0, ``int` `b=0):x(a),y(b) {}` `};`   `//utility function to find GCD of two numbers` `// GCD of a and b` `int` `gcd(``int` `a, ``int` `b)` `{` `    ``if` `(b == 0)` `       ``return` `a;` `    ``return` `gcd(b, a%b);` `}`   `// Finds the no. of Integral points between` `// two given points.` `int` `getBoundaryCount(Point p,Point q)` `{` `    ``// Check if line parallel to axes` `    ``if` `(p.x==q.x)` `        ``return` `abs``(p.y - q.y) - 1;` `    ``if` `(p.y == q.y)` `        ``return` `abs``(p.x-q.x) - 1;`   `    ``return` `gcd(``abs``(p.x-q.x),``abs``(p.y-q.y))-1;` `}`   `// Returns count of points inside the triangle` `int` `getInternalCount(Point p, Point q, Point r)` `{` `    ``// 3 extra integer points for the vertices` `    ``int` `BoundaryPoints = getBoundaryCount(p, q) +` `                         ``getBoundaryCount(p, r) +` `                         ``getBoundaryCount(q, r) + 3;`   `    ``// Calculate 2*A for the triangle` `    ``int` `doubleArea = ``abs``(p.x*(q.y - r.y) + q.x*(r.y - p.y)  +` `                         ``r.x*(p.y - q.y));`   `    ``// Use Pick's theorem to calculate the no. of Interior points` `    ``return` `(doubleArea - BoundaryPoints + 2)/2;` `}`