vmath2d/math2d.d

   1 /*
   2  * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   3  * Understanding is not required. Only obedience.
   4  *
   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.
   9  *
  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.
  14  *
  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/>.
  17  */
  18 module iv.vmath2d.math2d;
  19
  20 public import iv.vmath;
  21
  22
  23 // ////////////////////////////////////////////////////////////////////////// //
  24 public struct Math2D {
  25   @disable this ();
  26   @disable this (this);
  27
  28 public static:
  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); }
  31
  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)) {
  35     VT.Float area = 0;
  36     if (verts.length < 3) return area;
  37     auto j = verts.length-1;
  38     typeof(j) i = 0;
  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;
  42     }
  43     return area/cast(VT.Float)2;
  44   }
  45
  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);
  50   }
  51
  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)) {
  53     pragma(inline, true);
  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);
  56   }
  57
  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)) {
  60     pragma(inline, true);
  61     return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
  62   }
  63
  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)) {
  65     pragma(inline, true);
  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);
  78     }
  79     return VT.Invalid;
  80   }
  81
  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;
  88     }
  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));
 100       }
 101     }
 102     return VT.Invalid;
 103   }
 104 }