Triangle from a given rectangle

Question

We are given a set of (marked) points in a 2D coordinate system and function $f(x,y)$ which counts number of points marked in the rectangle $(0 , 0), (x , y)$ - where $(0 , 0)$ if down-left corner, $(x , y)$ is up-right corner and sides are parallel to $x$-axis and $y$-axis.

How could we determine the number of points marked inside or on the boundary of the triangle with coordinates $(x_1,y_1),(x_2,y_2)$ and $(x_3,y_3)$?

For example if the given set of points is $\{(1,5),(1,3),(3,6),(4,4),(2,6)\}$, then there are exactly $3$ marked point inside or boundary of the triangle $\{(4,5),(1,5),(1,8)\}$, exactly $3$ marked point inside or boundary of the triangle $\{(5,5),(1,5),(1,9)\}$ and $0$ marked point inside or boundary of the triangle $\{(2,1),(1,1),(1,2)\}$.

I am aware of the approaches like these. However, I am more interested in solving this with the help of the function $f(x,y)$.

PS: For this particular problem we can also assume that everything is from the set of natural numbers.

Answer 1

Assuming a finite set of points, and allowing their coordinates to range over $\mathbb R$, let $g(x_1,y_1,x_2,y_2)=f(x_2,y_2)-f(x_2,y_1)-f(x_1,y_2)+f(x_1,y_1)$. This function counts the number of points in the rectangle $x_1<x\le x_2$, $y_1<y\le y_2$.

First draw a box around the triangle. The number of points in the triangle is equal to the number of points in the rectangle minus the number of points in each of the grey areas. Note that we can always subdivide the grey areas into rectangles (D) and right angled triangles (A,B,C)

$$ $$ Finding the number of points in a rectangle is easy, just use our function $g$. To find the number of points in a right angled triangle we will have to keep subdividing. Looking at the bottom picture and searching for the number of points in the white triangle we cut it into four pieces. Points in E are not in the right angled triangle, and points in H are. We are then left with two more smaller right angled triangles F & G which we can divide again repeatedly. Assuming there are only finitely many points we will hopefully reach a situation where both F & G are empty and thus no further subdivisions are necessary.

However, points lying near the diagonal line might require a very large number of iterations before discovering which side they are on, and those lying exactly on the boundary may cause us to never terminate the subdivision. I'm not sure of any way to avoid this problem if the only information on point locations is using the function $f$.