Re: вопрос по объектно-ориентированному пронраммирован
От: Павел Кузнецов  
Дата: 06.05.02 08:30
Оценка: 169 (18)
Здравствуйте 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).
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.