Algorithm Request: Comparison against a range that wraps

Author Message
vegipete

Guru

Joined: 29/01/2013
Location: Canada
Posts: 1182
Posted: 06:35pm 24 Jun 2021      

Does anyone have or can figure out an _elegant_ algorithm for determining if two values are within a certain range of each other when the allowable range wraps around?

For example, suppose I want to know if two times are within 5 minutes of each other.
Say 12:30 and and 12:27.
"IF ABS(time1 - time2) < deltatime THEN true" works fine except...
it fails with, say, 12:58 and 1:02 (assuming a 12 hour clock.)

I have something with 5 IF statements, plus some MODs, which just strikes me as ugly.

Is there a better way?
Visit Vegipete's *Mite Library for cool programs.
Mixtel90

Guru

Joined: 05/10/2019
Location: United Kingdom
Posts: 8964
Posted: 06:43pm 24 Jun 2021      

Convert all times to seconds since a fixed point, do the calculation then convert back?
jirsoft

Guru

Joined: 18/09/2020
Location: Czech Republic
Posts: 533
Posted: 07:27pm 24 Jun 2021      

  vegipete said  
it fails with, say, 12:58 and 1:02 (assuming a 12 hour clock.)


Is the difference between those 2 times 0:04 (12:58am, 1:02pm) or 11:56 (12:58pm, 1:02am)? You need to set the border conditions. But I'm not expert for 12 hour clock...
vegipete

Guru

Joined: 29/01/2013
Location: Canada
Posts: 1182
Posted: 09:23pm 24 Jun 2021      

I only give time as an example. Compass direction in degrees is much the same. 359 degrees is very close to 1 degree. Or screen pixels, where the edges wrap to the other side.

I haven't come up with a simple criteria yet for when to 'unwrap' one of the limits. For example, with 359 degrees, you would subtract 360, giving -1, which _is_ close to 1.
Mixtel90

Guru

Joined: 05/10/2019
Location: United Kingdom
Posts: 8964
Posted: 09:40pm 24 Jun 2021      

You don't allow it to wrap round. :)

a = b*(1*(b<360))

Any use? Have I got the right idea?
a is always equal to b until b=360 then a=0
Volhout
Guru

Joined: 05/03/2018
Location: Netherlands
Posts: 5994
Posted: 09:48pm 24 Jun 2021      

To determine the difference, you subtract a from b
To determine the difference in a case a wrap: add full range to b.
Then subtraxt
Then take modulus range
vegipete

Guru

Joined: 29/01/2013
Location: Canada
Posts: 1182
Posted: 11:44pm 24 Jun 2021      

Here's an example with degrees:

'target_angle' is where you want to be.
'current_angle' is where you are.
'tolerance' is whether you are close enough.
All angles are in degrees MOD 360, ie from 0 to 359.99whatever
angle_min = target_angle - tolerance
angle_max = target_angle + tolerance
if (angle_min < current_angle) AND (current_angle < target_max) then DoSomething
This won't work with wrapping.

Instead
angle_min = target_angle - tolerance
angle_max = target_angle + tolerance
if angle_min < 0 then
  if current_angle > angle_min+360 OR current_angle < angle_max then DoSomething
elseif angle_max >= 360 then
  if current_angle > angle_min OR current_angle < angle_max-360 then DoSomething
elseif angle_min < current_angle AND current_angle < angle_max then
  DoSomething
endif
works, but seems so convoluted and crazy. But maybe that's what is required.
phil99

Guru

Joined: 11/02/2018
Location: Australia
Posts: 3321
Posted: 01:51am 25 Jun 2021      

Vegipete's concept is the same as one I used for time, though different code and it works well. For angles another method is to convert numbers over 180 to negative. But only if they are within the "window" distance of 0 / 360.
Eg.

if (X > 180) AND (Y-window < 0)  then X = X - 360
if (Y > 180) AND (X-window < 0)  then Y = Y - 360

Then perform the tolerance window test.

Phil

Edit I think that's how it went, many years ago.
Edited 2021-06-25 12:02 by phil99
TassyJim

Guru

Joined: 07/08/2011
Location: Australia
Posts: 6546
Posted: 05:08am 25 Jun 2021      

