Algorithm to Encompassing a Set

[Sean Doherty]

It appears that it is more difficult than one would think to write an Algorithm to Encompassing a Set a set. Lets assume a 2 players and 2D screen full of pixels; each players owns half of the pixels on the screen.

What is you wanted to draw a line around the clusters of pixels owned by the sames player. Now what if you wanted to draw a smoth line around the clusters of pixels owned by the same players?

Not sure if anyone has givne this any though? But if you have I would be interested in what you came up with?

Thanks

[Jim Buck]

What is the difference between a line and a smooth line? You mean a curve?

[Sean Doherty]

What is the difference between a line and a smooth line? You mean a curve?

Yes, a curved line.

[luggage]

Off the top of my head, and I'm not 100% convinced this would work but...

First make a best fit rectangle. The following will get you that (but you'll want to amend it later).leftEdge = 640;
rightEdge = 0;
topEdge = 480;
bottomEdge = 0;

for each pixel...

if (x < leftEdge) leftEdge = x;
if (y < topEdge) topEdge = y;
if (x > rightEdge) rightEdge = x;
if (y > bottomEdgeEdge) bottomEdgeEdge = y;Now each of the pixels that contributed to the edge (ie. any that passed one of the 'if' tests above) put into a list. You will also need to put any that are also on the edge (ie. if you have two pixels with an x of 4 then both of these needed to be added to the list.

With that list of points generate a catmull-rom curve. Best look up Catmull-Rom on the web they're quite straightforward (and D3DX has a function in there for you).

Basically you give it at least four points (you can supply it duplicate points if you have less than 4 points in your list. This will generate a spline which will go through each of those points. The you just plot that.

If you need the catmull-rom code just give me a shout.

[Rainer Deyke]

First smooth the data. Give each pixel a value of 1.0 if it belongs to player 1 and -1.0 if it belongs to player 2. Give each pixel a new value that is a weighted average of its old value and the values of its old neighbors. Repeat until the desired level of smoothness is reached is reached.

All positive pixel values belong to player 1 and all negative pixel values belong to player 2. To draw the boundary between them, color each pixel that belongs to a different player than any one of its neighbors. For a thinner line, only examine the bottom right neighbor.

[luggage]

Bah. Just realised my method would fail in certain circumstances. You'd have to take into account any pixels which are 'near' the edge of the bounding rectangle.

I suppose instead of taking the pixel approach you could split the screen into smaller squares, it's a flagged square if it has a pixel inside it.

You could then maybe just start with the bounding rectangle around these smaller squares. Then for each square on a row look for the left one. If it's not the very edge adjust it left a bit (don't want the curve too close). Do this so you get a rough outline then use the CatmullRom based on these squares. Basically use a de-ressed grid to fuzzy it up a little.

[Sean Doherty]

Bah. Just realised my method would fail in certain circumstances. You'd have to take into account any pixels which are 'near' the edge of the bounding rectangle.

I suppose instead of taking the pixel approach you could split the screen into smaller squares, it's a flagged square if it has a pixel inside it.

You could then maybe just start with the bounding rectangle around these smaller squares. Then for each square on a row look for the left one. If it's not the very edge adjust it left a bit (don't want the curve too close). Do this so you get a rough outline then use the CatmullRom based on these squares. Basically use a de-ressed grid to fuzzy it up a little.

Ya, I think your code would enclose some pixels from the other player. If you have CatmullRom code hat does not use DirectX that would be great!

[Sean Doherty]

First smooth the data. Give each pixel a value of 1.0 if it belongs to player 1 and -1.0 if it belongs to player 2. Give each pixel a new value that is a weighted average of its old value and the values of its old neighbors. Repeat until the desired level of smoothness is reached is reached.

All positive pixel values belong to player 1 and all negative pixel values belong to player 2. To draw the boundary between them, color each pixel that belongs to a different player than any one of its neighbors. For a thinner line, only examine the bottom right neighbor.

Not sure I am following your weighted average?

[Rainer Deyke]

Not sure I am following your weighted average?

new_pixel(x, y) = pixel(x - 1, y - 1) * 0.025
+ pixel(x - 1, y) * 0.1
+ pixel(x - 1, y + 1) * 0.025
+ pixel(x, y - 1) * 0.1
+ pixel(x, y) * 0.5
+ pixel(x, y + 1) * 0.1
+ pixel(x + 1, y - 1) * 0.025
+ pixel(x + 1, y) * 0.1
+ pixel(x + 1, y + 1) * 0.025;

Repeat as necessary. Tweak the numbers until you get the desired effect.

[Sharkbait]

Rainer's idea seems like the best solution, but there is still another problem to content with: What if the pixels of one player are in two or more disjoint clusters? For example, Player 1 has pixels in two opposite corners, while Player 2 has pixels occupying the middle.

[luggage]

Oh. I didn't realise that it wasn't to cover any of the other players pixels. It certainly wouldn't work then! Here's the Catmull-Rom code in case it's any use for anyone.

You use it the same as you would the D3DX function. Bit of info here.
http://www.mvps.org/directx/articles/catmull/

And a blitz demo here...
http://www.bigfizz.com/catmull.zip
Any problems just drop me a message.

pCgVector3D CgVector3D_Add(pCgVector3D r, pCgVector3D a, pCgVector3D b) {

r->x = (a->x + b->x);
r->y = (a->y + b->y);
r->z = (a->z + b->z);

return r;
}

pCgVector3D CgVector3D_Scale(pCgVector3D r, pCgVector3D a, FP f) {

r->x = a->x * f;
r->y = a->y * f;
r->z = a->z * f;

return r;
}

pCgVector3D CgVector3D_CatmullRomInterpolate(pCgVector3D result, pCgVector3D v1, pCgVector3D v2, pCgVector3D v3, pCgVector3D v4, FP delta) {

CgVector3D c1, c2, c3, c4, temp;

c1 = *v2;

CgVector3D_Scale(&c2, v1, -0.5f);
CgVector3D_Scale(&temp, v3, 0.5f);
CgVector3D_Add(&c2, &c2, &temp);

CgVector3D_Scale(&temp, v2, -2.5f);
CgVector3D_Add(&c3, v1, &temp);
CgVector3D_Scale(&temp, v3, 2.0f);
CgVector3D_Add(&c3, &c3, &temp);
CgVector3D_Scale(&temp, v4, -0.5f);
CgVector3D_Add(&c3, &c3, &temp);

CgVector3D_Scale(&c4, v1, -0.5f);
CgVector3D_Scale(&temp, v2, 1.5f);
CgVector3D_Add(&c4, &c4, &temp);
CgVector3D_Scale(&temp, v3, -1.5f);
CgVector3D_Add(&c4, &c4, &temp);
CgVector3D_Scale(&temp, v4, 0.5f);
CgVector3D_Add(&c4, &c4, &temp);

CgVector3D_Scale(result, &c4, delta);
CgVector3D_Add(result, result, &c3);
CgVector3D_Scale(result, result, delta);
CgVector3D_Add(result, result, &c2);
CgVector3D_Scale(result, result, delta);
CgVector3D_Add(result, result, &c1);

return result;
}

[Sean Doherty]

Rainer's idea seems like the best solution, but there is still another problem to content with: What if the pixels of one player are in two or more disjoint clusters? For example, Player 1 has pixels in two opposite corners, while Player 2 has pixels occupying the middle.

Ya, I was really thinking of the issue in terms of which players owns a particular star system. As such, it is more than possible for players to own star systems all over the place. I think the Catmull-Rom code might work in conjunction once the corners of the groups have been identified. Not really sure how to find a corner since the x & y could be in conflict?

[Rod Hyde]

I suspect that I may be redefining the problem slightly, but taking Rainer's idea a little further, could you draw the areas of influence as a "gravity well" rather than by drawing curves?

This way, player 1's pixels contribute positive weights to the local gravity and player 2's pixels contribute negative weights. You would then shade each area (let's say red for player 1 and blue for player 2) according to its gravity.

If an area contained significantly more of player 1's pixels than player 2's, then that area would show up with an opaque red. If player 1 was only slightly more ascendant than player 2 then the red would be close to transparent. If it contained an even mix of both players then it would be a neutral colour. If player 2 was dominant in that area then it would be mostly blue, starting from almost transparent for hardly any dominance to totally opaque for full dominance.

This would show both the area of influence, and the amount of influence, without having to draw a curve around an area.

The granularity doesn't necessarily have to go as low as one pixel. You could count the number of pixels of each colour within a grid square then attach the weights to squares rather than to individual pixels.

--- Rod

[Mark Sheeky]

Or to put it graphically, assume that the pixels are red for one player and blue for the other and do a big gaussian blur to show the areas of influence.

Mark

[Sean Doherty]

I suspect that I may be redefining the problem slightly, but taking Rainer's idea a little further, could you draw the areas of influence as a "gravity well" rather than by drawing curves?

This way, player 1's pixels contribute positive weights to the local gravity and player 2's pixels contribute negative weights. You would then shade each area (let's say red for player 1 and blue for player 2) according to its gravity.

If an area contained significantly more of player 1's pixels than player 2's, then that area would show up with an opaque red. If player 1 was only slightly more ascendant than player 2 then the red would be close to transparent. If it contained an even mix of both players then it would be a neutral colour. If player 2 was dominant in that area then it would be mostly blue, starting from almost transparent for hardly any dominance to totally opaque for full dominance.

This would show both the area of influence, and the amount of influence, without having to draw a curve around an area.

The granularity doesn't necessarily have to go as low as one pixel. You could count the number of pixels of each colour within a grid square then attach the weights to squares rather than to individual pixels.

--- Rod

What if I add a thrid palyer to the problem?

[Rod Hyde]

What if I add a third player to the problem?I was afraid that you'd ask that! My first thought is that now you would have to calculate the gravity map on a player by player basis. The player whose gravity well is deepest at any given point in the map would own that point. The degree of ownership would be related to the difference in depth between that player's gravity well and those of the other players at the same point.

I would also be tempted to implement a cut-off value so that a difference in depth smaller than the cut-off value would mean no control.

--- Rod

[Sean Doherty]

I was afraid that you'd ask that! My first thought is that now you would have to calculate the gravity map on a player by player basis. The player whose gravity well is deepest at any given point in the map would own that point. The degree of ownership would be related to the difference in depth between that player's gravity well and those of the other players at the same point.

I would also be tempted to implement a cut-off value so that a difference in depth smaller than the cut-off value would mean no control.

--- Rod

I going to try to implement it using a 3 dimensional array.

GravityMap[x][y][Number of Player]

At least I will see what kind of value I can produce. If anyone has a beter idea?

[Mark Sheeky]

You can still work the gravity algorithm in several dimensions, just remove antigravity and have a separate number for each player.

Assign a value for each player to each item. Check the type and range of each other item and make the number for that type go up by a value inversely proportional to the distance.

Mark