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, version 3 of the License ONLY.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  16  */
  17 module iv.vmath2d.math2d;
  18
  19 public import iv.vmath;
  20
  21
  22 // ////////////////////////////////////////////////////////////////////////// //
  23 public struct Math2D {
  24   @disable this ();
  25   @disable this (this);
  26
  27 public static:
  28   static T nmin(T) (in T a, in T b) { pragma(inline, true); return (a < b ? a : b); }
  29   static T nmax(T) (in T a, in T b) { pragma(inline, true); return (a > b ? a : b); }
  30
  31   // gets the signed area
  32   // if the area is less than 0, it indicates that the polygon is clockwise winded
  33   auto signedArea(VT) (const(VT)[] verts) @trusted if (IsVectorDim!(VT, 2)) {
  34     VT.Float area = 0;
  35     if (verts.length < 3) return area;
  36     auto j = verts.length-1;
  37     typeof(j) i = 0;
  38     for (; i < verts.length; j = i, ++i) {
  39       area += verts.ptr[j].x*verts.ptr[i].y;
  40       area -= verts.ptr[j].y*verts.ptr[i].x;
  41     }
  42     return area/cast(VT.Float)2;
  43   }
  44
  45   // indicates if the vertices are in counter clockwise order
  46   // warning: If the area of the polygon is 0, it is unable to determine the winding
  47   bool isCCW(VT) (const(VT)[] verts) if (IsVectorDim!(VT, 2)) {
  48     return (verts.length > 2 && signedArea(verts) > 0);
  49   }
  50
  51   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)) {
  52     pragma(inline, true);
  53     mixin(ImportCoreMath!(VT.Float, "fabs"));
  54     return (fabs((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y)) <= EPSILON!(VT.Float)+tolerance);
  55   }
  56
  57   // *signed* area; can be used to check on which side `b` is
  58   auto area(VT) (in auto ref VT a, in auto ref VT b, in auto ref VT c) if (IsVectorDim!(VT, 2)) {
  59     pragma(inline, true);
  60     return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
  61   }
  62
  63   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)) {
  64     pragma(inline, true);
  65     mixin(ImportCoreMath!(VT.Float, "fabs"));
  66     immutable VT.Float a1 = p2.y-p1.y;
  67     immutable VT.Float b1 = p1.x-p2.x;
  68     immutable VT.Float c1 = a1*p1.x+b1*p1.y;
  69     immutable VT.Float a2 = q2.y-q1.y;
  70     immutable VT.Float b2 = q1.x-q2.x;
  71     immutable VT.Float c2 = a2*q1.x+b2*q1.y;
  72     immutable VT.Float det = a1*b2-a2*b1;
  73     if (fabs(det) > EPSILON!(VT.Float)) {
  74       // lines are not parallel
  75       immutable VT.Float invdet = cast(VT.Float)1/det;
  76       return VT((b2*c1-b1*c2)*invdet, (a1*c2-a2*c1)*invdet);
  77     }
  78     return VT.Invalid;
  79   }
  80
  81   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)) {
  82     mixin(ImportCoreMath!(VT.Float, "fabs"));
  83     static if (firstIsSeg && secondIsSeg) {
  84       // fast aabb test for possible early exit
  85       if (nmax(point0.x, point1.x) < nmin(point2.x, point3.x) || nmax(point2.x, point3.x) < nmin(point0.x, point1.x)) return VT.Invalid;
  86       if (nmax(point0.y, point1.y) < nmin(point2.y, point3.y) || nmax(point2.y, point3.y) < nmin(point0.y, point1.y)) return VT.Invalid;
  87     }
  88     immutable VT.Float den = ((point3.y-point2.y)*(point1.x-point0.x))-((point3.x-point2.x)*(point1.y-point0.y));
  89     if (fabs(den) > EPSILON!(VT.Float)) {
  90       immutable VT.Float e = point0.y-point2.y;
  91       immutable VT.Float f = point0.x-point2.x;
  92       immutable VT.Float invden = cast(VT.Float)1/den;
  93       immutable VT.Float ua = (((point3.x-point2.x)*e)-((point3.y-point2.y)*f))*invden;
  94       static if (firstIsSeg) { if (ua < 0 || ua > 1) return VT.Invalid; }
  95       if (ua >= 0 && ua <= 1) {
  96         immutable VT.Float ub = (((point1.x-point0.x)*e)-((point1.y-point0.y)*f))*invden;
  97         static if (secondIsSeg) { if (ub < 0 || ub > 1) return VT.Invalid; }
  98         if (ua != 0 || ub != 0) return VT(point0.x+ua*(point1.x-point0.x), point0.y+ua*(point1.y-point0.y));
  99       }
 100     }
 101     return VT.Invalid;
 102   }
 103 }