Здравствуйте Albatross, Вы писали:
(Вопрос об организации поиска пересечений геометрических примитивов.)

Мультиметоды — одна из фундаментальных проблем C++. Она поднимается в различных форумах и группах новостей с завидной регулярностью. Эту проблему упоминает Страуструп в книге "Дизайн и эволюция языка C++", ей уделяет внимание Скотт Мейерс в "Наиболее эффективном использовании C++", не обходит ее стороной и модный Андрей Александреску в "Modern C++ Design". Более того, существует даже несколько специальных библиотек и расширений для C++, предназначенных для решения подобных задач (поиск в Google по словам "C++ multimethods").

На сегодняшний день можно выделить три способа решения задач связанных с множественной диспетчеризацией, и, в частности, поиска пересечений.

1. RTTI
   

   class Primitive { public: virtual ~Primitive(); ... };
   class Polygon : public Primitive { ... };
   class Line : public Primitive { ... };
   class Point : public Primitive { ... };
   
   bool overlap(const Polygon&, const Polygon&);
   bool overlap(const Polygon&, const Line&);
   bool overlap(const Polygon&, const Point&);
   bool overlap(const Line&, const Line&);
   bool overlap(const Line&, const Point&);
   
   bool overlap(const Primitive& pri1, const Primitive& pri1)
   {
     if (const Polygon* polygon1 = dynamic_cast<const Polygon*>(&pri1))
     {
       if (const Polygon* polygon2 = dynamic_cast<const Polygon*>(&pri2))
          return overlap(*polygon1, *polygon2);
       if (const Line* line2 = dynamic_cast<const Line*>(&pri2))
          return overlap(*polygon1, *line2);
       if (const Point* point2 = dynamic_cast<const Point*>(&pri2))
          return overlap(*polygon1, *point2);
       throw Exception("unknow geometric primitive type");
     }
     if (const Line* line1 = dynamic_cast<const Line*>(&pri1))
     {
       if (const Polygon* polygon2 = dynamic_cast<const Polygon*>(&pri2))
          return overlap(*polygon2, *line1);
       if (const Line* line2 = dynamic_cast<const Line*>(&pri2))
          return overlap(*line1, *line2);
       if (const Point* point2 = dynamic_cast<const Point*>(&pri2))
          return overlap(*line1, *point2);
       throw Exception("unknow geometric primitive type");
     }
     if (const Point* point1 = dynamic_cast<const Point*>(&pri1))
     {
       if (const Polygon* polygon2 = dynamic_cast<const Polygon*>(&pri2))
          return overlap(*polygon2, *point1);
       if (const Line* line2 = dynamic_cast<const Line*>(&pri2))
          return overlap(*line2, *point1);
       if (const Point* point2 = dynamic_cast<const Point*>(&pri2))
          return overlap(*point1, *point2);
       throw Exception("unknow geometric primitive type");
     }
     throw Exception("unknow geometric primitive type");
   }

   
   
   • Достоинства: хорошая поддержка со стороны языка, возможность поиска пересечений объектов унаследованных классов, сравнительно легко добавлять новые примитивы (код "диспетчера" можно локализовать в одной функции).
     
   • Недостатки: производительность.
2. Двойная виртуализация
   

   class Primitive
   {
   public:
     virtual ~Primitive();
     virtual bool overlaps(const Primitive&) = 0;
     virtual bool overlaps(const Polygon&) = 0;
     virtual bool overlaps(const Line&) = 0;
     virtual bool overlaps(const Point&) = 0;
   };
   
   class Polygon : public Primitive
   {
   public:
     virtual bool overlaps(const Primitive& pri)
     {
       return pri.overlaps(*this);
     }
     virtual bool overlaps(const Polygon&);
     virtual bool overlaps(const Line&);
     virtual bool overlaps(const Point&);
   };
   
   class Line : public Primitive
   {
   public:
     virtual bool overlaps(const Primitive& pri)
     {
       return pri.overlaps(*this);
     }
     virtual bool overlaps(const Polygon&);
     virtual bool overlaps(const Line&);
     virtual bool overlaps(const Point&);
   };
   
   class Point : public Primitive
   {
   public:
     virtual bool overlaps(const Primitive& pri)
     {
       return pri.overlaps(*this);
     }
     virtual bool overlaps(const Polygon&);
     virtual bool overlaps(const Line&);
     virtual bool overlaps(const Point&);
   };

   
   
   • Достоинства: наглядность, хорошая поддержка со стороны языка, возможность поиска пересечений объектов унаследованных классов, производительность выше, чем в (1).
     
   • Недостатки: неудобство расширения (все знают про всех, код поиска пересечений размазан по всем классам, добавление нового примитива требует модификации остальных).
3. Матрица указателей на функции пересечения примитивов по идентификаторам, хранящимся в объекте (ad hoc rtti).
   

   class Primitive
   {
   public:
     int id() const;
   
   protected:
     Primitive(int id);
   
     ...
   };
   
   class Polygon : public Primitive
   {
   public:
     Polygon() : Primitive(0) { }
   };
   
   class Line : public Primitive
   {
   public:
     Line() : Primitive(1) { }
   };
   
   class Point : public Primitive
   {
   public:
     Point() : Primitive(2) { }
   };
   
   bool overlap_polygon_polygon(const Polygon&, const Polygon&);
   bool overlap_polygon_line(const Polygon&, const Polygon&);
   bool overlap_polygon_point(const Polygon&, const Polygon&);
   bool overlap_line_polygon(const Polygon&, const Polygon&);
   bool overlap_line_line(const Polygon&, const Polygon&);
   bool overlap_line_point(const Polygon&, const Polygon&);
   bool overlap_point_polygon(const Polygon&, const Polygon&);
   bool overlap_point_line(const Polygon&, const Polygon&);
   bool overlap_point_point(const Polygon&, const Polygon&);
   
   typedef bool OverlapFunction(const Polygon&, const Polygon&);
   
   OverlapFunction* overlappers [3][3] = 
   {
     { overlap_polygon_polygon, overlap_polygon_line, overlap_polygon_point },
     { overlap_line_polygon,    overlap_line_line,    overlap_line_point },
     { overlap_point_polygon,   overlap_point_line,   overlap_point_point },
   };
   
   bool overlap(const Primitive& pri1, const Primitive& pri1)
   {
     return overlappers[pri1.id()][pri2.id()](pri1, pri2);
   }

   
   
   • Достоинства: максимальная производительность, возможность добавления поиска пересечений новых примитивов без модификации исходных классов.
     
   • Недостатки: слабая интеграция с языком, в частности, невозможность поиска пересечений объектов унаследованных классов, необходимость поддержания набора уникальных идентификаторов.

Для real-time с приличным количеством примитивов
подходят только (2) и (3).

Здравствуйте Павел Кузнецов!

Добавлю к сказанному о мультиметодах.

Третий способ дает квадратичный рост сложности.

Для лучшей масштабируемости (и обхода проблемы с матрицей функций) используют ранжирование.

Принцип двойной передачи
1) передача абстрактному объекту_1 абстрактного объекта_2
2) передача абстрактному объекту_2 конкретного объекта_1

Причем объект_2 должен знать о классе объекта_1 и иметь соответствующую сигнатуру.

То есть, объект_2 имеет ранг, равный или больший, чем ранг объекта_1.

Замечу, что равенство рангов не требует совпадения классов.
Например, несколько классов могут знать друг о друге.

class Class71;
class Class72;
class Class73;

