Get the most average position of X objects on a path with Y available positions

Question

Hi,

Its friday, and in local time the clock is 3.22pm, so my brain wont give me a solution, so i ask:

Im trying to write a function/algorithm in Actionscript 3.0 that gives me the most average positions of x number of positions along a path of y number of available positions.

Y is always larger than X of course.

The background is, I got a map, with for example 50 possible placements of objects (along a path). But i only got 32 objects to place along this path, but i want their placements to be as average/even along that path as possible. So that it for example won't be a big gap at the end. My avaiable positions are at the moment stored in an array with point values.

If you just do totalPos/wantedPos and floor it, it will be a "ugly" gap at the end, any ideas?

EDIT:

I wanted to add the function incase anyone else wants it:

function place (x : uint, y : uint ) : Array
{
    var a : Array = new Array();
    var s : Number = y / x;
    var c : Number = 0;

    for (var i : Number = 0; i<x; i++) {
        c++;
        var pos : Number = Math.round(i * s);
        a.push(posArray[pos]);
    }
    return a;
}

Assumes you have an array posArray with the possible positions already...

Answer 1

If you do totalPos/wantedPos, you get a number that is likely not in int.

For example 32/7 = 4.57...

If you floor it and choose 4, then you do get a big gap at the end. However, if you accumulate the 4.57 and floor that, you will narrow the gap.

Again for example 32/7 = 4.57... So initially you choose 4. For the next number you get 2 * 4.57... = 9.14..., so you choose 9. Then 3 * 4.57... = 13.71 so you choose 13. Etc ...

It would probably be better if you rounded instead of floored.

Good luck :)

Answer 2

If I understand correctly, I think there is a basic algorithm for this kind of thing (but its been too long since school!). Basically, its a recursive call so you pass in the end points and it puts an object on the middle point. You then recurse with the start-to-middle as the first end-point, and the middle-to-end as the second. So you keep dividing the gaps by half.

As I type this, I realize this will only work if the number of objects to distribute is a square. However, I will leave the answer in case it gives someone else a better idea.