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