Re: what is the best way to implement this problem?
On Jan 27, 7:05 am, "Daniel T." <danie...@earthlink.net> wrote:
abir <abirba...@gmail.com> wrote:
This question may not be very specific to C++ , rather than C++ is
used as a language to implement it.
I have a set of points (a vector of ) as input for a system, just like
blackboard drawing.
where the point is defined as
struct point{ int x,int y;};
my job is to create an animal (or a few) out of those points. i may
even fail to create an animal if it doesn't look like any which i
know.
Your problem is a basic pattern matching problem. You have a set of
points and you have a sequence of points: the input pattern... and a
another container of sequences of points. It is your job to see how many
of the second container match the points in the first container. Each
sequence of points in the second container is associated with an animal.
Once you know which sequences from the second container match up, you
can create the correct animals.
Sorry, I had to run and didn't finish the above to my satisfaction...
At any rate, you have a sequence of points and a container of
sequences of points, and you want to see which sequences in the
container match the sequence you have. First you need a function that
can compare two sequences of points and determine if they are alike
(enough.)
bool alike(const vector<point>& a, const vector<point>& b);
and you need an association between a sequence of points and an
animal. You could do this in a number of ways, but the Prototype
pattern would probably be easist.
struct AnimalAssoc {
vector<point> pattern;
Animal* animal;
};
Now it is simply a matter of running through different patterns and
see which match.
vector<Animal*> animalsMade;
for ( AnimalAssocContainer::iterator it = animalFactory.begin();
it != animalFactory.end();
++it)
{
if (alike(myPattern, it->pattern))
animalsMade.push_back(it->animal->clone());
}