class Class71
{
public:
  int rank() const { return 7; }

  int op(Class71* another);
  int op(Class72* another);
  int op(Class73* another);
};
class Class72
{
public:
  int rank() const { return 7; }

  int op(Class71* another);
  int op(Class72* another);
  int op(Class73* another);
};
class Class73
{
public:
  int rank() const { return 7; }

  int op(Class71* another);
  int op(Class72* another);
  int op(Class73* another);
};

Таким образом, если потребовать, чтобы объекты старшего ранга имели сигнатуры методов для обработкм объектов всех младших рангов, то вводим тройную диспетчеризацию.

1) ранжирование
2) первый пас — интерфейсу объекта младшего ранга
3) второй пас — младший объект вызывает интерфейс старшего

class ClassBase
{
public:
  virtual int rank() const = 0;

  // первый пас - ранжирование
  // рассмотрим для некоммутативных функций
  // поскольку для коммутативных или антикоммутативных будет в 2 раза меньше кода

  int left_op_pass1(ClassBase* right) // не виртуальная
  {
    if(this->rank() < right->rank())
      return this->left_op_pass2(right);
    else
      return right->right_op_pass2(this);
  }

  virtual int left_op_pass2(ClassBase* right) = 0;
  virtual int right_op_pass2(ClassBase* left) = 0;
  // пример некоммутативной функции : разность множеств A\B != B\A

  // коммутативная функция (например, сложение) : A+B == B+A
  virtual int right_op_pass2(ClassBase* left) { return left_op_pass2(left); }

  // антикоммутативная функция : A/B == 1/(B/A)
  virtual int right_op_pass2(ClassBase* left) { return invert(left_op_pass2(left); }
};

class Class1a;
class Class1b;
class ClassBase1 : public ClassBase // объекты одного ранга имеют общую базу!!!
{
public:
  int rank() const { return 1; }

  virtual int left_op_pass3(Class1a* right) = 0;
  virtual int left_op_pass3(Class1b* right) = 0;

  virtual int right_op_pass3(Class1a* left) = 0;
  virtual int right_op_pass3(Class1b* left) = 0;
};

class Class1a : public ClassBase1
{
  virtual int left_op_pass2(ClassBase* right)
  { static_cast<ClassBase1*>(right)->right_op_pass3(this); }
  virtual int right_op_pass2(ClassBase* right)
  { static_cast<ClassBase1*>(right)->left_op_pass3(this); }

...
};

...

// заметим, что классы 1a, 1b не знают про нововведение

class Class2c;
class Class2d;
class ClassBase2 : public ClassBase1 // добавлена поддержка новых классов
// одиночное наследование от предыдущей базы, чтобы младшие объекты могли
// вызывать static_cast<ClassBase1*>(right)->left_op_pass3(this);
{
public:
  int rank() const { return 2; }

  virtual int left_op_pass3(Class1a* right) = 0;
  virtual int left_op_pass3(Class1b* right) = 0;
  virtual int left_op_pass3(Class1c* right) = 0;
  virtual int left_op_pass3(Class1d* right) = 0;

  virtual int right_op_pass3(Class1a* left) = 0;
  virtual int right_op_pass3(Class1b* left) = 0;
  virtual int right_op_pass3(Class1c* left) = 0;
  virtual int right_op_pass3(Class1d* left) = 0;
};

class Class2c : public ClassBase2
{
  virtual int left_op_pass2(ClassBase* right)
  {
    assert(right->rank() >= 2);
    // объект должен знать меня, и, следовательно, наследовать от ClassBase2
    static_cast<ClassBase2*>(right)->right_op_pass3(this);
  }
  virtual int right_op_pass2(ClassBase* right)
  { static_cast<ClassBase1*>(right)->left_op_pass3(this); }

...
};

Пример вызова

Class2c* obj2c;
Class1a* obj1a;

obj2c->left_op_pass1( (ClassBase*)obj1a ) ==>
  
  if(obj1a->rank() < obj2c->rank())
  return obj1a->left_op_pass2( (ClassBase*)obj2c ) ==>

    return ((ClassBase1*)obj2c)->left_op_pass3( (Class1a*)obj1a ) ==>

      ((Class2a*)obj2c)->left_op_pass3( (Class1a*)obj1a )
      HAPPY END!

В результате, конечно, получается RTTI ad hoc... Но, к счастью, не таблица виртуальных функций вручную (а матрицы функций — именно это и есть!)

Подобный фокус можно провернуть с множественными интерфейсами — в стиле COM.
Там роль ранга будут играть идентификаторы интерфейсов классов-баз (ClassBase1, ClassBase2...)
Каждая новая версия библиотеки должна будет поддерживать предыдущую.

Здравствуйте Albatross, Вы писали:

A>Представьте себе ситуацию...

Если тебя интересует в первую очередь объектная модель, а не эффективность, то можно ввести объект описывающие фигуру не в её родных примитивах (окружностях, длинах, углах), а неких универсальных (возможно даже для частного случая) примитивах (например, точках и/или векторах). Все твои объекты должны уметь создавать/заполнять такие объекты (назовём их регионы), ну а алгоритмы пересечения нужно делать уже для регионов.

Этот подход будет работать для любых типов твоих фигур при минимальных затратах. К тому же для реализации других алгоритмов тебе уже не нужно будет сильно напрягаться, достаточно будет его реализовать только для регионов.

Представьте себе ситуацию — есть у меня абстрактный класс Geometry , под которым мы понимаем некоторый геметрический объект. От него наследуются классы Point, Line , ну и Polygon. В Geometry определён абстрактный виртуальный метод BOOL Geometry::IsOverlap (Geometry * AnotherGeometry), который просто показывает, есть ли у этих объектов общие точки. Есть своя реализация этого метода в каждом из потомков — то есть в классах Point, Line и Polygon. Но тут возникает следующая проблема. Класс Polygon, в принципе, должен знать только о себе, то есть он сможет определить, пересекается ли он с другим полигоном. А как же быть с остальными фигурами? Можно, конечно, в каждом классе выяснять, что за объект туда поступает и на основе этого вычислять, пересекается или нет. Но тогда получается, что если мы сделаем замену в классе полигона, то придётся переписывать все остальные классы. Каким образом надо действовать? Как реализовывать этот метод? Помогите советом! :???:

Здравствуйте Павел Кузнецов, Вы писали:

J>>недостаток размазанности решаются введением класса-хелпера, в который, собственно, и выносится весь код определения пересечения.

ПК>Класс-helper здесь даже не нужен: можно вызывать соответствующую функцию из набора функций поиска пересечений. Основная проблема, однако, не решается: размазанность диспетчеризации. При добавлении новых примитивов все равно требуется модификация всех остальных.

Ну, как показано выше, -- модификация всех необязательна. С использованием тройной диспетчеризации.
Хотя это и эротично...

Хелперы могут пригодиться для
1) составных регионов (например, что получится при пересечении сектора с многоугольником?)
2) капсулирования отдельных операций (ведь для N классов потребуется как минимум N(N+1) сигнатур одной бинарной операции).

По сути, хелперы выступают интерфейсами одной функции.
Кроме того, упрощается работа с некоммутативными, n-арными и т.д. функциями.

class Primitive;

class BinaryOp
{
public:
  virtual int rank() const = 0;

  Primitive* perform(Primitive* p1, Primitive* p2) = 0;
};

class Primitive
{
public:
  virtual const BinaryOp* intersector() const = 0;
  virtual const BinaryOp* combinator() const = 0;
};

