Add simple 2d geometry library.

Its point is to allow intersecting rays with grid lines and
advancing rays from one cell to the next.

1 files changed, 84 insertions, 0 deletions

diff --git a/crawl-ref/source/geom2d.h b/crawl-ref/source/geom2d.h
new file mode 100644
index 0000000000..d65ea06842
--- /dev/null
+++ b/crawl-ref/source/geom2d.h
@@ -0,0 +1,84 @@
+#ifndef GEOM2D_H
+#define GEOM2D_H
+
+namespace geom {
+
+struct vector
+{
+    double x;
+    double y;
+
+    vector(double _x = 0.0, double _y = 0.0)
+        : x(_x), y(_y) {}
+
+    const vector& operator+=(const vector &v);
+    vector operator+(const vector &v) const;
+    const vector& operator*=(double t);
+    vector operator*(double t) const;
+};
+
+struct form
+{
+    double a;
+    double b;
+
+    form(double _a = 0.0, double _b = 0.0)
+        : a(_a), b(_b) {}
+
+    double operator()(const vector &v) const;
+};
+
+// A ray in two-dimensional space given by starting point
+// and direction vector.
+// The points of R are start + t*dir.
+struct ray
+{
+    vector start;
+    vector dir;
+
+    ray() {}
+    ray(double x0, double y0, double xd, double yd)
+        : start(x0, y0), dir(xd, yd) {}
+
+    vector shoot(double t) const;
+    void advance(double t);
+};
+
+// A line in two-dimensional space as the preimage of a number
+// under a linear form. L = form^{-1}(val).
+struct line
+{
+    form f;
+    double val;
+};
+
+// A sequence of evenly spaced parallel lines, like the
+// horizontal or vertical lines in a grid.
+// Lines are f^{-1}(offset + k*dist) for integers k.
+struct lineseq
+{
+    form f;
+    double offset;
+    double dist;
+
+    lineseq() {}
+    lineseq(double a, double b, double o, double d)
+        : f(a,b), offset(o), dist(d) {}
+};
+
+struct grid
+{
+    lineseq ls1;
+    lineseq ls2;
+
+    grid(lineseq l1, lineseq l2) : ls1(l1), ls2(l2) {}
+};
+
+double intersect(const ray &r, const line &l);
+double nextintersect(const ray &r, const lineseq &ls);
+bool nextcell(ray &r, const grid &g, bool pass_corner);
+
+}
+
+#endif
+