C++ Design Pattern Problem

Question

You're given 3 shapes: rectangle, triangle and circle. Your task is to find if one shape is contained in another shape. Define this function as a new operation (e.g. bool isContained()) without changing the class hierarchy of the elements on which it operates. Use the appropriate design pattern.

Answer 1

bool isContained( Shape1, Shape2);

returns true of Shape1 is contained by Shape2

Algorithm:

beginning at the center of shape 1, pass a vertical line through

Shape1 and extend it until it hits the end of the graphical board.

If the line passes through shape 2 at any point, then there is at

least partial containment.

Again, beginning at the center of shape1, but at a direction of 1

degree clockwise, pass a line through Shape1 and extend it fully

as described. If this line passes through Shape2 at any point, then

there is at least partial containment.

Proceeding this way, incrementing by 1 degree, from the center of

Shape1, FULLY extended, if the line passes through Shape2 at any

point, then there is at least partial containment.

Yes, you can increment the angle by more than 1 degree as needed.

As long as this TEST LINE passes shape2 at any point, there is

at least partial containment.

You stated that you are not allowed to change the class hierarchy

of your geometry libraries, but did not and probably cannot

specify the classes involved.

If the shape is reprented by an array of points, you can calculate

the slope of, say one side of the shape from one vertex to the

next, and then the slope of the test line. If the slopes differ,

then the lines intersect and you can find the intersection point

via the formula:

x = (M2 - M1) / (B1 - B2)

You can then determine if this intersection point is in the set

of Shape2