Question: Let's say I have a triangle given by the three integer vertices (x1,y1), (x2,y2) and (x3,y3). What sort of algorithm can I use to return a comprehensive list of ALL (x,y) integer pairs that lie inside the triangle.

Answer: 
The following algorithm should be appropriate:

1. Sort the triangle vertices by x coordinate in increasing order. Now we have two segments (1-2 and 2-3) on the one side (top or bottom), and one segment from the other one (1-3).
2. Compute coefficients of equations of lines (which contain the segments):

```
A * x + B * y + C = 0
A = y2 - y1
B = x1 - x2
C = x2 * y1 - x1 * y2

```

There (x1, y1) and (x2, y2) are two points of the line.
3. For each of ranges [x1, x2), (x2, x3], and x2 (special case) iterate over integer points in ranges and do the following for every x:

	1. Find top bound as y\_top = (- A1 \* x - C1) div B1.
	2. Find bottom bound as y\_bottom = (- A2 \* y - C2 - 1) div B2 + 1.
	3. Add all points between (x, y\_bottom) and (x, y\_top) to the result.

This algorithm is for not strictly internal vertices. For strictly internal vertices items 3.1 and 3.2 slightly differ.
The proper name for this problem is triangle [rasterization](http://en.wikipedia.org/wiki/Rasterisation).

It's a well researched problem and there's variety of methods to do it. The two popular methods are:

1. Scan line by scan line. 

For each scan-line you require some basic geometry to recalculate
the start and the end of the line. See [Bresenham's Line drawing algorithm](http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm).
2. Test every pixel in the bounding box to see if it is in the
triangle.

This is usually done by using [barycentric](http://en.wikipedia.org/wiki/Barycentric_coordinate_system_%28mathematics%29#Barycentric_coordinates_on_triangles) co-ordinates.

Most people assume method 1) is more efficient as you don't waste time testing pixels that can are outside the triangle, approximately half of all the pixels in the bounding box. However, 2) has a major advantage - it can be run in parallel far more easily and so for hardware is usually the much faster option. 2) is also simpler to code.

The original [paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.157.4621&rep=rep1&type=pdf) for describing exactly how to use method 2) is written by Juan Pineda in 1988 and is called "A Parallel Algorithm for Polygon Rasterization".

For triangles, it's conceptually very simple (if you learn barycentric co-ordindates). If you convert each pixel into triangle barycentric coordinates, alpha, beta and gamma - then the simple test is that alpha, beta and gamma must be between 0 and 1.