Thread:User talk:Wompi/Questions/reply (9)

I also thought there might be some issues at certain angles with the single loop approach.

I think you need to take a <math>n^2</math> approach, ie, a loop within a loop. Otherwise you need to use a sorting technique (with nlogn), then a single loop. Here is pseudocode:

initialise min_sum = Inf
For each bot, b:
    me_b = find the angle from me to b
    initialise min_rel = Inf, max_rel = -Inf.
    for each bot c, excluding b:
        me_c = find the angle from me to c
        rel = the relative angle between me_b and me_c
        if rel < min_rel, min_rel = rel. if rel > max_rel, max_rel = rel.
    sum = max_rel - min_rel
    if sum < min_sum, min_sum = sum, min_ang = me_b + min_rel, max_ang = me_b + max_rel.

The other approach would be to sort all the angles into radial order, then go through looking for the largest space between two angles, and then use the opposite part of the circle. So in pseudocode:

for each bot, b:
    me_b = angle from me to b
    angles[i++] = me_b

sort_ascending(angles)

max_rel = abs(relative_angle(angles[0] - angles[angles.length - 1]))
min_angle = angles[0]
max_angle = angles[angles.length-1]
max_index = 0
for(i = 1; i < angles.length; i++)
    rel = abs(relative_angles(angles[i-1] - angles[i]));
    if rel > max_rel
        max_rel = rel
        min_angle = angles[i]
        max_angle = angles[i-1]
        max_index = i