1 /**
2  * 2D geometry math stuff
3  *
4  * License:
5  *   This Source Code Form is subject to the terms of
6  *   the Mozilla Public License, v. 2.0. If a copy of
7  *   the MPL was not distributed with this file, You
8  *   can obtain one at http://mozilla.org/MPL/2.0/.
9  *
10  * Authors:
11  *   Vladimir Panteleev <vladimir@thecybershadow.net>
12  */
13 
14 module ae.utils.geometry;
15 
16 import std.traits;
17 import std.math;
18 
19 import ae.utils.math;
20 
21 enum TAU = 2*PI;
22 
23 auto sqrtx(T)(T x)
24 {
25 	static if (is(T : int))
26 		return std.math.sqrt(cast(float)x);
27 	else
28 		return std.math.sqrt(x);
29 }
30 
31 auto dist (T)(T x, T y) { return sqrtx(x*x+y*y); }
32 auto dist2(T)(T x, T y) { return       x*x+y*y ; }
33 
34 struct Point(T)
35 {
36 	T x, y;
37 	void translate(T dx, T dy) { x += dx; y += dy; }
38 	Point!T getCenter() { return this; }
39 }
40 auto point(T...)(T args) { return Point!(CommonType!T)(args); }
41 
42 struct Rect(T)
43 {
44 	T x0, y0, x1, y1;
45 	@property T w() { return x1-x0; }
46 	@property T h() { return y1-y0; }
47 	void sort() { sort2(x0, x1); sort2(y0, y1); }
48 	@property bool sorted() { return x0 <= x1 && y0 <= y1; }
49 	void translate(T dx, T dy) { x0 += dx; y0 += dy; x1 += dx; y1 += dy; }
50 	Point!T getCenter() { return Point!T(average(x0, x1), average(y0, y1)); }
51 }
52 auto rect(T...)(T args) { return Rect!(CommonType!T)(args); }
53 
54 struct Circle(T)
55 {
56 	T x, y, r;
57 	@property T diameter() { return 2*r; }
58 	void translate(T dx, T dy) { x += dx; y += dy; }
59 	Point!T getCenter() { return Point!T(x, y); }
60 }
61 auto circle(T...)(T args) { return Circle!(CommonType!T)(args); }
62 
63 enum ShapeKind { none, point, rect, circle }
64 struct Shape(T)
65 {
66 	ShapeKind kind;
67 	union
68 	{
69 		Point!T point;
70 		Rect!T rect;
71 		Circle!T circle;
72 	}
73 
74 	this(Point!T point)
75 	{
76 		this.kind = ShapeKind.point;
77 		this.point = point;
78 	}
79 
80 	this(Rect!T rect)
81 	{
82 		this.kind = ShapeKind.rect;
83 		this.rect = rect;
84 	}
85 
86 	this(Circle!T circle)
87 	{
88 		this.kind = ShapeKind.circle;
89 		this.circle = circle;
90 	}
91 
92 	auto opDispatch(string s, T...)(T args)
93 		if (is(typeof(mixin("point ." ~ s ~ "(args)"))) &&
94 		    is(typeof(mixin("rect  ." ~ s ~ "(args)"))) &&
95 		    is(typeof(mixin("circle." ~ s ~ "(args)"))))
96 	{
97 		switch (kind)
98 		{
99 			case ShapeKind.point:
100 				return mixin("point ." ~ s ~ "(args)");
101 			case ShapeKind.circle:
102 				return mixin("circle." ~ s ~ "(args)");
103 			case ShapeKind.rect:
104 				return mixin("rect  ." ~ s ~ "(args)");
105 			default:
106 				assert(0);
107 		}
108 	}
109 }
110 auto shape(T)(T shape) { return Shape!(typeof(shape.tupleof[0]))(shape); }
111 
112 bool intersects(T)(Shape!T a, Shape!T b)
113 {
114 	switch (a.kind)
115 	{
116 		case ShapeKind.point:
117 			switch (b.kind)
118 			{
119 			case ShapeKind.point:
120 				return a.point.x == b.point.x && a.point.y == b.point.y;
121 			case ShapeKind.circle:
122 				return dist2(a.point.x-b.circle.x, a.point.y-b.circle.y) < sqr(b.circle.r);
123 			case ShapeKind.rect:
124 				assert(b.rect.sorted);
125 				return between(a.point.x, b.rect.x0, b.rect.x1) && between(a.point.y, b.rect.y0, b.rect.y1);
126 			default:
127 				assert(0);
128 			}
129 		case ShapeKind.circle:
130 			switch (b.kind)
131 			{
132 			case ShapeKind.point:
133 				return dist2(a.circle.x-b.point.x, a.circle.y-b.point.y) < sqr(a.circle.r);
134 			case ShapeKind.circle:
135 				return dist2(a.circle.x-b.circle.x, a.circle.y-b.circle.y) < sqr(a.circle.r+b.circle.r);
136 			case ShapeKind.rect:
137 				return intersects!T(a.circle, b.rect);
138 			default:
139 				assert(0);
140 			}
141 		case ShapeKind.rect:
142 			switch (b.kind)
143 			{
144 			case ShapeKind.point:
145 				assert(a.rect.sorted);
146 				return between(b.point.x, a.rect.x0, a.rect.x1) && between(b.point.y, a.rect.y0, a.rect.y1);
147 			case ShapeKind.circle:
148 				return intersects!T(b.circle, a.rect);
149 			case ShapeKind.rect:
150 				assert(0); // TODO
151 			default:
152 				assert(0);
153 			}
154 		default:
155 			assert(0);
156 	}
157 }
158 
159 bool intersects(T)(Circle!T circle, Rect!T rect)
160 {
161 	// http://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection
162 
163 	Point!T circleDistance;
164 
165 	auto hw = rect.w/2, hh = rect.h/2;
166 
167 	circleDistance.x = abs(circle.x - rect.x0 - hw);
168 	circleDistance.y = abs(circle.y - rect.y0 - hh);
169 
170 	if (circleDistance.x > (hw + circle.r)) return false;
171 	if (circleDistance.y > (hh + circle.r)) return false;
172 
173 	if (circleDistance.x <= hw) return true;
174 	if (circleDistance.y <= hh) return true;
175 
176 	auto cornerDistance_sq =
177 		sqr(circleDistance.x - hw) +
178 		sqr(circleDistance.y - hh);
179 
180 	return (cornerDistance_sq <= sqr(circle.r));
181 }