Пространственная индексация 2D-карты с использованием шаблонов C++ для любой фигуры

Question

У меня есть шаблон класса для пространственной индексации, который по умолчанию должен работать для любого 2d-объекта, который реализует функцию 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. Я хочу научиться эффективно использовать шаблоны

Этот вопрос относится к этому " Родовому дереву ", где рекомендуется использовать шаблоны для аналогичной задачи. Пытался реализовать это... но я, возможно, мое понимание шаблонов не достаточно хорошо.

ПРИМЕЧАНИЕ: мой GridMap2d не является QuadTree, но я все же добавил 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 ){ ... }
};

Кстати, inline Ключевое слово не имеет никакого эффекта при использовании в объявлении класса.