c++ - 使用 C++ 模板对任何形状进行空间索引 2D map

Question

我有 spatial indexing 的模板类默认情况下，它适用于任何实现函数 void boundingBox( Rect2d * box ) 的二维对象使用 std::vector<OBJECT*>作为插入特定网格瓦片中的对象的容器。

template <class OBJECT, class TILE = std::vector<OBJECT*> >
class GridMap2D {

public:
double    step, invStep;
int       nx, ny, nxy;
TILE *    tiles;

// ==== functions

inline int getIx( double x ){ return (int)( invStep * x ); };
inline int getIy( double y ){ return (int)( invStep * y ); };

inline double getX( int ix ){ return step * ix ; };
inline double getY( int iy ){ return step * iy ; };

inline int getIndex ( int ix,   int iy   ){ return nx*iy + ix;                     };
inline int getIndex ( double x, double y ){ return getIndex( getIx(x), getIy(y) ); };
inline TILE* getTile( double x, double y ){ return  tiles + getIndex( x, y );      };

inline void insert( OBJECT* p, int i ){
    tiles[ i ].push_back( p );
}
inline void insert( OBJECT* p, int ix, int iy ){ insert( p, getIndex( ix,iy ) ); };

// this is very general method to insert any object with bounding box
// but for many object it is not very efficient
// some objects suchb as Point2d does not even implement boundingBox()
inline void insert( OBJECT* p ){
    Rect2d bbox;
    p.boundingBox( &bbox );
    int ix0 = getIx( bbox.x0 ); // TODO: bound check ?
    int iy0 = getIy( bbox.y0 );
    int ix1 = getIx( bbox.x1 );
    int iy1 = getIy( bbox.y1 );
    for( int iy=iy0; iy<=iy1; iy++ ){
        for( int ix=ix0; ix<=ix1; ix++ ){
            insert( p, ix, iy );
        }
    }
}

void init( int nx_, int ny_, double step_, int tile_n0 ){
    step    = step_;
    invStep = 1/step;
    nx = nx_; ny=ny_;
    nxy = nx*ny;
    tiles  = new TILE[ nxy ];
    for (int i=0; i<nxy; i++){
        if ( tile_n0 != 0 ){
            tiles[i].reserve( tile_n0 );
        }
    }
}

};

及其对 Segment2d 的特化没有实现 boundingBox()但有自己的insert基于线光栅化的算法:

template<> class GridMap2D< Segment2d, std::vector<Segment2d*> >{
public:
inline void insert( Segment2d* l ){
    Vec2d* a = l->a;
    Vec2d* b = l->b;
    double ax  = a->x;
    double ay  = a->y;
    double bx  = b->x;
    double by  = b->y;

    double dx = fabs( bx - ax );
    double dy = fabs( by - ay );
    int dix = ( ax < bx ) ? 1 : -1;
    int diy = ( ay < by ) ? 1 : -1;
    int ix    = getIx( ax );
    int iy    = getIy( ay );
    int ixb   = getIx( bx );
    int iyb   = getIy( by );
    double x=0, y=0;
    int i=0;
    insert( l, ix, iy   );
    insert( l, ixb, iyb );
    while ( ( ix != ixb ) && ( iy != iyb  ) ) {
        if ( x < y ) {
            x  += dy;
            ix += dix;
        } else {
            y  += dx;
            iy += diy;
        }
        insert( l, ix, iy );
    }
}

};

这将把线插入到它经过的网格瓦片槽中......像这样:

但我对模板的工作方式有几个问题:

1. 特化Segment2d我得到了 error: ‘getIx’ was not declared in this scope .这是否意味着专用模板不知道基本模板中定义的功能？或者我可能错误地进行了特化。我真的不想多次重写代码，那么模板方法就没有意义了。

2. 我不确定当我通过一些参数实例化或专门化模板时会发生什么，这些参数没有实现基本模板使用的某些方法。例如

   1. 考虑我使用不同的容器类型参数作为 TILE没有实现 .push_back()
   2. 我的 Segment2d不执行 boundingBox()特化能解决这个问题吗？

---

背景:

我有两个目标:

1. 我想创建非常快速的空间索引，以加速任何二维形状的光线转换和碰撞。

   • 因为它应该尽可能快，所以我想使用模板(在编译时解决)而不是使用 virtual 的一些类继承层次结构方法。

2. 我想学习如何有效地使用模板

这个问题与这个“Generic Quadtree”有关，建议使用模板来完成类似的任务。试图实现它......但我可能对模板的理解还不够好。

注意:我的 GridMap2d 不是 QuadTree，但我仍然添加了 QuadTree 作为关键字，因为问题与其相关。四叉树是非常常见的空间索引数据结构，使用模板实现它会遇到同样的问题。

Answer 1

