How about maintaining a range of columns for each row that are in the triangle? What you can do is set the min and max column for each row where each point is, and where each triangle line crosses a horizontal row separator line.
public class Point
{
public float X;
public float Y;
public Point(float x, float y) { this.X = x; this.Y = y; }
}
public class Line
{
float ROW_SIZE = 100f;
float COL_SIZE = 100f;
public Point P1, P2; // P1 has the lowest Y
public float Slope, Intercept; // set in constructor
public bool IsVertical;
public Line(Point p1, Point p2)
{
if (p1.Y > p2.Y) { P1 = p2; P2 = p1; } // p1 has lowest Y
else { P1 = p1; P2 = p2; }
IsVertical = (p1.X == p2.X);
if (!IsVertical) { Slope = (p2.Y - p1.Y) / (p2.X - p1.X); Intercept = p1.Y - Slope * p1.X; }
}
public void ExpandRanges(int[] minCol, int[] maxCol)
{
// start out at row, col where P1 is, which has lowest Y
int row = (int)(P1.Y / ROW_SIZE);
int col = (int)(P1.X / COL_SIZE);
int lastRow = (int)(P2.Y / ROW_SIZE);
int lastCol = (int)(P2.X / COL_SIZE);
// expand row to include P1
minCol[row] = Math.Min(col, minCol[row]); maxCol[row] = Math.Max(col, maxCol[row]);
// now we find where our line intercepts each horizontal line up to P2
float currY = P1.Y;
float currX = P1.X;
while (row < lastRow)
{
row = row + 1;
float rowY = row * ROW_SIZE;
float diffY = rowY - currY;
float diffX = IsVertical ? 0f : diffY / Slope;
currY = currY + diffY;
currX = currX + diffX;
col = (int)(currX / COL_SIZE);
// expand rows above and below dividing line to include point
minCol[row - 1] = Math.Min(col, minCol[row - 1]);
maxCol[row - 1] = Math.Max(col, maxCol[row - 1]);
minCol[row] = Math.Min(col, minCol[row]);
maxCol[row] = Math.Max(col, maxCol[row]);
}
// expand last row to include P2
minCol[lastRow] = Math.Min(lastCol, minCol[lastRow]);
maxCol[lastRow] = Math.Max(lastCol, maxCol[lastRow]);
}
public static void Test()
{
Point p1 = new Point(160, 250);
Point p2 = new Point(340, 250);
Point p3 = new Point(250, 40);
Line l1 = new Line(p1, p2);
Line l2 = new Line(p2, p3);
Line l3 = new Line(p3, p1);
Line[] lines = { l1, l2, l3 };
int rowCount = 4;
int[] minCol = new int[rowCount];
int[] maxCol = new int[rowCount];
for (int i = 0; i < rowCount; i++)
{
minCol[i] = int.MaxValue;
maxCol[i] = int.MinValue;
}
for (int i = 0; i < lines.Length; i++)
lines[i].ExpandRanges(minCol, maxCol);
for (int i = 0; i < rowCount; i++)
Console.WriteLine("Row {0}: {1} - {2}", i, minCol[i], maxCol[i]);
}
}
Output:
Row 0: 2 - 2
Row 1: 1 - 3
Row 2: 1 - 3
Row 3: 2147483647 - -2147483648