Grouping colored people

[RaymondXie]

I have a question for discussion:

Suppose there are a group of people wearing in different colors. They are standing in a playground according the following rules:
1. Each color stands in its own line, Red in line 1, Green in line 2, ....
2. Each people in its own line can stand anywhere in that line, not necessary side by side
3. Using a 2D coordinate system to represent this scenario, every one has a unique [x, y], x is the position, y is the color

Now, looking down to this crowd from sky, you will these peoples forms some groups, some group has 2 or three colors, some might have all the colors, the size of each group is different.

The question is:

How do I find out a [Xmin, X1, X2, ..., Xmax], in that range, there are all the colors in it(some color might have more than 2 people, but at least one is required)

This means looking from sky, you will find the most crowdy and complete group.

I need the coordinate pair of all the people in the range.

[Zachm]

Have a look at this (http://www.codeguru.com/forum/showthread.php?t=439321) thread.

It is a similar problem to yours - you just need to alter the algorithm a bit in order to keep track of which colors are represented in each group.

Regards,
Zachm

[RaymondXie]

Thanks for your reply, I haven't figured out how the algorithm applies to my problem, they seem to be different problems, let me try to illustrate my question again:

Line1:x0000000x000x000000x000000000x0x000x...
Line2:000x0000000x0000x0000x0000000x0x0000000x00...
Line3:0x0000000x0000x00000x0000x00000x000x00x...
Line4:0000000000000000000x000000000000000000000...
Now, as seen by human, it is clear(clearer if I can use color here) that there are some groups with all appearance of the three colors very close (or they are crowded group)

The x-border of the crowded group is what I am looking for.

[Zachm]

If anything, I think you made it less clearer :)
"The x-border of the crowded group is what I am looking for"

What is the meaning of "x-border" ?
I thought you needed to find the group with most different colors in it. If you map all possible groups using the flood-fill algo, then you can check which colors exist in each group and pick the group with most colors.

Maybe I misunderstood what you mean by "group" as I see a group by a bunch of x's that form a cluster in which there is a path of only x's between each 2 individual x's in the group, where the only allowed movements are between neighboring x's. Neighboring could mean vertically / horizontally or even diagonally in neighboring cells of your 2D array.

If I am mistaken, please elaborate more on the problem.

Regards,
Zachm

[RaymondXie]

Hi,

Thanks for your reply, I feel Flood Fill algorithm might somehow help although I haven't figured it out, I've created a picture for better understanding, please see the attachment. Question remaining: if using Flood Fill, since the appearance of different color points might not necessarily connect together, even in the final result, those points might still scatter in the picture, then how does the algorithm decide the cluster? that algorithm seems working great for Windows' mine-sweeper game but I don't know how to apply it here in my question. In the picture I created as example, points are already very crowded , but in real scenario, all the points might well scatter in the plane and far away from each other.

[Zachm]

If you need to find the crowdest cluster in terms of distance from each individual to the next, then flood fill won't do the job since flood-fill requires the individuals to be neighboring to each other, otherwise it can't "flood-fill" the group.
Finding arbitrary clusters in 2D space may be a difficult task with no perfect quick answer.
Consider using "K-means"(google it) or other heuristic methods if this is your case.

Regards,
Zachm.

[pm_kirkham]

For the scenario where you have each colour on its own y value, you can scan the upper bound on the x co-ordinate and keep a count for each colour you find. When all counts are non-zero, then for each new person found scan the lower bound up until the count of any colour would reduce to zero. doing this over the entire range for the x values, keeping track of the bounds corresponding to the most crowded range.