The simplest is
diff = (new_angle-old_angle + 360) mod 360


You will have to decide if you want negative results or all positive. It depends on the usage.

MOD gives integer results so either multiply by 10 then MOD then divide by 10 etc or use another way to do MOD

dim float old_angle, new_angle, diff
do
input "both angles:", old_angle,new_angle
diff = (new_angle-old_angle + 360) mod 360 ' MOD gives integer results
print diff
diff = new_angle-old_angle + 360
if diff >= 360 then diff = diff - 360
print diff
print
loop


edit:
diff = (((new_angle-old_angle)*10 + 3600+1800) mod 3600)/10-180 ' 1 decimal place and negatives


Jim
Edited 2021-06-25 15:56 by TassyJim
phil99

Guru

Joined: 11/02/2018
Location: Australia
Posts: 3321
Posted: 06:09am 25 Jun 2021      

Found my old code fragment for compass. my previous post is messed up.

'window comparator
window=10 : x=356 : y=3
if (y>=360-window) and (x<window) then : y=y-360 :endif
if (x>=360-window) and (y<window) then : x=x-360 :endif
? abs(x-y)
if (abs(x-y) =< window) then : ?"within range" :else :? "No match" :endif
jirsoft

Guru

Joined: 18/09/2020
Location: Czech Republic
Posts: 533
Posted: 08:22am 25 Jun 2021      

I will prepare both values with MOD to  proper range 0-MAX, so you will have for example 2 values 0-359 for angle or 0:00-11:59 for 12-hour clock time.
Then if smallest difference
min(max(a,b)-min(a,b), WRAP+min(a,b)-max(a,b))
where WRAP is 360 for angle and 12:00 for time...
CaptainBoing

Guru

Joined: 07/09/2016
Location: United Kingdom
Posts: 2171
Posted: 09:12am 25 Jun 2021      

Two ways I use.

As already alluded-to, convert the times to unix/epoch time then compare (later MMBasics have Epoch time built in) but here is a Function  I use all the time on smaller Mites

If Abs(UnixTime(d1$)-UnixTime(d2$))<=300 Then...


... or (as already alluded-to) use DateDiff  (which uses UnixTime at its core) and the time period of your choice to do the same comparison

If Abs(DateDiff("m",d1$,d2$))<=5 Then ...


Neither of the above methods are fazed by the wrap around from 23:59 to 00:00
Edited 2021-06-25 19:17 by CaptainBoing
Volhout
Guru

Joined: 05/03/2018
Location: Netherlands
Posts: 5994
Posted: 09:54am 25 Jun 2021      

  jirsoft said  
min(max(a,b)-min(a,b), WRAP+min(a,b)-max(a,b))
where WRAP is 360 for angle and 12:00 for time...


Couldn't put it any more compact...
vegipete

Guru

Joined: 29/01/2013
Location: Canada
Posts: 1182
Posted: 05:55pm 25 Jun 2021      

There's some awesome ideas!

Jiri's version seems to be the hardest to break - I haven't been able to. I split it into 2 lines to simplify it slightly.
Phill's only works within the window. (Which suits my request.) His can't return an arbitrary difference.
TassyJim's only works 'forwards'. (359,1 is OK, 1,359 is not)

The neat thing is that all three have an underlying similarity. Plus they are more elegant than my brute force IF EVERYTHING method.

Thanks!

dim float old_angle, new_angle, diff
dim window = 10
do
input "both angles:", old_angle,new_angle

print "Phill99"
if (new_angle >= 360-window) AND (old_angle < window) then new_angle = new_angle - 360
if (old_angle >= 360-window) AND (new_angle < window) then old_angle = old_angle - 360
diff = abs(new_angle - old_angle)
print diff
print

print "TassyJim"
diff = new_angle-old_angle + 360
if diff >= 360 then diff = diff - 360
print diff
print

print "Jiri"
diff = max(old_angle,new_angle)-min(old_angle,new_angle)
diff = min(diff, 360-diff)
print diff
print

loop


Edit: might be able to simplify Jiri's some more:
diff = abs(old_angle - new_angle)
diff = min(diff, 360-diff)

Edited 2021-06-26 04:01 by vegipete