Primitive* combine(Primitive* p1, Primitive* p2)
{
  const BinaryOp* c1 = p1->combinator();
  const BinaryOp* c2 = p2->combinator();

  if(c1->rank() >= c2->rank())
    return c1->perform(p1, p2);
  else
    return c2->perform(p1, p2);
}

Здравствуйте Павел Кузнецов, Вы писали:

ПК>(Вопрос об организации поиска пересечений геометрических примитивов.)

ПК>На сегодняшний день можно выделить три способа решения задач связанных с множественной диспетчеризацией, и, в частности, поиска пересечений.

ПК>

Двойная виртуализация
ПК>

ПК>class Primitive
ПК>{
ПК>public:
ПК>  virtual ~Primitive();
ПК>  virtual bool overlaps(const Primitive&) = 0;
ПК>  virtual bool overlaps(const Polygon&) = 0;
ПК>  virtual bool overlaps(const Line&) = 0;
ПК>  virtual bool overlaps(const Point&) = 0;
ПК>};

ПК>class Polygon : public Primitive
ПК>{
ПК>public:
ПК>  virtual bool overlaps(const Primitive& pri)
ПК>  {
ПК>    return pri.overlaps(*this);
ПК>  }
ПК>  virtual bool overlaps(const Polygon&);
ПК>  virtual bool overlaps(const Line&);
ПК>  virtual bool overlaps(const Point&);
ПК>};

ПК>class Line : public Primitive
ПК>{
ПК>public:
ПК>  virtual bool overlaps(const Primitive& pri)
ПК>  {
ПК>    return pri.overlaps(*this);
ПК>  }
ПК>  virtual bool overlaps(const Polygon&);
ПК>  virtual bool overlaps(const Line&);
ПК>  virtual bool overlaps(const Point&);
ПК>};

ПК>class Point : public Primitive
ПК>{
ПК>public:
ПК>  virtual bool overlaps(const Primitive& pri)
ПК>  {
ПК>    return pri.overlaps(*this);
ПК>  }
ПК>  virtual bool overlaps(const Polygon&);
ПК>  virtual bool overlaps(const Line&);
ПК>  virtual bool overlaps(const Point&);
ПК>};
ПК>

ПК>

ПК>
• Достоинства: наглядность, хорошая поддержка со стороны языка, возможность поиска пересечений объектов унаследованных классов, производительность выше, чем в (1).
  ПК>
• Недостатки: неудобство расширения (все знают про всех, код поиска пересечений размазан по всем классам, добавление нового примитива требует модификации остальных).
  ПК>

извиняюсь за столь обильную цитату
я писал в http://www.rsdn.ru/forum/message.asp?mid=51829&only

Автор: jazzer
Дата: 06.05.02

, что недостаток размазанности решаются введением класса-хелпера, в который, собственно, и выносится весь код определения пересечения.

Более того, имеет смысл предусмотреть общий механизм пересечения просто фигур через их общее представление в виде тех же регионов, напрмер.
Тогда введение новой фигуры не затронет старых пользователей, а новые получат уже новый специально для нее определенный механизм определения пересечения.
Более того, мы можем легко устраивать наследование и решать эти проблемы через него. Скажем, мы введем примитив Circle и объявим новые классы-наследники для существующих примитивов, которые будут отличаться от предков только тем, что будут уметь пересекаться с окружностями. тогда старые пользователи, которые ничего не знают о существовании окружностей, так и будут использовать старые классы, а новые будут использовать новые.
Причем правильнее всего пользоваться каким-нть typedef'ом, чтобы иметь возможность оперативно переключать тип примитива с предка на его более умного потомка.

В общем, я за двойную диспетчеризацию (или виртуализацию)

You will always get what you always got
  If you always do  what you always did

Здравствуйте Курилка, Вы писали:

К>Здравствуйте Аноним, Вы писали:

А>>Здравствуйте Курилка, Вы писали:

К>>>Здравствуйте Dima2, Вы писали:

D>>>>Здравствуйте Рома, Вы писали:

D>>>>Ребята, а чего вы пытаетесь засунуть этот вопрос в алгоритмы.
D>>>>По моему с чисткой рядов не надо перебарщивать, ведь вопрос касается объектной модели системы классов, чего вы его сунете в алгоритмы :no:

К>>>вообще-то я не знал куда его пихать, как бы к c++ он прямого-то отношения не имеет, скорее его бы в проектирование, но там какие-то не совсем те темы, т.е. даже скорее в прочее, хотя ИМХО проблема в данном случае отчасти лежит в алгоритме как раз.


А>>Меня интересует имеено ОБЪЕКТНАЯ МОДЕЛЬ....
А>>то есть как надо делать — какие классы и всё такое..
А>>дело даже не в алгоритме пересечения

К>Ну если так подходить, то с объектной моделью у тебя всё в порядке...
К>Другое дело, что такая абстрактная модель очень плохо работает, когда ты пытаешься реализовать
К>алгоритм, необходимый в ней.
К>Т.е. нельзя строить иерархию классов и интерфейсов не беря в рассчёт механизмы их взаимодействия (т.е. алгоритмы).

К>Что-то на ночь глядя в теорию потянуло...




Ну хорошо, предлагается сделать так — завести класс интерфейса, который будет заниматься пресечением. И типа там будет одна функция, коотрая принимает 2 указателя на базовый класс. Потом она выясняет, что за объекты и уже, основываясь на этих фактах нахродит пересечение. Правильно?

Здравствуйте Albatross, Вы писали:

Каким образом надо действовать? Как реализовывать этот метод? Помогите советом!

Я недавно столкнулся с похожей проблемой. Не смог придумать ничего лучше, чем создать обьект, который хранит список всех фигур (в моём случае это иконки). Можно добавить в базовый класс виртуальную функцию GetRegion, которая возвращала бы HRGN. Потом для необходимой пары фигур вызывать

int CombineRgn(
  HRGN hrgnDest,      // handle to destination region
  HRGN hrgnSrc1,      // handle to source region
  HRGN hrgnSrc2,      // handle to source region
  int fnCombineMode   // region combining mode
);

где fnCombibeMode = RGN_AND
В результате получится многоугольник пересечения.
Если функция вернёт NULLREGION, то пересечения нет.
Другое дело, если ты пишешь без использования API, тогда тебе придётся реализовать функции проверки самостоятельно

Здравствуйте The Lex, Вы писали:

TL>Здравствуйте Кодт, Вы писали:

К>>Здравствуйте Павел Кузнецов!

К>>Добавлю к сказанному о мультиметодах...

TL>А теперь бы все это в статейку оформить, а?

TL>P.S. Сижу и думаю: кому же первому ответ отправить: Кузнецову или Кодту?

Ничто не ново под луной...

Журнал "Открытые Системы" март 2002.
"ООП, мультиметоды и пирамидальная эволюция"
http://www.osp.ru/os/2002/03/041.htm

Здравствуйте Рома, Вы писали:

A>>>вот мне что посоветовали :
A>>>"в таких случаях испольуется double dispatching

A>>>возражение о том, что если перепишется Полигон, то придется переписывать реализации методов пересечения
A>>>bool Line::overlaps(const Polygon& f)
A>>>не специфичен для обсуждаемой задачи, это — общая проблема изменения интерфейса при наличии классов, которые от этого интерфейса зависят (что всегда будет, иначе зачем нужны такие классы :) )

