Difference between revisions of "Thread:User talk:Wompi/Questions/reply (9)"

From Robowiki
Jump to navigation Jump to search
(Reply to Questions)
 
(fix code)
 
Line 7: Line 7:
 
For each bot, b:
 
For each bot, b:
 
     me_b = find the angle from me to b
 
     me_b = find the angle from me to b
     initialise min_rel = Inf, max_rel = Inf, sum = 0.
+
     initialise min_rel = Inf, max_rel = -Inf.
 
     for each bot c, excluding b:
 
     for each bot c, excluding b:
 
         me_c = find the angle from me to c
 
         me_c = find the angle from me to c
Line 15: Line 15:
 
     if sum < min_sum, min_sum = sum, min_ang = me_b + min_rel, max_ang = me_b + max_rel.
 
     if sum < min_sum, min_sum = sum, min_ang = me_b + min_rel, max_ang = me_b + max_rel.
 
</pre>
 
</pre>
The other approach would be to sort all the angles into radial order, then go through looking for the largest gap between two angles, and then use the opposite part of the circle. So in pseudocode:
+
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:
  
 
<pre>
 
<pre>

Latest revision as of 08:37, 25 April 2012

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