# Triangle from a given rectangle

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.

-
Does $f$ include marked points on the boundary of the rectangle? – Blue Feb 9 '13 at 6:28
@Blue:Yes.$\space$ – Ryan Earlington Feb 9 '13 at 6:44
Taking $x$ and $y$ positive ... Define $g(x,y) := f(x,y) - f(x-1,y) - f(x,y-1) + f(x-1,y-1)$. Then $g(x,y) = 1$ when point $(x,y)$ itself is marked, and $g(x,y) = 0$ otherwise. Then sum $g$ over the points in the triangle ... which is probably easier said (or typed) than done. Hmmm ... – Blue Feb 9 '13 at 6:59
This is only solvable due to the assumption that "everything is from the set of natural numbers" (I suppose this applies to coordinates; distances and areas are of course are likely to not be natural numbers). Then your "triangles" are just finite sets of points in a grid, you can cover them by rectangles and add up. With non-integral coordinates you can never cover a triangle with a finite set of rectangles without also covering points outside the triangle. – Marc van Leeuwen Aug 16 '13 at 10:07

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