IT>>В этом случае каждый должен знать о каждом. Это будет работать эффективно, но сложность программы будет расти в прогрессии с каждой новой добавляемой фигурой.

Р>Да и переписывать уже готовый код при добавлении новой фигуры или исправлении старой не очень-то :no:
Р>Чем меньше классы знают друг о друге, тем лучше.

Согласен абсолютно.
Это, вроде как, очевидное правило — если у класса есть пользователи, то интерфейс его меняться может только в сторону расширения.

Если Вы меняете внутреннее представление полигона, но оставляете интерфейс фиксированным, то кому какое дело до его внутренней реализации?

А как я говорил Albatross'у в private communication, собственно выяснением пересечения методы классов фигур заниматься не должны (и, соответственно, должны знать только о существовании друг друга, а не о внутреннем представлении, даже данном через фиксированный интерфейс), они должны вызывать функции некоего класса-хелпера, который является другом всех классов, желающих попересекаться. Таким образом только класс-хелпер будет зависеть от реализации классов-фигур, но необходимость этого и так очевидна, если мы хотим написать хоть немного эффективную программу при том обилии виртуальных вызовов, да и вообще сложно себе представить алгоритм, который не знает, с чем имеет дело :)))

You will always get what you always got
  If you always do  what you always did

Здравствуйте, Шахтер, Вы писали:

ПК>>Мультиметоды — одна из фундаментальных проблем C++.

Ш>Я думаю, это не проблема языка, как такового.

Это проблема ООП вообще.

Для "монометодов" диспетчеризация не представляет сложности: все классы в иерархии частично упорядочены, и можно всегда сказать, какая реализация метода должна быть вызвана.

А для мультиметодов — приходится вводить частичный порядок над кортежами классов (как минимум, над парами).
Который учитывает уже имеющийся частичный порядок самих классов — во-первых;
Который как-то разруливает неоднозначности — во-вторых;
Который выдерживает масштабирование (добавление новых классов) — в-третьих.

Есть разные реализации мультиметодов.
Самые популярные — это
1. Обработчик-сообщение (преимущество первого аргумента)
2. Двойная диспетчеризация (преимущество второго аргумента)
3. Первый подошедший (в порядке регистрации сигнатур)
4. Точное совпадение (всё, что не подошло — вызывает дефолт)
отличающиеся в первую очредь порядком (а уже потом — техникой воплощения).
Ну и ещё пару схем могу привести, но они затейливые.

Короче говоря, перед тем, как кодировать мультиметоды — нужно объяснить себе, что же в самом деле должно происходить между каждой парой классов. А не только между теми, для которых существуют сигнатуры мультиметода.

Здравствуйте Albatross, Вы писали:

A>Представьте себе ситуацию — есть у меня абстрактный класс Geometry , под которым мы понимаем некоторый геметрический объект. От него наследуются классы Point, Line , ну и Polygon. В Geometry определён абстрактный виртуальный метод BOOL Geometry::IsOverlap (Geometry * AnotherGeometry), который просто показывает, есть ли у этих объектов общие точки. Есть своя реализация этого метода в каждом из потомков — то есть в классах Point, Line и Polygon. Но тут возникает следующая проблема. Класс Polygon, в принципе, должен знать только о себе, то есть он сможет определить, пересекается ли он с другим полигоном. А как же быть с остальными фигурами? Можно, конечно, в каждом классе выяснять, что за объект туда поступает и на основе этого вычислять, пересекается или нет. Но тогда получается, что если мы сделаем замену в классе полигона, то придётся переписывать все остальные классы. Каким образом надо действовать? Как реализовывать этот метод? Помогите советом!

Ну не знаю что тебе посоветовать, но:
проблема по-моему не в реализации классов, а в подходе к пересечению. Как ты сможешь пересечь 2 фигуры если тебе обе (или одна из них) не известны? Посморти в WinAPI, там есть один общий, так сказать, "класс" под названием region, который получается пересечением примитивов. Так вот любой алгоритм пересечения будет исходить из структуры твоего объекта Geometry, которая должна быть известна и достаточно абстрактна (и однообразна для всех подклассов). Подходы могут быть: набор примитивов (например триангуляция) или по границам и др. Примерно вот такая мысль.
ЗЫ. IsOverlap — это не есть осмысленное выражение, пологичнее было бы overlaps или intersects

Здравствуйте Albatross, Вы писали:

A>Каким образом надо действовать? Как реализовывать этот метод? Помогите советом!

Безупречного решения этой проблемы вроде нет.
Твой вопрос очень подробно обсуждался Скоттом Мейерсом в Наиболее эффективном использовании C++

Автор(ы): Скотт Мейерс
В новой книге Скотта Мейерса, которая является
продолжением популярного издания
"Эффективное использование C++",
приводятся рекомендации по
наиболее эффективному использованию конструкций языка C++. Рассматриваются
правила перегрузки операторов, способы приведения типов, реализация механизма
RTTI и многое другое. Даны практические советы по применению буферизованного
оператора new, виртуальных конструкторов, интеллектуальных указателей,
proxy-классов и двойной диспетчеризации. Особое внимание уделяется работе с
исключениями и возможностям использования кода С в программах, написанных на
C++. Подробно описаны новейшие средства языка и показано, как с их помощью
повысить производительность программ. Приложения содержат код шаблона auto_ptr и
аннотированный список литературы и Internet-ресурсов, посвященных C++.

(Правило 31)(Кстати, там даже постановка как у тебя, тоже столкновения но только всяких космических объектов ). Он рассмотрел много способов решения и каждый из них имел те или иные минусы. Выбор зависит от специфики конкретной задачи и прочих субъективных условий. Вообщем, по этому вопросу тебе просто необходимо это прочитать.

Здравствуйте Рома, Вы писали:

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

Здравствуйте Dima2, Вы писали:

D>Здравствуйте Рома, Вы писали:

D>Ребята, а чего вы пытаетесь засунуть этот вопрос в алгоритмы.
D>По моему с чисткой рядов не надо перебарщивать, ведь вопрос касается объектной модели системы классов, чего вы его сунете в алгоритмы

вообще-то я не знал куда его пихать, как бы к c++ он прямого-то отношения не имеет, скорее его бы в проектирование, но там какие-то не совсем те темы, т.е. даже скорее в прочее, хотя ИМХО проблема в данном случае отчасти лежит в алгоритме как раз.

Здравствуйте Курилка, Вы писали:

К>Здравствуйте Dima2, Вы писали:

D>>Здравствуйте Рома, Вы писали:

D>>Ребята, а чего вы пытаетесь засунуть этот вопрос в алгоритмы.
D>>По моему с чисткой рядов не надо перебарщивать, ведь вопрос касается объектной модели системы классов, чего вы его сунете в алгоритмы :no:

К>вообще-то я не знал куда его пихать, как бы к c++ он прямого-то отношения не имеет, скорее его бы в проектирование, но там какие-то не совсем те темы, т.е. даже скорее в прочее, хотя ИМХО проблема в данном случае отчасти лежит в алгоритме как раз.


Меня интересует имеено ОБЪЕКТНАЯ МОДЕЛЬ....
то есть как надо делать — какие классы и всё такое..
дело даже не в алгоритме пересечения

Здравствуйте Аноним, Вы писали:

А>Меня интересует имеено ОБЪЕКТНАЯ МОДЕЛЬ....
А>то есть как надо делать — какие классы и всё такое..
А>дело даже не в алгоритме пересечения

