Skip to content

Instantly share code, notes, and snippets.

@michaelbartnett
Last active December 11, 2015 06:28
Show Gist options
  • Save michaelbartnett/4559662 to your computer and use it in GitHub Desktop.
Save michaelbartnett/4559662 to your computer and use it in GitHub Desktop.
Value type enumerable line plotter
/// <summary>
/// Struct representing a 2D integral point.
/// Has GetHashCode and Equals methods, so you can use this in a
/// dictionary for sparse coordinate maps and other collections.
///
/// Supports addition and subtraction.
///
/// Point p0 = new Point(3, 4);
/// Point p1 = new Point(-5, 6);
/// Point p3 = p1 - p0; // => [-8, 2]
/// Point p4 = p3 + p1; // => [5, 8]
///
///
/// Supports scalar multiplication and division by either int,
/// long, float or double.
///
/// Point p0 = new Point(2, 3);
/// Point p1 = p0 * 4; // => [8, 12]
/// Point p2 = p1 * 0.5f; // => [4, 6]
///
///
/// Supports reading by element index.
///
/// Point p0 = new Point(2, 3);
/// Print(p0[1]); // Prints "3"
///
///
/// Has convenient constants:
///
/// Point.Zero => [0, 0]
/// Point.Unit => [1, 1]
/// Point.UnitX => [1, 0]
/// Point.UnitY => [0, 1]
///
/// </summary>
public struct Point
{
public static readonly Point Zero = new Point(0, 0);
public static readonly Point Unit = new Point(1, 1);
public static readonly Point UnitX = new Point(1, 0);
public static readonly Point UnitY = new Point(0, 1);
public int x, y;
public int this[int index] {
get {
switch (index) {
case Dimension.First: return this.x;
case Dimension.Second: return this.y;
default: throw new ArgumentException("Index must be 0 or 1, you passed " + index);
}
}
set {
switch (index) {
case Dimension.First: this.x = value; break;
case Dimension.Second: this.y = value; break;
default: throw new ArgumentException("Index must be 0 or 1, you passed " + index);
}
}
}
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
public static Point operator+(Point a, Point b)
{
return new Point(a.x + b.x, a.y + b.y);
}
public static Point operator-(Point a, Point b)
{
return new Point(a.x - b.x, a.y - b.y);
}
public static Point operator*(Point p, int n)
{
return new Point(p.x * n, p.y * n);
}
public static Point operator*(Point p, long n)
{
return new Point((int)(p.x * n), (int)(p.y * n));
}
public static Point operator*(Point p, float n)
{
return new Point((int)(p.x * n), (int)(p.y * n));
}
public static Point operator*(Point p, double n)
{
return new Point((int)(p.x * n), (int)(p.y * n));
}
public static Point operator/(Point p, int n)
{
return new Point(p.x / n, p.y / n);
}
public static Point operator/(Point p, long n)
{
return new Point((int)(p.x / n), (int)(p.y / n));
}
public static Point operator/(Point p, float n)
{
return new Point((int)(p.x / n), (int)(p.y / n));
}
public static Point operator/(Point p, double n)
{
return new Point((int)(p.x / n), (int)(p.y / n));
}
public override string ToString()
{
return string.Format("Point({0}, {1})", x, y);
}
public override int GetHashCode()
{
int hash = 17;
hash = hash * 23 + x.GetHashCode();
hash = hash * 23 + x.GetHashCode();
return hash;
}
public override bool Equals(object o)
{
if (o.GetType() != typeof(Point)) {
return false;
}
var other = (Point) o;
return this == other;
}
public static bool operator==(Point a, Point b)
{
return a.x.Equals(b.x) &&
a.y.Equals(b.y);
}
public static bool operator!=(Point a, Point b)
{
return !(a == b);
}
}
/// <summary>
/// A nominally enumerable struct that will generate discrete points on a 2D line
/// between two points supplied to LinePoint.Plot. For specifying the endpoints
/// of the line it relies on a Point struct with int fields named "x" and "y".
///
/// A LinePoint implements both the IEnumerable<LinePoint> and the IEnumerator<LinePoint>
/// protocol. It does not explicitly implement this interface in the class definition,
/// but the C# compiler is able to detect that this is able to be iterated with a foreach
/// loop regardless sot that it does not generate any unnecessar garbage.
/// (see Eric Lippert's post, http://stackoverflow.com/a/5488242/136475).
///
/// Uses the Bresenham line algorithm: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
///
/// Example:
///
/// var diagLineStart = new Point(0, 12);
/// var diagLineEnd = new Point(10, 4);
///
/// foreach (PointLine p in PointLine.Plot(diagLineStart, diagLineEnd)) {
/// Debug.Log(string.Format("Point: {0}, {1}", p.X, p.Y));
/// }
///
/// </summary>
public struct PointLine
{
public int X { get; private set; }
public int Y { get; private set; }
/// <summary>
/// Function to initiate iteration over a discrete 2D line between
/// two specified integer endpoints.
///
/// Example:
///
/// foreach (PointLine p in PointLine.Plot(new Point(0, 0, new Point(7, 9))) {
/// Debug.Log(string.Format("Point: {0}, {1}", p.X, p.Y));
/// }
///
/// </summary>
public static PointLine Plot(Point p0, Point p1)
{
return new PointLine(p0, p1);
}
public PointLine Current { get { return this; } }
private Point p0;
private Point p1;
private int deltaX;
private int deltaY;
private int stepX;
private int stepY;
private int error;
private int nextX;
private int nextY;
private PointLine(Point p0, Point p1)
{
this.p0 = p0;
this.p1 = p1;
this.deltaX = Math.Abs(p1.x - p0.x);
this.deltaY = Math.Abs(p1.y - p0.y);
this.stepX = p0.x < p1.x ? 1 : -1;
this.stepY = p0.y < p1.y ? 1 : -1;
this.error = deltaX - deltaY;
this.X = default(int);
this.Y = default(int);
this.nextX = p0.x;
this.nextY = p0.y;
}
public bool MoveNext()
{
this.X = nextX;
this.Y = nextY;
int twoErr = error * 2;
if (twoErr > -deltaY) {
error -= deltaY;
nextX += stepX;
}
if (twoErr < deltaX) {
error += deltaX;
nextY += stepY;
}
return (this.X != p1.x || this.Y != p1.y);
}
public PointLine GetEnumerator()
{
var newOne = this;
newOne.nextX = newOne.p0.x;
newOne.nextY = newOne.p0.y;
newOne.error = newOne.deltaX - newOne.deltaY;
return newOne;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment