00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef __KGRID2D_H_
00021 #define __KGRID2D_H_
00022
00023 #include <math.h>
00024
00025 #include <qpair.h>
00026 #include <qvaluelist.h>
00027 #include <qvaluevector.h>
00028
00029 #include <kglobal.h>
00030
00031
00032
00033 namespace KGrid2D
00034 {
00039 typedef QPair<int, int> Coord;
00040
00045 typedef QValueList<Coord> CoordList;
00046 }
00047
00048 inline KGrid2D::Coord
00049 operator +(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00050 return KGrid2D::Coord(c1.first + c2.first, c1.second + c2.second);
00051 }
00052
00053 inline KGrid2D::Coord
00054 operator -(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00055 return KGrid2D::Coord(c1.first - c2.first, c1.second - c2.second);
00056 }
00057
00062 inline KGrid2D::Coord
00063 maximum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00064 return KGrid2D::Coord(kMax(c1.first, c2.first), kMax(c1.second, c2.second));
00065 }
00070 inline KGrid2D::Coord
00071 minimum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00072 return KGrid2D::Coord(kMin(c1.first, c2.first), kMin(c1.second, c2.second));
00073 }
00074
00075 inline QTextStream &operator <<(QTextStream &s, const KGrid2D::Coord &c) {
00076 return s << '(' << c.second << ", " << c.first << ')';
00077 }
00078
00079 inline QTextStream &operator <<(QTextStream &s, const KGrid2D::CoordList &list)
00080 {
00081 for(KGrid2D::CoordList::const_iterator i=list.begin(); i!=list.end(); ++i)
00082 s << *i;
00083 return s;
00084 }
00085
00086
00087 namespace KGrid2D
00088 {
00095 template <class Type>
00096 class Generic
00097 {
00098 public:
00102 Generic(uint width = 0, uint height = 0) {
00103 resize(width, height);
00104 }
00105
00106 virtual ~Generic() {}
00107
00111 void resize(uint width, uint height) {
00112 _width = width;
00113 _height = height;
00114 _vector.resize(width*height);
00115 }
00116
00120 void fill(const Type &value) {
00121 for (uint i=0; i<_vector.count(); i++) _vector[i] = value;
00122 }
00123
00127 uint width() const { return _width; }
00131 uint height() const { return _height; }
00135 uint size() const { return _width*_height; }
00136
00140 uint index(const Coord &c) const {
00141 return c.first + c.second*_width;
00142 }
00143
00147 Coord coord(uint index) const {
00148 return Coord(index % _width, index / _width);
00149 }
00150
00154 const Type &at(const Coord &c) const { return _vector[index(c)]; }
00158 Type &at(const Coord &c) { return _vector[index(c)]; }
00162 const Type &operator [](const Coord &c) const { return _vector[index(c)]; }
00166 Type &operator [](const Coord &c) { return _vector[index(c)]; }
00167
00171 const Type &at(uint index) const { return _vector[index]; }
00175 Type &at(uint index) { return _vector[index]; }
00179 const Type &operator [](uint index) const { return _vector[index]; }
00183 Type &operator [](uint index) { return _vector[index]; }
00184
00188 bool inside(const Coord &c) const {
00189 return ( c.first>=0 && c.first<(int)_width
00190 && c.second>=0 && c.second<(int)_height );
00191 }
00192
00196 void bound(Coord &c) const {
00197 c.first = kMax(kMin(c.first, (int)_width-1), 0);
00198 c.second = kMax(kMin(c.second, (int)_height-1), 0);
00199 }
00200
00201 protected:
00202 uint _width, _height;
00203 QValueVector<Type> _vector;
00204 };
00205 }
00206
00207 template <class Type>
00208 QDataStream &operator <<(QDataStream &s, const KGrid2D::Generic<Type> &m) {
00209 s << (Q_UINT32)m.width() << (Q_UINT32)m.height();
00210 for (uint i=0; i<m.size(); i++) s << m[i];
00211 return s;
00212 }
00213
00214 template <class Type>
00215 QDataStream &operator >>(QDataStream &s, KGrid2D::Generic<Type> &m) {
00216 Q_UINT32 w, h;
00217 s >> w >> h;
00218 m.resize(w, h);
00219 for (uint i=0; i<m.size(); i++) s >> m[i];
00220 return s;
00221 }
00222
00223
00224 namespace KGrid2D
00225 {
00226
00227
00234 class SquareBase
00235 {
00236 public:
00240 enum Neighbour { Left=0, Right, Up, Down, LeftUp, LeftDown,
00241 RightUp, RightDown, Nb_Neighbour };
00242
00246 static double angle(Neighbour n) {
00247 switch (n) {
00248 case Left: return M_PI;
00249 case Right: return 0;
00250 case Up: return M_PI_2;
00251 case Down: return -M_PI_2;
00252 case LeftUp: return 3.0*M_PI_4;
00253 case LeftDown: return -3.0*M_PI_4;
00254 case RightUp: return M_PI_4;
00255 case RightDown: return -M_PI_4;
00256 case Nb_Neighbour: Q_ASSERT(false);
00257 }
00258 return 0;
00259 }
00260
00264 static Neighbour opposed(Neighbour n) {
00265 switch (n) {
00266 case Left: return Right;
00267 case Right: return Left;
00268 case Up: return Down;
00269 case Down: return Up;
00270 case LeftUp: return RightDown;
00271 case LeftDown: return RightUp;
00272 case RightUp: return LeftDown;
00273 case RightDown: return LeftUp;
00274 case Nb_Neighbour: Q_ASSERT(false);
00275 }
00276 return Nb_Neighbour;
00277 }
00278
00283 static bool isDirect(Neighbour n) { return n<LeftUp; }
00284
00288 static Coord neighbour(const Coord &c, Neighbour n) {
00289 switch (n) {
00290 case Left: return c + Coord(-1, 0);
00291 case Right: return c + Coord( 1, 0);
00292 case Up: return c + Coord( 0, -1);
00293 case Down: return c + Coord( 0, 1);
00294 case LeftUp: return c + Coord(-1, -1);
00295 case LeftDown: return c + Coord(-1, 1);
00296 case RightUp: return c + Coord( 1, -1);
00297 case RightDown: return c + Coord( 1, 1);
00298 case Nb_Neighbour: Q_ASSERT(false);
00299 }
00300 return c;
00301 }
00302 };
00303
00310 template <class T>
00311 class Square : public Generic<T>, public SquareBase
00312 {
00313 public:
00317 Square(uint width = 0, uint height = 0)
00318 : Generic<T>(width, height) {}
00319
00327 CoordList neighbours(const Coord &c, bool insideOnly = true,
00328 bool directOnly = false) const {
00329 CoordList neighbours;
00330 for (uint i=0; i<(directOnly ? LeftUp : Nb_Neighbour); i++) {
00331 Coord n = neighbour(c, (Neighbour)i);
00332 if ( insideOnly && !Generic<T>::inside(n) ) continue;
00333 neighbours.append(n);
00334 }
00335 return neighbours;
00336 }
00337
00344 Coord toEdge(const Coord &c, Neighbour n) const {
00345 switch (n) {
00346 case Left: return Coord(0, c.second);
00347 case Right: return Coord(Generic<T>::width()-1, c.second);
00348 case Up: return Coord(c.first, 0);
00349 case Down: return Coord(c.first, Generic<T>::height()-1);
00350 case LeftUp: return Coord(0, 0);
00351 case LeftDown: return Coord(0, Generic<T>::height()-1);
00352 case RightUp: return Coord(Generic<T>::width()-1, 0);
00353 case RightDown: return Coord(Generic<T>::width()-1, Generic<T>::height()-1);
00354 case Nb_Neighbour: Q_ASSERT(false);
00355 }
00356 return c;
00357 }
00358 };
00359
00360
00372 class HexagonalBase
00373 {
00374 public:
00378 enum Neighbour { Left = 0, Right, LeftUp, LeftDown,
00379 RightUp, RightDown, Nb_Neighbour };
00380
00384 static double angle(Neighbour n) {
00385 switch (n) {
00386 case Left: return M_PI;
00387 case Right: return 0;
00388 case LeftUp: return 2.0*M_PI/3;
00389 case LeftDown: return -2.0*M_PI/3;
00390 case RightUp: return M_PI/3;
00391 case RightDown: return -M_PI/3;
00392 case Nb_Neighbour: Q_ASSERT(false);
00393 }
00394 return 0;
00395 }
00396
00400 static Neighbour opposed(Neighbour n) {
00401 switch (n) {
00402 case Left: return Right;
00403 case Right: return Left;
00404 case LeftUp: return RightDown;
00405 case LeftDown: return RightUp;
00406 case RightUp: return LeftDown;
00407 case RightDown: return LeftUp;
00408 case Nb_Neighbour: Q_ASSERT(false);
00409 }
00410 return Nb_Neighbour;
00411 }
00412
00416 static Coord neighbour(const Coord &c, Neighbour n) {
00417 bool oddRow = c.second%2;
00418 switch (n) {
00419 case Left: return c + Coord(-1, 0);
00420 case Right: return c + Coord( 1, 0);
00421 case LeftUp: return c + (oddRow ? Coord( 0, -1) : Coord(-1, -1));
00422 case LeftDown: return c + (oddRow ? Coord( 0, 1) : Coord(-1, 1));
00423 case RightUp: return c + (oddRow ? Coord( 1, -1) : Coord( 0, -1));
00424 case RightDown: return c + (oddRow ? Coord( 1, 1) : Coord( 0, 1));
00425 case Nb_Neighbour: Q_ASSERT(false);
00426 }
00427 return c;
00428 }
00429
00433 static uint distance(const Coord &c1, const Coord &c2) {
00434 return kAbs(c1.first - c2.first) + kAbs(c1.second - c2.second)
00435 + (c1.first==c2.first || c1.second==c2.second ? 0 : -1);
00436 }
00437 };
00438
00450 template <class Type>
00451 class Hexagonal : public Generic<Type>, public HexagonalBase
00452 {
00453 public:
00457 Hexagonal(uint width = 0, uint height = 0)
00458 : Generic<Type>(width, height) {}
00459
00466 CoordList neighbours(const Coord &c, bool insideOnly = true) const {
00467 CoordList neighbours;
00468 for (uint i=0; i<Nb_Neighbour; i++) {
00469 Coord n = neighbour(c, (Neighbour)i);
00470 if ( insideOnly && !Generic<Type>::inside(n) ) continue;
00471 neighbours.append(n);
00472 }
00473 return neighbours;
00474 }
00475
00476
00485 CoordList neighbours(const Coord &c, uint distance, bool all,
00486 bool insideOnly = true) const {
00487
00488 CoordList ring;
00489 if ( distance==0 ) return ring;
00490 ring = neighbours(c, insideOnly);
00491 if ( distance==1 ) return ring;
00492 CoordList center;
00493 center.append(c);
00494 for (uint i=1; i<distance; i++) {
00495 CoordList newRing;
00496 CoordList::const_iterator it;
00497 for (it=ring.begin(); it!=ring.end(); ++it) {
00498 CoordList n = neighbours(*it, insideOnly);
00499 CoordList::const_iterator it2;
00500 for (it2=n.begin(); it2!=n.end(); ++it2)
00501 if ( center.find(*it2)==center.end()
00502 && ring.find(*it2)==ring.end()
00503 && newRing.find(*it2)==newRing.end() )
00504 newRing.append(*it2);
00505 center.append(*it);
00506 }
00507 ring = newRing;
00508 }
00509 if ( !all ) return ring;
00510 CoordList::const_iterator it;
00511 for (it=ring.begin(); it!=ring.end(); ++it)
00512 center.append(*it);
00513 center.remove(c);
00514 return center;
00515 }
00516 };
00517
00518 }
00519
00520 #endif