Не переживай совместными усилиями мы тебя отстояли
А вообще-то надо давно расписать тематику форумов (Денис где ты), чтобы не было таких споров.

Здравствуйте Курилка, Вы писали:

К>хотя ИМХО проблема в данном случае отчасти лежит в алгоритме как раз.

Как раз нет. Человеку не важно КАК делать пересечение (он про это ни слова ни сказал), ему нужна удобная для использования и поддержки система. Алгоритмы здесь действительно ни при чем.

Здравствуйте Аноним, Вы писали:

А>Здравствуйте Курилка, Вы писали:

К>>Здравствуйте Dima2, Вы писали:

D>>>Здравствуйте Рома, Вы писали:

D>>>Ребята, а чего вы пытаетесь засунуть этот вопрос в алгоритмы.
D>>>По моему с чисткой рядов не надо перебарщивать, ведь вопрос касается объектной модели системы классов, чего вы его сунете в алгоритмы

К>>вообще-то я не знал куда его пихать, как бы к c++ он прямого-то отношения не имеет, скорее его бы в проектирование, но там какие-то не совсем те темы, т.е. даже скорее в прочее, хотя ИМХО проблема в данном случае отчасти лежит в алгоритме как раз.


А>Меня интересует имеено ОБЪЕКТНАЯ МОДЕЛЬ....
А>то есть как надо делать — какие классы и всё такое..
А>дело даже не в алгоритме пересечения

Ну если так подходить, то с объектной моделью у тебя всё в порядке...
Другое дело, что такая абстрактная модель очень плохо работает, когда ты пытаешься реализовать
алгоритм, необходимый в ней.
Т.е. нельзя строить иерархию классов и интерфейсов не беря в рассчёт механизмы их взаимодействия (т.е. алгоритмы).

Что-то на ночь глядя в теорию потянуло...

Здравствуйте Dima2, Вы писали:

D>Здравствуйте Аноним, Вы писали:

D>Не переживай совместными усилиями мы тебя отстояли
D>А вообще-то надо давно расписать тематику форумов (Денис где ты), чтобы не было таких споров.

Да ладно, я сам не очень был уверен, что делать с этим топиком, если честно.
Извиняюсь за оффтопик, но на твой взгляд где сейчас место вопросам про "ОБЪЕКТНЫЕ МОДЕЛИ"?
По-моему определённого места на форуме сейчас нет (лучше всего "проектирование", но та тема забита топиками скорее о разработке, чем о "software design").

Здравствуйте Albatross, Вы писали:


A>Ну хорошо, предлагается сделать так — завести класс интерфейса, который будет заниматься пресечением. И типа там будет одна функция, коотрая принимает 2 указателя на базовый класс. Потом она выясняет, что за объекты и уже, основываясь на этих фактах нахродит пересечение. Правильно?

Ага. Только выяснять тип обьекта нельзя. Лучше использовать virtual функции.

Здравствуйте Albatross, Вы писали:

A>Ну хорошо, предлагается сделать так — завести класс интерфейса, который будет заниматься пресечением. И типа там будет одна функция, коотрая принимает 2 указателя на базовый класс. Потом она выясняет, что за объекты и уже, основываясь на этих фактах нахродит пересечение. Правильно?

Умная идея, позволяет абстрагироваться от алгоритма пересечения...
Однако это переносит проблему распознания объектов в этот алгоритм, а в принципе разные алгоритмы используют разные данные. Т.е. проблемы ещё те, ну да ладно — пойду я домой, буду рад завтра с утра почитать новые умные мысли по этому поводу.

Здравствуйте Рома, Вы писали:

Р>Здравствуйте Albatross, Вы писали:


A>>Ну хорошо, предлагается сделать так — завести класс интерфейса, который будет заниматься пресечением. И типа там будет одна функция, коотрая принимает 2 указателя на базовый класс. Потом она выясняет, что за объекты и уже, основываясь на этих фактах нахродит пересечение. Правильно?

Р>Ага. Только выяснять тип обьекта нельзя. Лучше использовать virtual функции.


Хе! в том-то и дело! какую виртуальную функцию ты здесь предложишь? Можно, конечно, пофантазировать — типа она будет возвращать все точки этого объекта. Но тогда просто и без интерфейсного класса обойтись! ТИпа блин просто прописать это в каждом — вызов Geometry::GEtPOints — и просто смотреть, есть ли совпадающие с GEtPOints у тебя..
Но это же лажа — все точки возвращать!

Здравствуйте Albatross, Вы писали:

A>Здравствуйте Рома, Вы писали:

Р>>Здравствуйте Albatross, Вы писали:


A>>>Ну хорошо, предлагается сделать так — завести класс интерфейса, который будет заниматься пресечением. И типа там будет одна функция, коотрая принимает 2 указателя на базовый класс. Потом она выясняет, что за объекты и уже, основываясь на этих фактах нахродит пересечение. Правильно?

Р>>Ага. Только выяснять тип обьекта нельзя. Лучше использовать virtual функции.


A>Хе! в том-то и дело! какую виртуальную функцию ты здесь предложишь? Можно, конечно, пофантазировать — типа она будет возвращать все точки этого объекта. Но тогда просто и без интерфейсного класса обойтись! ТИпа блин просто прописать это в каждом — вызов Geometry::GEtPOints — и просто смотреть, есть ли совпадающие с GEtPOints у тебя..
A>Но это же лажа — все точки возвращать!
Неа и линию и круг можно описать как регион

Р>Здравствуйте Albatross, Вы писали:

Р>Неа и линию и круг можно описать как регион

HRGN CreateEllipticRgn(
  int nLeftRect,   // x-coord of the upper-left corner of the bounding rectangle
  int nTopRect,    // y-coord of the upper-left corner of the bounding rectangle
  int nRightRect,  // x-coord of the lower-right corner of the bounding rectangle
  int nBottomRect  // y-coord of the lower-right corner of the bounding rectangle
);

Вот эллипс, к примеру. Линия описывается тривиально.

Здравствуйте IT, Вы писали:

IT>Здравствуйте Albatross, Вы писали:

A>>Представьте себе ситуацию...

IT>Если тебя интересует в первую очередь объектная модель, а не эффективность, то можно ввести объект описывающие фигуру не в её родных примитивах (окружностях, длинах, углах), а неких универсальных (возможно даже для частного случая) примитивах (например, точках и/или векторах). Все твои объекты должны уметь создавать/заполнять такие объекты (назовём их регионы), ну а алгоритмы пересечения нужно делать уже для регионов.

IT>Этот подход будет работать для любых типов твоих фигур при минимальных затратах. К тому же для реализации других алгоритмов тебе уже не нужно будет сильно напрягаться, достаточно будет его реализовать только для регионов.


Ну так просто не получится! Точки здесь не помогут, потомму что у любого региона их континум. Здесь будут сильно отличающиеся друг от друга механизмы хранения того или иного объекта, в том-то и дело.

Здравствуйте Albatross, Вы писали:

IT>>Если тебя интересует в первую очередь объектная модель, а не эффективность, то можно ввести объект описывающие фигуру не в её родных примитивах (окружностях, длинах, углах), а неких универсальных (возможно даже для частного случая) примитивах (например, точках и/или векторах). Все твои объекты должны уметь создавать/заполнять такие объекты (назовём их регионы), ну а алгоритмы пересечения нужно делать уже для регионов.

A>Ну так просто не получится! Точки здесь не помогут, потомму что у любого региона их континум. Здесь будут сильно отличающиеся друг от друга механизмы хранения того или иного объекта, в том-то и дело.

