Circular In Range check

[elset191]

I am trying to create an algorithm that will tell me if two ranges of numbers overlap at all.  The ranges are defined by their center, and the span.  So the first element is center - span/2 and the last is center + span/2.  This in itself is easy enough to do, however the application requires that I work with numbers that are cyclical.

Say my numbers have possible values from 0-255.  Then if I have one range that is (center=255, range=6) and (center=2, range=4), these would overlap.

I've written code that works, but it looks very Rubey. What I do is if the center+range/2 exceeds the max I find two ranges.  For example, the (255,6) example above I would come up with 252-258 and -4 to 2.   Likewise, the (2,4) example above would give me 0-4 and 256-260.  With these sets of numbers I check all 8 possible combinations to see if one of them falls in the range.

252 <= 0 <= 258

252 <= 4 <= 258

-4 <= 0 <= 2

-4 <= 4 <= 2

0 <= 252 <= 4

0 <= 258 <= 4 

256 <= 252 <= 260

256 <= 258 <= 260

If at least one of these returns true, then the areas are deemed to overlap.

I couldn't convince myself that any fewer than these 8 comparisons would be enough catch all cases, but that may be the case.

Everything about my code screams Rube Goldberg at me, but I can not think of another way to do this.  So, I throw it to any of you who may have free time to tackle it.

[nathand]

Try this.  It gets the distance between the two centers (which is the lesser of the direct difference, or the remainder of the sum divided by the point at which the values wrap around), then checks to see if that distance is less than or equal to half the sum of the ranges.  I was tempted to provide only the description so you could have the fun of working out the implementation, since it's kind of a neat exercise - sorry for ruining that.

[JÞB]

Nicely done Nathan.

Modulus math seems to get forgotten a lot after 3rd grade- yet we all can tell time like "it is ten to eight" (o'clock).  

[elset191]

---

nathand wrote:

Try this.  It gets the distance between the two centers (which is the lesser of the direct difference, or the remainder of the sum divided by the point at which the values wrap around), then checks to see if that distance is less than or equal to half the sum of the ranges.  I was tempted to provide only the description so you could have the fun of working out the implementation, since it's kind of a neat exercise - sorry for ruining that.

---

 Yeah, I guess that's a little better than my solution.  Thanks a bunch.

[elset191]

One change I had to make (which I think is right) is decrementing pulses, because the range is 0 to pulses-1 rather than 1 to pulses.

Also, nathand, do you have any suggestions on finding the new center and span (they are getting combined into one super-range)?  My old algorithm was dependent on the rubeness of the first part.

[nathand · Accepted solution]

I started looking at how to do the super-range and discovered a problem in the first version I posted; try this one instead.

EDIT: a slightly neater alternative is to get rid of the first Max/Min and put an absolute value after the first subtraction instead; same result either way.

Message Edited by nathand on 04-08-2010 02:28 PM

[elset191]

That's a pretty subtle difference, unless I'm missing something.  Is it just an off by one error sometimes, or is there more to it?

Regarding the edit, yes I did that first thing.

[nathand]

My original approach failed when the sum of the centers was just less than the "pulses" value.  For example, centers at 250 and 3 gave a sum of 253 and a difference of 247, so the distance between them was calculated as 247 which isn't right.

I don't have a neat method for finding the combined center.  You can get the combined span by adding the two values going into the "less than or equal to."

[elset191]

---

nathand wrote: 

I don't have a neat method for finding the combined center.  You can get the combined span by adding the two values going into the "less than or equal to."

---

That doesn't quite work.  At least one case I have checked is when one range is completely within the other.  For example, (87,8) and (85,2) should remain 8 span (and center 87), but the method you described gives 7.  It's not always off by one, (87,8) and (87,2) gives 5, for instance.

[nathand]

---

elset191 wrote:

That doesn't quite work.  At least one case I have checked is when one range is completely within the other.  For example, (87,8) and (85,2) should remain 8 span (and center 87), but the method you described gives 7.  It's not always off by one, (87,8) and (87,2) gives 5, for instance.

---

Good point; I should have tested more thoroughly before suggesting that.  This has been a fascinating way to be unproductive for a few hours today, and if I'm ever looking for a programming puzzle for someone maybe I'll suggest this.  It may not be the most efficient implementation but I'm pretty sure the code below does what you need.  If I missed another case let me know.