2 * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
3 * Understanding is not required. Only obedience.
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
18 module iv
.vmath2d
.math2d
;
20 public import iv
.vmath
;
23 // ////////////////////////////////////////////////////////////////////////// //
24 public struct Math2D
{
29 static T
nmin(T
) (in T a
, in T b
) { pragma(inline
, true); return (a
< b ? a
: b
); }
30 static T
nmax(T
) (in T a
, in T b
) { pragma(inline
, true); return (a
> b ? a
: b
); }
32 // gets the signed area
33 // if the area is less than 0, it indicates that the polygon is clockwise winded
34 auto signedArea(VT
) (const(VT
)[] verts
) @trusted if (IsVectorDim
!(VT
, 2)) {
36 if (verts
.length
< 3) return area
;
37 auto j
= verts
.length
-1;
39 for (; i
< verts
.length
; j
= i
, ++i
) {
40 area
+= verts
.ptr
[j
].x
*verts
.ptr
[i
].y
;
41 area
-= verts
.ptr
[j
].y
*verts
.ptr
[i
].x
;
43 return area
/cast(VT
.Float
)2;
46 // indicates if the vertices are in counter clockwise order
47 // warning: If the area of the polygon is 0, it is unable to determine the winding
48 bool isCCW(VT
) (const(VT
)[] verts
) if (IsVectorDim
!(VT
, 2)) {
49 return (verts
.length
> 2 && signedArea(verts
) > 0);
52 bool isCollinear(VT
, T
:double) (in auto ref VT a
, in auto ref VT b
, in auto ref VT c
, T tolerance
=0) if (IsVectorDim
!(VT
, 2)) {
54 mixin(ImportCoreMath
!(VT
.Float
, "fabs"));
55 return (fabs((b
.x
-a
.x
)*(c
.y
-a
.y
)-(c
.x
-a
.x
)*(b
.y
-a
.y
)) <= EPSILON
!(VT
.Float
)+tolerance
);
58 // *signed* area; can be used to check on which side `b` is
59 auto area(VT
) (in auto ref VT a
, in auto ref VT b
, in auto ref VT c
) if (IsVectorDim
!(VT
, 2)) {
61 return (b
.x
-a
.x
)*(c
.y
-a
.y
)-(c
.x
-a
.x
)*(b
.y
-a
.y
);
64 VT
lineIntersect(VT
) (in auto ref VT p1
, in auto ref VT p2
, in auto ref VT q1
, in auto ref VT q2
) if (IsVectorDim
!(VT
, 2)) {
66 mixin(ImportCoreMath
!(VT
.Float
, "fabs"));
67 immutable VT
.Float a1
= p2
.y
-p1
.y
;
68 immutable VT
.Float b1
= p1
.x
-p2
.x
;
69 immutable VT
.Float c1
= a1
*p1
.x
+b1
*p1
.y
;
70 immutable VT
.Float a2
= q2
.y
-q1
.y
;
71 immutable VT
.Float b2
= q1
.x
-q2
.x
;
72 immutable VT
.Float c2
= a2
*q1
.x
+b2
*q1
.y
;
73 immutable VT
.Float det
= a1
*b2
-a2
*b1
;
74 if (fabs(det
) > EPSILON
!(VT
.Float
)) {
75 // lines are not parallel
76 immutable VT
.Float invdet
= cast(VT
.Float
)1/det
;
77 return VT((b2
*c1
-b1
*c2
)*invdet
, (a1
*c2
-a2
*c1
)*invdet
);
82 VT
segIntersect(bool firstIsSeg
=true, bool secondIsSeg
=true, VT
) (in auto ref VT point0
, in auto ref VT point1
, in auto ref VT point2
, in auto ref VT point3
) if (IsVectorDim
!(VT
, 2)) {
83 mixin(ImportCoreMath
!(VT
.Float
, "fabs"));
84 static if (firstIsSeg
&& secondIsSeg
) {
85 // fast aabb test for possible early exit
86 if (nmax(point0
.x
, point1
.x
) < nmin(point2
.x
, point3
.x
) ||
nmax(point2
.x
, point3
.x
) < nmin(point0
.x
, point1
.x
)) return VT
.Invalid
;
87 if (nmax(point0
.y
, point1
.y
) < nmin(point2
.y
, point3
.y
) ||
nmax(point2
.y
, point3
.y
) < nmin(point0
.y
, point1
.y
)) return VT
.Invalid
;
89 immutable VT
.Float den
= ((point3
.y
-point2
.y
)*(point1
.x
-point0
.x
))-((point3
.x
-point2
.x
)*(point1
.y
-point0
.y
));
90 if (fabs(den
) > EPSILON
!(VT
.Float
)) {
91 immutable VT
.Float e
= point0
.y
-point2
.y
;
92 immutable VT
.Float f
= point0
.x
-point2
.x
;
93 immutable VT
.Float invden
= cast(VT
.Float
)1/den
;
94 immutable VT
.Float ua
= (((point3
.x
-point2
.x
)*e
)-((point3
.y
-point2
.y
)*f
))*invden
;
95 static if (firstIsSeg
) { if (ua
< 0 || ua
> 1) return VT
.Invalid
; }
96 if (ua
>= 0 && ua
<= 1) {
97 immutable VT
.Float ub
= (((point1
.x
-point0
.x
)*e
)-((point1
.y
-point0
.y
)*f
))*invden
;
98 static if (secondIsSeg
) { if (ub
< 0 || ub
> 1) return VT
.Invalid
; }
99 if (ua
!= 0 || ub
!= 0) return VT(point0
.x
+ua
*(point1
.x
-point0
.x
), point0
.y
+ua
*(point1
.y
-point0
.y
));