Точки я привёл к примеру. Главное найти универсальный набор примитивов. Может быть получится взять за основу подход принятый в метафайлах — хранить и манипулировать последовательностями действий, а не только данными. В общем, речь идёт об универсальном формате представления любых объектов.

Здравствуйте IT, Вы писали:

IT>Здравствуйте Albatross, Вы писали:

IT>>>Если тебя интересует в первую очередь объектная модель, а не эффективность, то можно ввести объект описывающие фигуру не в её родных примитивах (окружностях, длинах, углах), а неких универсальных (возможно даже для частного случая) примитивах (например, точках и/или векторах). Все твои объекты должны уметь создавать/заполнять такие объекты (назовём их регионы), ну а алгоритмы пересечения нужно делать уже для регионов.

A>>Ну так просто не получится! Точки здесь не помогут, потомму что у любого региона их континум. Здесь будут сильно отличающиеся друг от друга механизмы хранения того или иного объекта, в том-то и дело.

IT>Точки я привёл к примеру. Главное найти универсальный набор примитивов. Может быть получится взять за основу подход принятый в метафайлах — хранить и манипулировать последовательностями действий, а не только данными. В общем, речь идёт об универсальном формате представления любых объектов.



вот мне что посоветовали :
"в таких случаях испольуется double dispatching

Сообщение послал(а): jazzer (glip.7ka.mipt.ru)
Дата: 01:14:04 6/5/02

В ответ на: мне тут вот что ответили... (Albatross)

не знаю, как по-русски, что-то вроде "двойная диспетчеризация"

это чтобы все делать не через определение типа, а через вызовы виртуальных методов

суть в следующем

объявляются (и определяются) методы, определяющие пересечение данного объекта с другим типом, например,

bool Polygon::overlaps(const Line&);

а также общий метод

bool Polygon::overlaps(const Figure& f)
{
return f.overlaps(*this); // здесь тип уже точно известен тип передаваемой фигуры
}

так все работает


возражение о том, что если перепишется Полигон, то придется переписывать реализации методов пересечения
bool Line::overlaps(const Polygon& f)
не специфичен для обсуждаемой задачи, это — общая проблема изменения интерфейса при наличии классов, которые от этого интерфейса зависят (что всегда будет, иначе зачем нужны такие классы :) )


"

Здравствуйте Albatross, Вы писали:

A>вот мне что посоветовали :
A>"в таких случаях испольуется double dispatching

A>возражение о том, что если перепишется Полигон, то придется переписывать реализации методов пересечения
A>bool Line::overlaps(const Polygon& f)
A>не специфичен для обсуждаемой задачи, это — общая проблема изменения интерфейса при наличии классов, которые от этого интерфейса зависят (что всегда будет, иначе зачем нужны такие классы )

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

Здравствуйте IT, Вы писали:

IT>Здравствуйте Albatross, Вы писали:

A>>вот мне что посоветовали :
A>>"в таких случаях испольуется double dispatching

A>>возражение о том, что если перепишется Полигон, то придется переписывать реализации методов пересечения
A>>bool Line::overlaps(const Polygon& f)
A>>не специфичен для обсуждаемой задачи, это — общая проблема изменения интерфейса при наличии классов, которые от этого интерфейса зависят (что всегда будет, иначе зачем нужны такие классы )

IT>В этом случае каждый должен знать о каждом. Это будет работать эффективно, но сложность программы будет расти в прогрессии с каждой новой добавляемой фигурой.

Да и переписывать уже готовый код при добавлении новой фигуры или исправлении старой не очень-то
Чем меньше классы знают друг о друге, тем лучше.

Мне кажется, что тут набо юзать двойную диспетчеризацию.

Здравствуйте jazzer, Вы писали:

ПК>>Двойная виртуализация

J>недостаток размазанности решаются введением класса-хелпера, в который, собственно, и выносится весь код определения пересечения.

Класс-helper здесь даже не нужен: можно вызывать соответствующую функцию из набора функций поиска пересечений. Основная проблема, однако, не решается: размазанность диспетчеризации. При добавлении новых примитивов все равно требуется модификация всех остальных.

J>Более того, имеет смысл предусмотреть общий механизм пересечения просто фигур через их общее представление в виде тех же регионов, напрмер. Тогда введение новой фигуры не затронет старых пользователей, а новые получат уже новый специально для нее определенный механизм определения пересечения.

Это непрактично. Примитивы определяются именно для того, чтобы избежать общего представления фигур/тел треугольниками/отрезками и т.д. В трехмерке поиск пересечений даже примитивов является нетривиальной задачей, не говоря уже о "polygon soup".

J>В общем, я за двойную диспетчеризацию (или виртуализацию)

На практике оптимальным подходом оказывается комбинация всех трех способов: двойная виртуализация для "встроенных" примитивов, RTTI для примитивов пользователя для диспетчеризации первого уровня с последующей детализацией через таблицы.

Здравствуйте Кодт, Вы писали:

К>Добавлю к сказанному о мультиметодах.
К>Третий способ дает квадратичный рост сложности.
К>Для лучшей масштабируемости (и обхода проблемы с матрицей функций) используют ранжирование.

Действительно. Обычно при решении задачи поиска пересечений понятия объектов и примитивов разделяют. Объекты описывают общую структуру (одиночный примитив, набор примитивов, выпуклое полигональное тело и т.д.). Тогда количество примитивов можно значительно снизить.

Здравствуйте Павел Кузнецов, Вы писали:

ПК>Здравствуйте jazzer, Вы писали:

ПК>>>Двойная виртуализация

J>>недостаток размазанности решаются введением класса-хелпера, в который, собственно, и выносится весь код определения пересечения.

ПК>Класс-helper здесь даже не нужен: можно вызывать соответствующую функцию из набора функций поиска пересечений. Основная проблема, однако, не решается: размазанность диспетчеризации. При добавлении новых примитивов все равно требуется модификация всех остальных.

размазанность диспетчеризации — да, он остается, он уходит размазанность реализации определения пересечения. Собственно, класс вводится для того, чтобы можно было его одной строчкой объявить другом и через это дать доступ к внутренностям фигур всем методам этого класса. Просто для удобства.

J>>Более того, имеет смысл предусмотреть общий механизм пересечения просто фигур через их общее представление в виде тех же регионов, напрмер. Тогда введение новой фигуры не затронет старых пользователей, а новые получат уже новый специально для нее определенный механизм определения пересечения.

ПК>Это непрактично. Примитивы определяются именно для того, чтобы избежать общего представления фигур/тел треугольниками/отрезками и т.д. В трехмерке поиск пересечений даже примитивов является нетривиальной задачей, не говоря уже о "polygon soup".

Правильно, это непрактично с точки зрения конечного решения, но в качестве практичного конечного решения это и не предлагается.
Просто я сужу по своему опыту: у меня была похожая задача и я первым делом, просто чтобы продемонстрировать в общих чертах работу программы, сделал все через одну функцию, которая принимала в себя регионы из API win32 (сама программа делалась для юникса).
А потом, когда основные вопросы были улажены, я уже занялся конкретной эффективной реализацией, заточенной для каждой пары типов примитивов.
Главное — что при этом мне не пришлось перелопачивать уже существовавший дизайн: для тех типов, для которых уже был определен алгоритм пересечения, работал он, для остальных работал "регионовый", и все это делалось автоматически.
Т.е. с самого начала в каждый момент моя программа была полностью работоспособной (и заказчик уже работал с ней, чтобы определить, что еще может понадобиться и т.д., на этом этапе производительность не была важна), просто шаг за шагом увеличивалась ее производительность.