“我真的不想多次重写代码，那么模板方法就没有意义了。”

当您专门化一个类时，您不会“继承”任何成员字段或方法。所以你需要一些特殊的技巧来得到你想要的。

您可以做的实际上是将 insert() 方法的行为移动到一个单独的模板类中。这样，当您专门化该类的行为时，您最终不会破坏其他字段和方法。这需要对您的代码进行一些巧妙的重组。

我认为这段代码应该可以完成这项工作:

struct GridMap2D_base {
  double    step, invStep;
  int       nx, ny, nxy;

  int getIx( double x ) const { return (int)( invStep * x ); };
  int getIy( double y ) const { return (int)( invStep * y ); };

  double getX( int ix ) const { return step * ix ; };
  double getY( int iy ) const { return step * iy ; };

  int getIndex ( int ix,   int iy   ) const { return nx*iy + ix;                     };
  int getIndex ( double x, double y ) const { return getIndex( getIx(x), getIy(y) ); };
};

struct PushBackHelper {
  // add versions of this for std::list, etc., as needed
  template <typename OBJECT>
  static void push_back(std::vector<OBJECT*>& tile, OBJECT* p) {
    tile.push_back(p);
  }
};

template<typename OBJECT>
struct InsertAlgorithm {
  int ix0, iy0, ix1, iy1, ix, iy;

  InsertAlgorithm(const GridMap2D_base& base, OBJECT* p) {
    Rect2d bbox;
    p->boundingBox( &bbox );
    ix0 = base.getIx( bbox.x0 ); // TODO: bound check ?
    iy0 = base.getIy( bbox.y0 );
    ix1 = base.getIx( bbox.x1 );
    iy1 = base.getIy( bbox.y1 );
    ix = 0;
    iy = 0;
  }

  bool should_preinsert1(const GridMap2D_base& base, int& ix2, int& iy2) { return false; }
  bool should_preinsert2(const GridMap2D_base& base, int& ix2, int& iy2) { return false; }

  bool should_insert(const GridMap2D_base& base, int& ix2, int& iy2)
  {
    while (ix<=ix1) {
      ix2 = ix;
      iy2 = iy;
      ix++;
      return true;
    }
    iy++;
    if (iy>iy1) return false;
    ix = 0;
    return should_insert(base, ix2, iy2);
  }
};

template<> struct InsertAlgorithm<Segment2d> {
  Vec2d* a;
  Vec2d* b;
  double ax, ay, bx, by, dx, dy, x, y;
  int dix, diy, ix, iy, ixb, iyb;

  InsertAlgorithm(const GridMap2D_base& base, Segment2d* l) {
    a = l->a;
    b = l->b;
    ax  = a->x;
    ay  = a->y;
    bx  = b->x;
    by  = b->y;
    x = 0;
    y = 0;

    dx = fabs( bx - ax );
    dy = fabs( by - ay );
    dix = ( ax < bx ) ? 1 : -1;
    diy = ( ay < by ) ? 1 : -1;
    ix    = base.getIx( ax );
    iy    = base.getIy( ay );
    ixb   = base.getIx( bx );
    iyb   = base.getIy( by );
  }

  bool should_preinsert1(const GridMap2D_base& base, int& ix2, int& iy2) {
    ix2 = ix;
    iy2 = iy;
    return true;
  }

  bool should_preinsert2(const GridMap2D_base& base, int& ix2, int& iy2) {
    ix2 = ixb;
    iy2 = iyb;
    return true;
  }

  bool should_insert(const GridMap2D_base& base, int& ix2, int& iy2)
  {
    if (ix==ixb && iy==iyb) return false;

    if ( x < y ) {
      x  += dy;
      ix += dix;
    } else {
      y  += dx;
      iy += diy;
    }

    ix2 = ix;
    iy2 = iy;
    return true;
  }
};

template<class OBJECT, typename TILE=std::vector<OBJECT*> >
class GridMap2D : public GridMap2D_base {
public:
  TILE* tiles;

  TILE* getTile( double x, double y ){ return  tiles + getIndex( x, y );      };

  void insert( OBJECT* p ){
    InsertAlgorithm<OBJECT> algo(*this, p);
    int ix = 0;
    int iy = 0;
    if (algo.should_preinsert1(*this, ix, iy)) {
      PushBackHelper::push_back(tiles[getIndex(ix, iy)], p);
    }
    if (algo.should_preinsert2(*this, ix, iy)) {
      PushBackHelper::push_back(tiles[getIndex(ix, iy)], p);
    }
    while (algo.should_insert(*this, ix, iy)) {
      PushBackHelper::push_back(tiles[getIndex(ix, iy)], p);
    }
  }

  void init( int nx_, int ny_, double step_, int tile_n0 ){ ... }
};

顺便说一下，the inline keyword has no effect when used within the class declaration .