Design Problem

Discussion in 'C++' started by Merlin, Oct 7, 2005.

  1. Merlin

    Merlin Guest

    Design Problem
    ===============

    Would appreciate any help or suggestion on this design issue. I have
    spent a great deal of time and effort for an elegant solution but it
    seems I am not getting anywhere...

    I have simplified my design problem to the following:

    Consider the following classes:
    Entity, Point, Polygon, Shape

    Entity is the base class of Point, Polygon and Shape

    Point is obvious
    Polygon is defined using a set of points
    Shape is a "set" of polygons BUT it will have one outside polygon and
    zero or more inside polygons (ie. holes)

    If I apply the composite pattern, I can make Entity to be the component
    and Point will be a leaf. [There are other leaves in my original
    design. Remember this is a simple example]

    Then Polygon will be a composite and so will Shape.
    The datastructure to use for the polygon could be an array or a list.

    However, the datastructure to use for Shape is debatable. Unlike a
    polygon where its points can happily reside side by side in an array or
    a list, the polygons in a shape have a hierarchial relationship. The
    outside polygon is the parent of the inside polygons. It therefore
    seems reasonable to use a tree data structure in Shape to store the
    polygons. GOF suggest using different data structure to store the
    children of a composite and Shape seems to offer an object where a tree
    would be appropriate.

    If the above solution is OK so far then a number of questions arise.

    1) the parent pointer for a composite pattern that is declared in the
    Entity(component) can be set for points of a polygon when we add them
    to a polygon. So each point of a polygon knows its parent(polygon). But
    what about the parent of a polygon in a shape. Will this pointer point
    to the Shape? Ie all the polygons of a shape (outside and inside) will
    know their parent in the composite? Or should this pointer be used to
    indicate the relationship between the polygons. In other words an
    inside polygon(hole) will have its parent pointer set to the outside
    polygon of the shape. Equally the parent pointer of the outside polygon
    of a shape will point to the shape(its parent). Is the parent pointer
    confined to the tree defined by the composite pattern and not the tree
    inside a shape? Can we traverse up from a hole to the outside polygon
    and then to the shape?

    2) Should we have an abstract base class named say Composite for
    Polygon and Shape and if so what will be its interface? The interface
    for a Composite in GOF pattern suggests methods such as Add, Remove and
    GetChild. Will these be enough for the Shape which has a tree data
    structure? Or perhaps we will ahve two sets of interfaces one for
    Polygon(list) and one for Shape(tree)?

    3) It may be the case that a shape (an outside polygon and some inside
    polygon(holes)) could have another shape inside one of the holes.
    Should we create a new class for such a composite named NestedShape or
    just use Shape. What will be the datastructure to store shape in
    NestedShape? Tree again? I like to be able to ask a NestedShape to give
    me all the holes for example...

    4) If I do use a tree data structure for shape whats the best option?
    Implement the tree or use a library? My tree has to be general (not
    binary etc) and most libraries out there implement Binary trees, Avl,
    etc. Does anyone know a good implementation of a general tree data
    structure in c++?

    5) Are there examples of the use of the Composite Pattern with tree
    data structure used to store the children? All examples I have seen use
    a list or an array.


    Many thanks in advance for suggestions...

    Merlin
     
    Merlin, Oct 7, 2005
    #1
    1. Advertising

  2. * Merlin:
    > Design Problem
    > ===============


    What's the C++ question?

    I think this is _most probably_ off-topic in clc++, and suggest you post this
    question in an oo and/or software engineering group.

    That said, it seems to me you're barking up the wrong windmill: just define
    the external functionality you require and implement the thing, which
    shouldn't take more than say 15 minutes; then, if it's too inefficient, apply
    common sense, measure, and optimize (that may take a bit longer). Do forget
    about parenting and such stuff, if it isn't part of the required external
    functionality. Also, you should probably remove your Entity class, which
    seems to only play the role of a Universal Base Class, which is Bad (TM).

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Oct 7, 2005
    #2
    1. Advertising

  3. On 6 Oct 2005 17:24:29 -0700, "Merlin" <> wrote:

    >Design Problem
    >===============
    >
    >Would appreciate any help or suggestion on this design issue. I have
    >spent a great deal of time and effort for an elegant solution but it
    >seems I am not getting anywhere...
    >
    >I have simplified my design problem to the following:
    >
    >Consider the following classes:
    >Entity, Point, Polygon, Shape
    >
    >Entity is the base class of Point, Polygon and Shape
    >
    >Point is obvious
    >Polygon is defined using a set of points
    >Shape is a "set" of polygons BUT it will have one outside polygon and
    >zero or more inside polygons (ie. holes)


    Not sure about this, but it sounds like you are eliminating certain
    kinds of shapes from your Shapes (e.g. circles, ellipses, Moebius
    strips, etc.) Usually, "Shape" is abstract and doesn't know how it
    will be drawn.

    >If I apply the composite pattern, I can make Entity to be the component
    >and Point will be a leaf. [There are other leaves in my original
    >design. Remember this is a simple example]


    As to the design, a Circle or Ellipse only needs to know just a few
    points. A circle can be described by one point (i.e. the center) and a
    length (i.e. the radius). The ellipse needs a few more data to
    describe its circumference.
    >
    >Then Polygon will be a composite and so will Shape.
    >The datastructure to use for the polygon could be an array or a list.


    Polygon would indeed be described sufficiently as an array of points.
    Since the order of the points appears to be important, I would use a
    vector, and not a list, to describe them...unless you need to add or
    subtract certain points very fast, in which case std::list<> might be
    more appropriate.

    >However, the datastructure to use for Shape is debatable. Unlike a
    >polygon where its points can happily reside side by side in an array or
    >a list, the polygons in a shape have a hierarchial relationship. The
    >outside polygon is the parent of the inside polygons. It therefore
    >seems reasonable to use a tree data structure in Shape to store the
    >polygons. GOF suggest using different data structure to store the
    >children of a composite and Shape seems to offer an object where a tree
    >would be appropriate.


    [rest snipped]

    Don't get caught up in the data representation until you have decided
    how you will use your structures. Maybe an array of points is not even
    necessary?

    --
    Bob Hairgrove
     
    Bob Hairgrove, Oct 7, 2005
    #3
  4. Merlin

    Merlin Guest

    Thanks for the reply. Please bear in mind this is striclty a simplified
    model and its not meant to be a hierarchy for other shapes such as
    circles etc. I am only concerned here with the datastructures to use
    for the composites in the context of Composite Design Pattern

    Regards

    Merlin
     
    Merlin, Oct 7, 2005
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ZackS
    Replies:
    5
    Views:
    6,817
    Just an Illusion
    Jul 9, 2004
  2. SpamProof
    Replies:
    3
    Views:
    654
    SpamProof
    Dec 1, 2003
  3. dave
    Replies:
    5
    Views:
    599
    William Brogden
    Jul 17, 2004
  4. Tim Smith
    Replies:
    2
    Views:
    861
    Tim Smith
    Dec 15, 2004
  5. trint
    Replies:
    1
    Views:
    362
    trint
    Nov 21, 2006
Loading...

Share This Page