Да, и что Вы думаете о применении наследников и typedef'ов?

You will always get what you always got
  If you always do  what you always did

Здравствуйте jazzer, Вы писали:

J>Собственно, класс (helper) вводится для того, чтобы можно было его одной строчкой объявить другом и через это дать доступ к внутренностям фигур всем методам этого класса. Просто для удобства.

Обычно дружественность здесь тоже не нужна. Примитивы должны давать достаточный public интерфейс для определения их пересечений. Хотя, в принципе, согласен, что вопрос о том, следует ли заводить вспомогательный класс, в данном случае принципиальным не является.

J>>>Более того, имеет смысл предусмотреть общий механизм пересечения (...)

ПК>>Это непрактично. Примитивы определяются именно для того, чтобы избежать общего представления фигур/тел треугольниками/отрезками и т.д.

J>Главное — что при этом мне не пришлось перелопачивать уже существовавший дизайн

Именно этот аргумент обычно становится решающим при отказе от двойной виртуализации.

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

Это в двухмерке, в трехмерке разработка алгоритма определения пересечений произвольных тел является изрядно сложной задачей, особенно при наличии ограничений по времени выполнения (например, в играх). Наиболее практичным и гибким подходом, на мой взгляд, является использование RTTI с последующим "сползанием" в ту или иную форму таблицы функций.

J>Да, и что Вы думаете о применении наследников и typedef'ов?

Согласен. Для многих задач возможность использования множественной диспетчеризации в присутствии наследования может становиться очень важным аргументом при выборе той или иной схемы.

В принципе существует возможность реализовать неплохую схему множественной виртуализации с использованием шаблонов, динамической регистрацией type_id классов и расширением таблицы мультиметодов. В таком случае можно даже учитывать нюансы наследования. Желающие могут посмотреть на вариант подобной реализации в "Modern C++ Design" Андрея Александреску или на http://sf.net/projects/loki-lib (см. в CVS).

Здравствуйте Кодт, Вы писали:

К>модификация всех необязательна. С использованием тройной диспетчеризации.

IMHO, это приводит к еще более размазанной диспетчеризации по всем вспомогательным классам со всеми вытекающими сложностями последующего сопровождения по сравнению с табличными методами. Но, как уже было замечено ранее, какого-то одного лучшего решения в этой области не существует. Все зависит от специфики и ограничений конкретной задачи.

К>Хелперы могут пригодиться для

Могут пригодиться != нужны. Я не против введения вспомогательных классов вообще, я только хочу заметить, что для данного класса задач в силу их алгоритмической природы более близки наборы функций, нежели вспомогательные классы. Все приведенные тобой примеры с успехом решаются использованием функций. В дальнейшей дискуссии в направлении вспомогательных классов я умываю руки: о вкусах не спорят.

Здравствуйте Albatross, Вы писали:

A>Представьте себе ситуацию — есть у меня абстрактный класс Geometry , под которым мы понимаем некоторый геметрический объект. От него наследуются классы Point, Line , ну и Polygon. В Geometry определён абстрактный виртуальный метод BOOL Geometry::IsOverlap (Geometry * AnotherGeometry), который просто показывает, есть ли у этих объектов общие точки. Есть своя реализация этого метода в каждом из потомков — то есть в классах Point, Line и Polygon. Но тут возникает следующая проблема. Класс Polygon, в принципе, должен знать только о себе, то есть он сможет определить, пересекается ли он с другим полигоном. А как же быть с остальными фигурами? Можно, конечно, в каждом классе выяснять, что за объект туда поступает и на основе этого вычислять, пересекается или нет. Но тогда получается, что если мы сделаем замену в классе полигона, то придётся переписывать все остальные классы. Каким образом надо действовать? Как реализовывать этот метод? Помогите советом! :???:

Классы Point, Line, Polygon должны заниматься только собой, сцепление должно быть минимальным.


Я сначала написал Primitive, везде заменять это на Graphics в лом, поэтому
Primitive == Graphics.

Я бы решал subj так:

1. Делаем класс COverlapDetector, у него есть метод virtual BOOL IsOverlap(Primitive* pP1, Primitive* pP2).
2. В классе Geometry делаем статичную переменную COverlapDetector* m_pOverlapDetector.
3. В методе IsOverlap(Primitive* pP) если m_pOverlapDetector инициализирован вызываем m_pOverlapDetector->IsOverlap(this, pP)

----------------------------------------------------

Затем ветка решения раздваивается (впрочем они могут существовать одновременно).
Ветка 1.


1.
По мере добавления примитивов создаем дерево CPointDetector-> CLineDetector-> CPolygonDetector.

CPointDetector должен уметь работать только с примитивами типа точка, CLineDetector должен работать с примитивами типа линия, плюс работа со смешанными примитивами линия — точка. Каждый последующий класс должен обрабатывать смешанное пересечение со всеми предыдущими примитивами.

BOOL CPointDetector::IsOverlap(Primitive* pP1, Primitive* pP2)
{
    //  Здесь делаем кастинг на точки, если точки проверяем...
}

BOOL CLineDetector::IsOverlap(Primitive* pP1, Primitive* pP2)
{
    if (CPointDetector::IsOverlap(pP1, pP2))
    return TRUE;
    
    //  Здесь делаем кастинг на линии - точки, и если есть смешивание выполняем проверку смешанных  примитивов линия - точка, иначе линия - линия.
}

2.

{
    CPolygonDetector PD;

    Primitive::SetOverlapDetector(&PD);
    //  Работаем... 
}

Очевидный недостаток — завязка на последовательность добавления примитивов, сцепление увеличивается с каждым добавленным в дерево классом. Достоинство — немного кода.

Ветка 2.

1. Создаем класс COverlapDetectorGroup (унаследованный от COverlapDetector), в нем
имеем два метода Add(COverlapDetector *pDetector), Remove(COverlapDetector *pDetector), которые добавляют/удаляют детекторы во внутренний список. В методе IsOverlap(Primitive* pP1, Primitive* pP2) в цикле вызываем метод IsOverlap у каждого объекта (до первого результата IsOverlap == TRUE).

2. Далее при добавлении примитивов создаем новые подклассы CPointPointOverlapDetector,
CPointLineOverlapDetector. На первый взгляд это имеет недостаток — придется создавать много
подклассов, но на практике много плюсов — удобно расширять, код очевиден, сцепление минимально, да и к тому же можно хорошо все это паковать в namespace.

{
    CPointPointOverlapDetector PPD;
    CPointLineOverlapDetector PLD;
    COverlapDetectorGroup ODG;

    odg.Add(&PPD);
    odg.Add(&PLD);

    Primitive::SetOverlapDetector(&ODG);

    //  Работаем... 
}

Можно создать несколько групп по типам примитивов и слить их в одну

