d2d.sdl2.Polygon source code

1 /**
2  * Polygon
3  */
4 module d2d.sdl2.Polygon;
5 
6 import std.algorithm;
7 import std.array;
8 import std.parallelism;
9 import std.range;
10 import std.traits;
11 import d2d.math.AxisAlignedBoundingBox;
12 import d2d.math.Segment;
13 import d2d.math.Vector;
14 
15 /**
16  * A polygon is an object defined by its vertices in 2 space
17  * T is the type of the polygon and sides is how many sides the polygon has
18  * TODO: upgrade to dimension-ambiguous model class in math
19  */
20 class Polygon(T, uint numSides) {
21 
22     Vector!(T, 2)[numSides] vertices; ///The vertices of the polygon
23 
24     /**
25      * Gets the sides of a polygon
26      */
27     @property Segment!(T, 2)[numSides] sides() {
28         Segment!(T, 2)[numSides] s;
29         foreach (i; iota(0, cast(uint) numSides).parallel) {
30             s[i] = new Segment!(T, 2)(this.vertices[i], this.vertices[(i + 1) % $]);
31         }
32         return s;
33     }
34 
35     /**
36      * Creates an empty polygon
37      */
38     this() {}
39 
40     /**
41      * Creates a polygon using a list of vertices as vertices
42      */
43     this(Vector!(T, 2)[] vertices...) {
44         assert(vertices.length == numSides);
45         this.vertices = vertices;
46     }
47 
48     /**
49      * Casts the polygon to a polygon of another type
50      */
51     U opCast(U)() if (is(U : Polygon!V, V...)) {
52         alias type = TemplateArgsOf!U[0];
53         return new U(cast(Vector!(type, 2)[]) this.vertices);
54     }
55 
56     /**
57      * Returns whether or not a given point is inside the polygon
58      * This algorithm uses scanlining (see Renderer.fillPolygon) 
59      * Conceptually, it draws a ray to the left from the given point; if the ray intersects the polygon an odd number of times
60      * the point is within the polygon
61      */
62     bool contains(U)(Vector!(U, 2) point) {
63         Segment!(T, 2)[] relevantSides = (cast(Segment!(T, 2)[]) this.sides).filter!(
64                 a => (a.initial.y - point.y) * (a.terminal.y - point.y) <= 0).array;
65         int intersections;
66         foreach (side; relevantSides) {
67             immutable dy = point.y - side.initial.y;
68             immutable intersection = (dy * side.direction.x + side.initial.x * side.direction.y) / side
69                 .direction.y;
70             if (intersection < point.x) {
71                 intersections++;
72             }
73         }
74         return intersections % 2 == 1;
75     }
76 
77 }
78 
79 /**
80  * Returns the rectangle bounding a polygon
81  */
82 AxisAlignedBoundingBox!(T, 2) bound(T, uint sides)(Polygon!(T, sides) toBound) {
83     Vector!(T, 2) minVals = new Vector!(T, 2)(T.max);
84     Vector!(T, 2) maxVals = new Vector!(T, 2)(T.max + 1); //Causes an overflow to get small value
85     foreach (vertex; toBound.vertices) {
86         if (vertex.x < minVals.x) {
87             minVals.x = vertex.x;
88         }
89         if (vertex.x > maxVals.x) {
90             maxVals.x = vertex.x;
91         }
92         if (vertex.y < minVals.y) {
93             minVals.y = vertex.y;
94         }
95         if (vertex.y > maxVals.y) {
96             maxVals.y = vertex.y;
97         }
98     }
99     return new AxisAlignedBoundingBox!(T, 2)(minVals.x, minVals.y,
100             maxVals.x - minVals.x, maxVals.y - minVals.y);
101 }
102 
103 alias iPolygon(uint T) = Polygon!(int, T);
104 alias dPolygon(uint T) = Polygon!(double, T);
105 alias fPolygon(uint T) = Polygon!(float, T);