vmath2d/vxstore.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.vxstore;
  18
  19 import iv.alice;
  20 import iv.vmath2d.math2d;
  21
  22
  23 // ////////////////////////////////////////////////////////////////////////// //
  24 public template IsGoodVertexStorage(T, VT) if ((is(T == struct) || is(T == class)) && IsVectorDim!(VT, 2)) {
  25   enum IsGoodVertexStorage = is(typeof((inout int=0) {
  26     T o = T.init;
  27     VT v = o[0];
  28     o[0] = v;
  29     v = o.centroid;
  30     int len = o.length;
  31     const(VT)[] vs = o[0..2];
  32     vs = o[];
  33     vs = o[1..$];
  34     // sadly, we can't check for `opIndex()` wrapping here
  35     o.swap(1, 2);
  36     // sadly, we can't check for `swap()` wrapping here
  37     o.remove(1);
  38     bool ins = o.inside(VT(0, 0));
  39     ins = o.inside(0, 0);
  40   }));
  41 }
  42
  43 public template IsGoodVertexStorage(T) if (is(T == struct) || is(T == class)) {
  44   static import std.traits;
  45   static if (is(std.traits.Unqual!(typeof(T.init.centroid)))) {
  46     enum IsGoodVertexStorage = IsGoodVertexStorage!(T, std.traits.Unqual!(typeof(T.init.centroid)));
  47   } else {
  48     enum IsGoodVertexStorage = false;
  49   }
  50 }
  51
  52 public template VertexStorageVT(T) if (IsGoodVertexStorage!T) {
  53   static import std.traits;
  54   alias VertexStorageVT = std.traits.Unqual!(typeof(T.init.centroid));
  55 }
  56
  57 //static assert(IsGoodVertexStorage!(VertexStorage!vec2));
  58 //pragma(msg, VertexStorageVT!(VertexStorage!vec2));
  59
  60
  61 // ////////////////////////////////////////////////////////////////////////// //
  62 public enum VertexStorageCommon = q{
  63   void moveBy() (VT.Float dx, VT.Float dy) { moveBy(VT(dx, dy)); }
  64
  65   void moveTo() (in auto ref VT pos) { moveBy(pos-centroid); }
  66   void moveTo() (VT.Float x, VT.Float y) { moveBy(VT(x, y)-centroid); }
  67
  68   bool inside() (VT.Float x, VT.Float y) { return inside(VT(x, y)); }
  69 };
  70
  71
  72 // ////////////////////////////////////////////////////////////////////////// //
  73 public struct VertexStorage(VT) if (IsVectorDim!(VT, 2)) {
  74 private:
  75   VT[] vtx;
  76   VT center = VT.Zero;
  77   int vtxUsed;
  78
  79 public:
  80   mixin(VertexStorageCommon);
  81
  82   // WARNING! all slices will become UB!
  83   void clear(bool complete=false) () {
  84     vtxUsed = 0;
  85     static if (complete) {
  86       if (vtx !is null) delete vtx;
  87     }
  88     center = VT.Zero;
  89   }
  90
  91   @property bool empty () const pure nothrow @safe @nogc { pragma(inline, true); return (vtxUsed == 0); }
  92
  93   @property int length () const pure nothrow @safe @nogc { pragma(inline, true); return vtxUsed; }
  94   alias opDollar = length;
  95
  96   @property VT centroid () nothrow @safe @nogc {
  97     //pragma(inline, true);
  98     if (!center.isFinite) {
  99       center = VT.Zero;
 100       if (vtxUsed > 0) {
 101         foreach (const ref v; vtx[0..vtxUsed]) center += v;
 102         center /= cast(VT.Float)vtxUsed;
 103       }
 104     }
 105     return center;
 106   }
 107
 108   bool sameIndex (int i0, int i1) const pure nothrow @safe @nogc {
 109     pragma(inline, true);
 110     return (((i0%vtxUsed)+vtxUsed)%vtxUsed == ((i1%vtxUsed)+vtxUsed)%vtxUsed);
 111   }
 112
 113   VT opIndex (int idx) const pure nothrow @trusted @nogc {
 114     pragma(inline, true);
 115     if (vtxUsed == 0) assert(0, "no vertices in storage");
 116     return vtx.ptr[((idx%vtxUsed)+vtxUsed)%vtxUsed];
 117   }
 118
 119   void opIndexAssign() (in auto ref VT v, int idx) nothrow @trusted @nogc {
 120     pragma(inline, true);
 121     if (vtxUsed == 0) assert(0, "no vertices in storage");
 122     vtx.ptr[((idx%vtxUsed)+vtxUsed)%vtxUsed] = v;
 123     center = VT.Invalid;
 124   }
 125
 126   void swap (int i0, int i1) pure nothrow @trusted @nogc {
 127     if (vtxUsed == 0) assert(0, "no vertices in storage");
 128     if (i0 == i1) return;
 129     i0 = ((i0%vtxUsed)+vtxUsed)%vtxUsed;
 130     i1 = ((i1%vtxUsed)+vtxUsed)%vtxUsed;
 131     auto tmp = vtx.ptr[i0];
 132     vtx.ptr[i0] = vtx.ptr[i1];
 133     vtx.ptr[i1] = tmp;
 134   }
 135
 136   // WILL become UB if storage will go out of scope when the result is still alive
 137   const(VT)[] opSlice (int lo, int hi) inout pure nothrow @trusted @nogc {
 138     pragma(inline, true);
 139     if (lo < 0 || hi < 0 || lo > hi || lo > vtxUsed || hi > vtxUsed) assert(0, "invalid slicing");
 140     return vtx[lo..hi];
 141   }
 142
 143   // WILL become UB if storage will go out of scope when the result is still alive
 144   const(VT)[] opSlice () inout pure nothrow @trusted @nogc {
 145     pragma(inline, true);
 146     return vtx[0..vtxUsed];
 147   }
 148
 149   void opOpAssign(string op:"~") (in auto ref VT v) nothrow @trusted {
 150     if (vtxUsed >= int.max/2) assert(0, "out of memory for vertices");
 151     if (vtxUsed < vtx.length) {
 152       vtx.ptr[vtxUsed] = v;
 153     } else {
 154       assert(vtxUsed == vtx.length);
 155       auto optr = vtx.ptr;
 156       vtx ~= v;
 157       if (vtx.ptr !is optr) {
 158         import core.memory : GC;
 159         optr = vtx.ptr;
 160         if (optr is GC.addrOf(optr)) GC.setAttr(optr, GC.BlkAttr.NO_INTERIOR);
 161       }
 162     }
 163     ++vtxUsed;
 164     center = VT.Invalid;
 165   }
 166
 167   void remove (int idx) nothrow @trusted {
 168     import core.stdc.string : memmove;
 169     if (vtxUsed == 0) assert(0, "no vertices in storage");
 170     auto i = ((idx%vtxUsed)+vtxUsed)%vtxUsed;
 171     if (i < vtxUsed-1) memmove(vtx.ptr+i, vtx.ptr+i+1, (vtxUsed-i-1)*vtx[0].sizeof);
 172     --vtxUsed;
 173     center = VT.Invalid;
 174   }
 175
 176   void moveBy() (in auto ref VT ofs) nothrow @trusted {
 177     foreach (ref v; vtx[0..vtxUsed]) v += ofs;
 178     if (center.isFinite) center += ofs;
 179   }
 180
 181   bool inside() (in auto ref VT p) { return insideConvexHelper(this, p); }
 182 }
 183
 184 //static assert(IsGoodVertexStorage!(VertexStorage!vec2, vec2));
 185 /*
 186 void foo () {
 187   VertexStorage!vec2 vs;
 188   vs.moveTo(vec2(0, 0));
 189   auto v0 = vs[0];
 190   vs ~= v0;
 191   vs[0] = v0;
 192   auto c = vs.centroid;
 193   auto s0 = vs[];
 194   auto s1 = vs[1..$];
 195 }
 196 */
 197
 198
 199 // ////////////////////////////////////////////////////////////////////////// //
 200 private int sign(T) (T v) { pragma(inline, true); return (v < 0 ? -1 : v > 0 ? 1 : 0); }
 201
 202
 203 // ////////////////////////////////////////////////////////////////////////// //
 204 // dumb O(n) support function, just brute force check all points
 205 public VT supportDumb(VS, VT) (ref VS vstore, in auto ref VT dir) if (IsGoodVertexStorage!(VS, VT)) {
 206   if (vstore.length == 0) return VT.Invalid; // dunno, something
 207   VT sup = vstore[0];
 208   auto maxDot = sup.dot(dir);
 209   foreach (const ref v; vstore[1..$]) {
 210     immutable d = v.dot(dir);
 211     if (d > maxDot) { maxDot = d; sup = v; }
 212   }
 213   return sup;
 214 }
 215
 216
 217 // support function using hill climbing
 218 public VT support(VS, VT) (ref VS vstore, in auto ref VT dir) if (IsGoodVertexStorage!(VS, VT)) {
 219   if (vstore.length <= 4) return supportDumb(vstore, dir); // we will check all vertices in those cases anyway
 220
 221   int vidx = 1, vtxdir = 1;
 222   auto maxDot = vstore[1].dot(dir);
 223
 224   // check backward direction
 225   immutable dot0delta = vstore[0].dot(dir)-maxDot;
 226   // if dot0delta is negative, there is no reason to go backwards
 227   if (dot0delta > 0) {
 228     // check forward direction
 229     immutable dot2delta = vstore[2].dot(dir)-maxDot;
 230     vtxdir = (dot2delta > dot0delta ? 1 : -1);
 231   }
 232
 233   // this loop is guaranteed to stop (obviously), but only for good convexes, so limit iteration count
 234   foreach (immutable itrcount; 0..vstore.length) {
 235     immutable d = vstore[vidx+vtxdir].dot(dir);
 236     if (d < maxDot) return vstore[vidx]; // i found her!
 237     // advance
 238     maxDot = d;
 239     vidx += vtxdir;
 240   }
 241
 242   // degenerate poly
 243   return vstore[vidx];
 244 }
 245
 246
 247 // gets the signed area
 248 // if the area is less than 0, it indicates that the polygon is clockwise winded
 249 public auto signedArea(VS) (ref VS vstore) if (IsGoodVertexStorage!VS) {
 250   alias VT = VertexStorageVT!VS;
 251   if (vstore.length < 3) return 0;
 252   VT.Float area = 0;
 253   foreach (immutable i; 0..vstore.length) {
 254     area += vstore[i].x*vstore[i+1].y;
 255     area -= vstore[i].y*vstore[i+1].x;
 256   }
 257   return area/cast(VT.Float)2;
 258 }
 259
 260
 261 // indicates if the vertices are in counter clockwise order
 262 // warning: If the area of the polygon is 0, it is unable to determine the winding
 263 public bool isCCW(VS) (ref VS vstore) if (IsGoodVertexStorage!VS) {
 264   return (vstore.length > 2 && signedArea(vstore) > 0);
 265 }
 266
 267
 268 // forces the vertices to be counter clock wise order
 269 public void forceCCW(VS) (ref VS vstore) if (IsGoodVertexStorage!VS) {
 270   if (vstore.length < 3) return;
 271   if (!isCCW(vstore)) {
 272     foreach (immutable idx; 0..vstore.length/2) vstore.swap(idx, vstore.length-idx-1);
 273     assert(isCCW(vstore));
 274   }
 275 }
 276
 277
 278 // removes all collinear points
 279 public void collinearSimplify(VS, FT:double) (ref VS vstore, FT tolerance=0) if (IsGoodVertexStorage!VS) {
 280   alias VT = VertexStorageVT!VS;
 281   int idx = 0;
 282   while (vstore.length > 3 && idx < vstore.length) {
 283     if (Math2D.isCollinear(vstore[idx-1], vstore[idx], vstore[idx+1], cast(VT.Float)tolerance)) {
 284       vstore.remove(idx);
 285     } else {
 286       ++idx;
 287     }
 288   }
 289 }
 290
 291
 292 // shapes with collinear/identical points aren't "convex"
 293 public bool isConvex(VS) (ref VS vstore) if (IsGoodVertexStorage!VS) {
 294   if (vstore.length < 3) return false;
 295   if (vstore.length == 3) return true; // nothing to check here
 296   int dir;
 297   foreach (immutable idx, const ref v0; vstore[]) {
 298     //immutable v0 = vstore[idx];
 299     immutable v1 = vstore[idx+1]-v0;
 300     immutable v2 = vstore[idx+2];
 301     int d = sign(v2.x*v1.y-v2.y*v1.x+v1.x*v0.y-v1.y*v0.x);
 302     if (d == 0) return false;
 303     if (idx) {
 304       if (dir != d) return false;
 305     } else {
 306       dir = d;
 307     }
 308   }
 309   return true;
 310 }
 311
 312
 313 public bool insideConvexHelper(VS, VT) (ref VS vstore, in auto ref VT p) /*if (IsGoodVertexStorage!(VS, VT))*/ {
 314   if (vstore.length < 3) return false;
 315   int side = 0;
 316   foreach (immutable idx, const ref v; vstore[]) {
 317     int d = sign((vstore[idx+1]-v).cross(p-v));
 318     if (d != 0) {
 319       if (side == 0) side = d; else if (side != d) return false;
 320     }
 321   }
 322   return true;
 323 }
 324
 325
 326 /*
 327 // use centroid
 328 public void moveTo(VS, VT) (ref VS vstore, in auto ref VT pos) if (IsGoodVertexStorage!(VS, VT)) {
 329   static if (is(typeof(&vstore.moveTo))) {
 330     vstore.moveTo(pos);
 331   } else {
 332     immutable ofs = pos-vstore.centroid;
 333     foreach (immutable idx, const ref v; vstore[]) vstore[idx] = v+ofs;
 334   }
 335 }
 336
 337
 338 public void moveTo(VS, FT:double) (ref VS vstore, FT x, FT y) if (IsGoodVertexStorage!VS) {
 339   alias VT = VertexStorageVT!VS;
 340   moveTo!VS(vstore, VT(cast(VT.Float)x, cast(VT.Float)y));
 341 }
 342
 343
 344 public void moveByHelper(VS, VT) (ref VS vstore, in auto ref VT ofs) if (IsGoodVertexStorage!(VS, VT)) {
 345   static if (is(typeof(&vstore.moveBy))) {
 346     vstore.moveBy(ofs);
 347   } else {
 348     foreach (immutable idx, const ref v; vstore[]) vstore[idx] = v+ofs;
 349   }
 350 }
 351
 352
 353 public void moveByHelper(VS, FT:double) (ref VS vstore, FT x, FT y) if (IsGoodVertexStorage!VS) {
 354   alias VT = VertexStorageVT!VS;
 355   .moveByHelper!VS(vstore, VT(cast(VT.Float)x, cast(VT.Float)y));
 356 }
 357 */
 358
 359
 360 public void scaleBy(VS, VT) (ref VS vstore, in auto ref VT scale) if (IsGoodVertexStorage!(VS, VT)) {
 361   foreach (immutable idx, const ref v; vstore[]) vstore[idx] = VT(v.x*scale.x, v.y*scale.y);
 362 }
 363
 364
 365 public void scaleBy(VS, FT:double) (ref VS vstore, FT scale) if (IsGoodVertexStorage!VS) {
 366   alias VT = VertexStorageVT!VS;
 367   scaleBy(vstore, VT(cast(VT.Float)scale, cast(VT.Float)scale));
 368 }
 369
 370
 371 // replace vstore points with convex hull (or nothing if it is not possible to build convex hull)
 372 // returns `false` if convex hull cannot be built
 373 public bool buildConvex(VS) (ref VS vstore) if (IsGoodVertexStorage!VS) {
 374   alias VT = VertexStorageVT!VS;
 375
 376   // no hulls with less than 3 vertices (ensure actual polygon)
 377   if (vstore.length < 3) { vstore.clear(); return false; }
 378
 379   // copy original vertices
 380   static VT[] averts;
 381   if (averts.length < vstore.length) {
 382     auto optr = averts.ptr;
 383     averts.length = vstore.length;
 384     if (averts.ptr !is optr) {
 385       import core.memory : GC;
 386       optr = averts.ptr;
 387       if (optr is GC.addrOf(optr)) GC.setAttr(optr, GC.BlkAttr.NO_INTERIOR);
 388     }
 389   }
 390   assert(averts.length >= vstore.length);
 391   foreach (immutable idx, const ref v; vstore[]) averts.ptr[idx] = v;
 392
 393   // find the right most point on the hull
 394   int rightMost = 0;
 395   VT.Float highestXCoord = averts[0].x;
 396   foreach (immutable i; 1..averts.length) {
 397     VT.Float x = averts[i].x;
 398     if (x > highestXCoord) {
 399       highestXCoord = x;
 400       rightMost = cast(int)i;
 401     } else if (x == highestXCoord) {
 402       // if matching x then take farthest negative y
 403       if (averts[i].y < averts[rightMost].y) rightMost = cast(int)i;
 404     }
 405   }
 406
 407   static int[] hull;
 408   if (hull.length < averts.length) {
 409     auto optr = hull.ptr;
 410     hull.length = averts.length;
 411     if (hull.ptr !is optr) {
 412       import core.memory : GC;
 413       optr = hull.ptr;
 414       if (optr is GC.addrOf(optr)) GC.setAttr(optr, GC.BlkAttr.NO_INTERIOR);
 415     }
 416   }
 417   hull.ptr[0..averts.length] = 0; // just in case, lol
 418
 419   int outCount = 0;
 420   int indexHull = rightMost;
 421   int vcount = 0;
 422
 423   for (;;) {
 424     hull[outCount] = indexHull;
 425
 426     // search for next index that wraps around the hull by computing cross products to
 427     // find the most counter-clockwise vertex in the set, given the previos hull index
 428     int nextHullIndex = 0;
 429     foreach (immutable i; 1..averts.length) {
 430       // skip if same coordinate as we need three unique points in the set to perform a cross product
 431       if (nextHullIndex == indexHull) { nextHullIndex = i; continue; }
 432       // cross every set of three unique vertices
 433       // record each counter clockwise third vertex and add to the output hull
 434       immutable e1 = averts[nextHullIndex]-averts[hull[outCount]];
 435       immutable e2 = averts[i]-averts[hull[outCount]];
 436       immutable c = e1.cross(e2);
 437       if (c < 0) nextHullIndex = i;
 438       // cross product is zero then e vectors are on same line
 439       // therefore want to record vertex farthest along that line
 440       if (c == 0 && e2.lengthSquared > e1.lengthSquared) nextHullIndex = i;
 441     }
 442     ++outCount;
 443     indexHull = nextHullIndex;
 444     // conclude algorithm upon wrap-around
 445     if (nextHullIndex == rightMost) { vcount = outCount; break; }
 446   }
 447   if (vcount < 3) { vstore.clear(); return false; }
 448
 449   // copy vertices into shape's vertices
 450   vstore.clear();
 451   foreach (immutable hidx; hull[0..vcount]) vstore ~= averts[hidx];
 452   if (!isConvex(vstore)) { vstore.clear(); return false; }
 453
 454   return true;
 455 }