{
    COverlapDetectorGroup PointODG;
    PointODG.Add(...
    ...

    COverlapDetectorGroup LineODG;
    LineODG.Add(...
    ...

    COverlapDetectorGroup SummaryODG;
    SummaryODG.Add(&LineODG);
    SummaryODG.Add(&PointODG);

    Primitive::SetOverlapDetector(&ODG);

    //  Работаем... 
}

Здравствуйте Павел Кузнецов, Вы писали:

ПК>Здравствуйте Albatross, Вы писали:
ПК>(Вопрос об организации поиска пересечений геометрических примитивов.)
ПК>Мультиметоды — одна из фундаментальных проблем C++...

А теперь бы все это в статейку оформить, а?

P.S. Сижу и думаю: кому же первому ответ отправить: Кузнецову или Кодту?

Здравствуйте Кодт, Вы писали:

К>Здравствуйте Павел Кузнецов!

К>Добавлю к сказанному о мультиметодах...

А теперь бы все это в статейку оформить, а?

P.S. Сижу и думаю: кому же первому ответ отправить: Кузнецову или Кодту?

Здравствуйте Кодт, Вы писали:

К>Журнал "Открытые Системы" март 2002.
К>"ООП, мультиметоды и пирамидальная эволюция"
К>http://www.osp.ru/os/2002/03/041.htm

Знаем, знаем — читали. Я имел в виду на RSDN бы чего-нибудь состряпать.

Здравствуйте Кодт, Вы писали:

К>Ну, как показано выше, -- модификация всех необязательна. С использованием тройной диспетчеризации. Хотя это и эротично...

Несмотря на мою очевидную нерасположенность применять "тройную диспетчеризацию" в задаче поиска пересечений, по дальнейшем размышлении я нашел идею изрядно интересной.

P.S. За ссылку на статью также спасибо

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>

Матрица указателей на функции пересечения примитивов по идентификаторам, хранящимся в объекте (ad hoc rtti).
...

ПК>
• Достоинства: максимальная производительность, возможность добавления поиска пересечений новых примитивов без модификации исходных классов.
  ПК>
• Недостатки: слабая интеграция с языком, в частности, невозможность поиска пересечений объектов унаследованных классов, необходимость поддержания набора уникальных идентификаторов.

Здесь

Автор: sergey_shandar
Дата: 25.03.04

, если интересно, реализованна мульти диспетчиризации построенная на N-мерном массиве указателей, с автоматическим заполнением и с устранением недостатка создания уникальных идентификаторов. Есть правда другой недостаток — создание списка используемых типов.

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Наиболее практичным и гибким подходом, на мой взгляд, является использование RTTI с последующим "сползанием" в ту или иную форму таблицы функций.

Павел, не могли бы Вы пояснить свою мысль фрагментом кода?

У меня в движке так сделанно... никаких двойных виртуальных фунций, ибо отсекать нужно максимально быстро...
Сорри, не могу сделать копи-паст, так что реализация не реализованна
Я заранее знал, что у меня есть только шары и бибоксы

#include <iostream>

struct BoundingVolume
{
protected:
  enum { bbox=0, bsphere=1 } type_id;
  friend bool Intersect(const BoundingVolume &v1, const BoundingVolume &v2);
};


class BBox: public BoundingVolume
{
public:
  BBox() { type_id=bbox; }
};

class BSphere: public BoundingVolume
{
public:
  BSphere() { type_id= bsphere; }
};

bool Intesect_bb(const BoundingVolume &b1, const BoundingVolume &b2)
{
  std::cout <<__FUNCSIG__ <<std::endl;
  return true;
}

bool Intesect_bs(const BoundingVolume &b1, const BoundingVolume &s2)
{
  std::cout <<__FUNCSIG__ <<std::endl;
  return true;
}

bool Intesect_sb(const BoundingVolume &s1, const BoundingVolume &b2)
{
  std::cout <<__FUNCSIG__ <<std::endl;
  return true;
}

bool Intesect_ss(const BoundingVolume &s1, const BoundingVolume &s2)
{
  std::cout <<__FUNCSIG__ <<std::endl;
  return true;
}

typedef bool (*IntersectFunction_t)(const BoundingVolume &v1, const BoundingVolume &v2);

const IntersectFunction_t IntersectFuctionsTable[4]=
{
  Intesect_bb, Intesect_bs, Intesect_sb, Intesect_ss
};

bool Intersect(const BoundingVolume &v1, const BoundingVolume &v2)
{
  return IntersectFuctionsTable[(v1.type_id<<1) + v2.type_id](v1, v2);
}


#include <iostream>

int main()
{
  BoundingVolume *pb = new BBox;
  BoundingVolume *ps = new BSphere;

  Intersect(*pb, *pb);
  Intersect(*pb, *ps);
  Intersect(*ps, *pb);
  Intersect(*ps, *ps);

}

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Здравствуйте Albatross, Вы писали:
ПК>(Вопрос об организации поиска пересечений геометрических примитивов.)

ПК>Мультиметоды — одна из фундаментальных проблем C++.

Я думаю, это не проблема языка, как такового.

ПК>На сегодняшний день можно выделить три способа решения задач связанных с множественной диспетчеризацией, и, в частности, поиска пересечений.

Не могу удержаться. Я тут недавно постил свой сэмпл

Автор: Шахтер
Дата: 08.05.04

.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, _Winnie, Вы писали:

_W>У меня в движке так сделанно... никаких двойных виртуальных фунций, ибо отсекать нужно максимально быстро...

Вот тот же пример, только с применением kafe.

struct BoundingVolume {};

class BBox: public BoundingVolume {};

class BSphere: public BoundingVolume {};

//------------------------------------------------------------------------------

#include <kafe/dispatch.hpp>

namespace kafe
{
/// Определение наследников.
template<>
struct children<BoundingVolume>: boost::mpl::vector<BBox, BSphere> {};

/// Определения возвращаемого типа.
struct mix<boost::mpl::vector<BoundingVolume, BoundingVolume> >: 
    mix_helper<boost::mpl::vector<BoundingVolume, BoundingVolume>, bool>
{
};

bool mix_func(const BBox *b1, const BBox *b2)
{
  std::cout <<__FUNCSIG__ <<std::endl;
  return true;
}

bool mix_func(const BBox *b1, const BSphere *b2)
{
  std::cout <<__FUNCSIG__ <<std::endl;
  return true;
}

bool mix_func(const BSphere *b1, const BBox *b2)
{
  std::cout <<__FUNCSIG__ <<std::endl;
  return true;
}

bool mix_func(const BSphere *b1, const BSphere *b2)
{
  std::cout <<__FUNCSIG__ <<std::endl;
  return true;
}
}

#include <iostream>

int main()
{    
    kafe::child<BoundingVolume, BBox> b;
    kafe::child<BoundingVolume, BSphere> s;
    
    kafe::call_mix_func(b, b);
    kafe::call_mix_func(b, s);
    kafe::call_mix_func(s, b);
    kafe::call_mix_func(s, s);
    
    std::cin.get();
}

А если функции не нужно возращать результат, и хочеться использовать шаблонные функции, то все будет выглядеть еще проще:

struct BoundingVolume {};

class BBox: public BoundingVolume {};

class BSphere: public BoundingVolume {};

//------------------------------------------------------------------------------

#include <kafe/dispatch.hpp>

namespace kafe
{
template<>
struct children<BoundingVolume>: boost::mpl::vector<BBox, BSphere> {};

template<class T1, class T2>
void mix_func(const T1 *b1, const T2 *b2)
{
  std::cout << typeid(T1).name() << " x " << typeid(T2).name() <<std::endl;
}

}

#include <iostream>

int main()
{    
    kafe::child<BoundingVolume, BBox> b;
    kafe::child<BoundingVolume, BSphere> s;
    
    kafe::call_mix_func(b, b);
    kafe::call_mix_func(b, s);
    kafe::call_mix_func(s, b);
    kafe::call_mix_func(s, s);
    
    std::cin.get();
}