Design Problem

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

re: Design Problem

* Merlin:[color=blue]
> Design Problem
> ===============[/color]

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?

re: Design Problem

On 6 Oct 2005 17:24:29 -0700, "Merlin" <merlin2769@hotmail.com> wrote:
[color=blue]
>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)[/color]

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.
[color=blue]
>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][/color]

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.[color=blue]
>
>Then Polygon will be a composite and so will Shape.
>The datastructure to use for the polygon could be an array or a list.[/color]

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.
[color=blue]
>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.[/color]

[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
NoSpamPlease@Home.com

re: Design Problem

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