2

Is there a known algorithm for finding if there exists an intersection between two ranges of degrees? It must be circular.

Ex. does 330 - 40 intersect with 20-50? (yes)

I know that, in general for a set of ranges, if the max of the mins is less than the min of the maxes, than they intersect, but the circular nature of degrees makes this a bit more complicated.

I currently have the following code. It seems to do exactly what I want it to, but it's very ugly. Anyone know of a better way to do this? Other than moving repetitive code into functions to make this look nicer? Ignore floating point comparison I'm just being lazy for this example

Note: I don't fmod 360 or -360 because it will result in 0 and screwing up the comparison. Ex. (5 - 360) inside of (350-20) --> would result in trying to figure out if (5 - 0) is inside of (350-20), now what? It seems to keep it more simple.

// Example program
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

bool bearingRangesIntersect(float p_fBearingMinDeg0, float p_fBearingMaxDeg0,     float p_fBearingMinDeg1, float p_fBearingMaxDeg1){

 // Normalize 
 if(p_fBearingMinDeg0 != -360.0f && p_fBearingMinDeg0 != 360.0f && (p_fBearingMinDeg0 < 0.0f || p_fBearingMinDeg0 > 360.0f)){
    p_fBearingMinDeg0 = fmod(p_fBearingMinDeg0, 360.0f);
    if(p_fBearingMinDeg0 < 0.0f){
      p_fBearingMinDeg0 += 360.0;
    }
 }
 if(p_fBearingMinDeg1 != -360.0f && p_fBearingMinDeg1 != 360.0f && (p_fBearingMinDeg1 < 0.0f || p_fBearingMinDeg1 > 360.0f)){
    p_fBearingMinDeg1= fmod(p_fBearingMinDeg1, 360.0f);
    if(p_fBearingMinDeg1< 0.0f){
      p_fBearingMinDeg1+= 360.0;
    }
 }
 if(p_fBearingMaxDeg0 != -360.0f && p_fBearingMaxDeg0 != 360.0f && (p_fBearingMaxDeg0 < 0.0f || p_fBearingMaxDeg0 > 360.0f)){
    p_fBearingMaxDeg0= fmod(p_fBearingMaxDeg0, 360.0f);
    if(p_fBearingMaxDeg0< 0.0f){
      p_fBearingMaxDeg0+= 360.0;
    }
 }
 if(p_fBearingMaxDeg1 != -360.0f && p_fBearingMaxDeg1 != 360.0f && (p_fBearingMaxDeg1 < 0.0f || p_fBearingMaxDeg1 > 360.0f)){
    p_fBearingMaxDeg1 = fmod(p_fBearingMaxDeg1, 360.0f);
    if(p_fBearingMaxDeg1 < 0.0f){
      p_fBearingMaxDeg1 += 360.0;
    }
 }

 // Make the min < max to respect comparison
 if(p_fBearingMinDeg0 > p_fBearingMaxDeg0){
    p_fBearingMinDeg0 -= 360.0f;
    if(p_fBearingMinDeg0 < -360.0f){
        p_fBearingMinDeg0 = fmod(p_fBearingMinDeg0, 360.0f);   
    }
 }

 if(p_fBearingMinDeg1 > p_fBearingMaxDeg1){
    p_fBearingMinDeg1 -= 360.0f;
    if(p_fBearingMinDeg1 < -360.0f){
       p_fBearingMinDeg1 = fmod(p_fBearingMinDeg0, 360.0f);   
    }
 }

 float fMaxOfMins = std::max(p_fBearingMinDeg0, p_fBearingMinDeg1);
 float fMinOfMaxs = std::min(p_fBearingMaxDeg0, p_fBearingMaxDeg1);

 return fMaxOfMins < fMinOfMaxs;
}

int main()
{

  // should be true
  bool result0 = bearingRangesIntersect(320,50,20,50);
  bool result1 = bearingRangesIntersect(-40,50, 20,50);
  bool result2 = bearingRangesIntersect(320,50,320,90);
  bool result3 = bearingRangesIntersect(-40,-90,-50,-80);

  // should be false
  bool result5 = bearingRangesIntersect(-40,50, 80,150);
  bool result6 = bearingRangesIntersect(181,270,-50,180);
  bool result7 = bearingRangesIntersect(300,50, 200, 270);
  bool result8 = bearingRangesIntersect(-120,-90, -40,-20);

  std::cout << "result0 = " << result0 << std::endl;
  std::cout << "result1 = " << result1 << std::endl;
  std::cout << "result2 = " << result2 << std::endl;
  std::cout << "result3 = " << result3 << std::endl;
  std::cout << "result5 = " << result5 << std::endl;
  std::cout << "result6 = " << result6 << std::endl;
  std::cout << "result7 = " << result7 << std::endl;
  std::cout << "result8 = " << result8 << std::endl;


  return 0;
}
Riptyde4
  • 5,134
  • 8
  • 30
  • 57
  • Since floating point number rarely turn out exactly, using `!=` such as in `fmod(p_fBearingMinDeg1, 360.0f) != 360.0f` may not be a good idea. Normally there is some error factor, epsilon used with floating point values. – Richard Chambers Jul 13 '17 at 21:02
  • Yes I was just lazy for this example hah. thanks – Riptyde4 Jul 13 '17 at 21:05
  • So your function `bearingRangesIntersect()` takes two sets of two bearings and determines whether they intersect or not? The first two arguments are the two bearings for the first set and the second two arguments are the two bearings for the second set and the function determines if the set of points along one arc of a circle, the arc specified by the first two arguments, overlaps or intersects the second arc of a circle, the arc specified by the second two arguments? – Richard Chambers Jul 13 '17 at 21:23
  • exactly @RichardChambers – Riptyde4 Jul 13 '17 at 21:25
  • And I suppose positive bearings are anti-clockwise around the circle and negative bearings are clockwise around the circle? It would seem you would want to do a normalize step in which the bearings are transformed into a single frame of reference, going anti-clockwise seems to be standard, and then checking for overlap. – Richard Chambers Jul 13 '17 at 21:31
  • Is there a reason to avoid the modulus operator? – Clay Siefken Jul 13 '17 at 21:33
  • @ClaySiefken floating point numbers – Riptyde4 Jul 13 '17 at 21:33
  • Rotations are different than bearings. Rotations are R, bearings are R mod 2pi. – Yakk - Adam Nevraumont Jul 13 '17 at 21:49
  • 1
    There are a lot of redundancies in this code, I think you could skip the `if` statements entirely and *always* use `fmod` for normalizing. And I'm curious, how could `fmod(x, 360.0) != 360.0` ever possibly be false? – Mark Ransom Jul 13 '17 at 22:51
  • @MarkRansom Ah, they're supposed to be checking if the fmod is equal to 0.0f - oops. I didn't want to fmod 360 because that would result in 0 value but I want to keep the value to calculate the intersection. I basically only want to fmod if its below 0, or over 360, and not equal to 360 or -360. – Riptyde4 Jul 14 '17 at 18:46

0 Answers0