How do I find all integral points inside a triangle efficiently

Question

Given triangle vertices co-ordinates ($x$ , $y$) ( ranges from $0$ to $10^{9}$).How do I find all integer points inside this triangle efficiently? because if I use scan-line it can take much time.

as shown in image we need to get all blue points.(vertices are also integers in given range) and have to find all such points, if answer is greater than 100 then return any such 100 points

Answer 1

One other idea besides scan-line:

1. Find a single point inside the triangle, e.g. check the neighbors of the vertices.
2. Use flood fill or somthing like this together with a fast triangle-point-test to find sufficiently many other points.

I still think a well-implemented scan-line algorithm would be faster because it does not have to apply the point-test for every point, but only has to find the start and end of a scan-line. This can be done fast if you translate the triangle into a half-space representation, i.e. a point is an inner point if it satisfies

$$a_ix +b_iy <1,\quad i=1,2,3$$

for appropriate $a_i,b_i,i=1,2,3$ which you need to compute only once.