Здравствуйте 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>В этом случае каждый должен знать о каждом. Это будет работать эффективно, но сложность программы будет расти в прогрессии с каждой новой добавляемой фигурой.

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

Здравствуйте 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).

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

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

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

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

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

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

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

Принцип двойной передачи
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...)
Каждая новая версия библиотеки должна будет поддерживать предыдущую.

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

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

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

ПК>

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

ПК>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

Здравствуйте 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).

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

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);
}

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

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

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. Сижу и думаю: кому же первому ответ отправить: Кузнецову или Кодту?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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