This code uses a Point type that contains X/Y as integers similar to System.Drawing.Point. This class is used to calculate vertical scan lines for a polygon. It has been tested with 3 points but beyond that I am unsure if it will work.
using System;
/// <summary>
/// Helper class used to calculate scan lines of a triangle
/// </summary>
public class TriangleScanLineCalculator
{
/// <summary>
/// Provides a high low type for storing min & max values for scan lines.
/// </summary>
public struct HiLoTYPE
{
public int High;
public int Low;
}
/// <summary>
/// Holds scan line information.
/// </summary>
protected internal HiLoTYPE[] scanLines;
/// <summary>
/// Holds the calculated scan line count.
/// </summary>
protected internal int scanLineCount;
/// <summary>
/// Gets the right most side of the triangle.
/// </summary>
public int MaximumX { get; private set; }
/// <summary>
/// Gets the left most side of the triangle.
/// </summary>
public int MinimumX { get; private set; }
/// <summary>
/// Gets the number of scan lines.
/// </summary>
public int Count
{
get { return scanLineCount; }
}
/// <summary>
/// Calculates the min & max y values for each scan line.
/// </summary>
/// <param name="points">The points that make up the triangle</param>
public void Calculate(Point[] points)
{
var xMax = 0;
var xMin = 0;
float XDelta = 0;
float YDelta = 0;
// X/Y distance between 2 vertexes
float YPos = 0;
float YSlope = 0;
var VertIndex1 = 0;
var VertIndex2 = 0;
var tempIndex = 0;
// Step 1: Find the min and max 'X' dimensions of the polygon
xMax = int.MinValue;
xMin = int.MaxValue;
for (var i = 0; i <= points.Length - 1; i++)
{
if (xMax < points[i].X)
{
xMax = points[i].X;
}
if (xMin > points[i].X)
{
xMin = points[i].X;
}
}
this.MinimumX = xMin;
this.MaximumX = xMax;
this.scanLineCount = xMax - xMin;
// Step 2: Resize scan line array to hold all the high and low x values
if (this.scanLines == null || this.scanLines.Length < xMax - xMin)
{
// allocate
Array.Resize(ref this.scanLines, (xMax - xMin) + 100);
}
// Step3: Set the height value of all scan lines to there min or max value(s)
for (var i = 0; i <= this.scanLines.Length - 1; i++)
{
this.scanLines[i].High = int.MinValue;
this.scanLines[i].Low = int.MaxValue;
}
// Step 4: Set up the Y highs and lows for each X scan line between the min X and Max X points
for (var i = 0; i < points.Length; i++)
{
// Step4a: Determine witch sides of the polygon we will be setting up
VertIndex1 = i;
VertIndex2 = i + 1;
if (VertIndex2 == points.Length) VertIndex2 = 0;
// Step4b: check if the first vertex if farther right then the second vertex
// and if so swap vertex indexes
if (points[VertIndex1].X > points[VertIndex2].X)
{
tempIndex = VertIndex1;
VertIndex1 = VertIndex2;
VertIndex2 = tempIndex;
}
// Step4c: Find the X/Y dist between vert1 and vert2
XDelta = points[VertIndex2].X - points[VertIndex1].X;
YDelta = points[VertIndex2].Y - points[VertIndex1].Y;
// Step4d: Determine the Y slope to use.
// YSlope determines how much to move down for every move we make to the right
if (XDelta != 0)
{
YSlope = YDelta / XDelta;
}
else
{
YSlope = 0;
}
// Save the starting y position in YPos
YPos = points[VertIndex1].Y;
// Step4e: Process all of scan lines between vert1 and vert2
for (var idy = points[VertIndex1].X; idy < points[VertIndex2].X; idy++)
{
// If the scan lines higher value has already been set then set the lower value
// we use the formula 'idy - XMin' to determine what index into the scan line
// array to use. (ScanLineIndex = AnyPositionBetweenVert1AndVert2 - LeftMostPartOfPoly)
// Store the scan line index in the TmpIndex variable so we don't
// have the overhead of doing 5 subtractions
tempIndex = idy - xMin;
var item = this.scanLines[tempIndex];
// Check if Scan(TmpIndex).High has been set already
if (item.High == int.MinValue)
{
// High has not been set yet
item.High = (int)YPos;
}
else
{
// High has been set yet so we set the low point
item.Low = (int)YPos;
// Ensure that the High is actually a higher value then low
if (item.High < item.Low)
{
var tempValue = item.High;
item.High = item.Low;
item.Low = tempValue;
}
}
this.scanLines[tempIndex] = item;
// update the Y position
YPos += YSlope;
}
}
}
/// <summary>
/// Retrieves a scan line.
/// </summary>
/// <param name="index">The index of the scan line.</param>
/// <returns>Returns information about the scan line.</returns>
public HiLoTYPE ScanLine(int index)
{
return this.scanLines[index];
}
/// <summary>
/// Gets all the scan lines.
/// </summary>
/// <returns>Returns all the scan line information.</returns>
public HiLoTYPE[] GetScanLines()
{
// if there are no scan lines return null.
if (this.scanLineCount == 0)
{
return null;
}
// resize the array
Array.Resize(ref this.scanLines, this.scanLineCount);
return this.scanLines;
}
/// <summary>
/// Calculates the scan lines for a triangle.
/// </summary>
/// <param name="points">The triangle points.</param>
/// <param name="minXValue">Will return the minimum x value that the triangle starts at.</param>
/// <returns>Returns the min max y values of the scanline.</returns>
public static HiLoTYPE[] Calculate(Point[] points, out int minXValue)
{
// create scan line calculator and get values from it
var scanner = new TriangleScanLineCalculator();
scanner.Calculate(points);
var items = scanner.GetScanLines();
minXValue = scanner.MinimumX;
return items;
}
}