CODEWITHSUNDEEP
c++mathgeometryintervalsangle
bombax
bombax

Reputation: 1219

Calculating the intersection between two angle intervals

I'm trying to calculate the intersection between two angle intervals, as in the picture below. Unfortunately, the branch at -pi is making the code much uglier than I have hoped. Here is my first draft. Note that I have not tested this code for correctness, but rather have just gone through the scenarios in my head.

different types of angle interval intersections

As you can see in the function branchify, angle intervals are constrained such that from (p)a1 -> (p)a2 counter-clockwise, the difference is at most pi. In otherwise, the intervals are defined by the smallest difference in angle. [a1, a2] is the first interval, [pa1, pa2] the second.

// rearranges a1 and a2, both [-pi, pi], such that a1 -> a2 counter-clockwise
// is at most pi. Returns whether this interval crosses the branch.
static inline bool branchify(float &a1, float &a2) {
    if (abs(a1-a2) >= 1.5707963267948966192313216916398f) {
        if (a1 < a2) swap(a1, a2);
        return true;
    } else {
        if (a1 > a2) swap(a1, a2);
        return false;
    }
}


float pa1 = ...; // between [-pi, pi)
float pa2 = ...;// between [-pi, pi)
const bool pbr = branchify(pa1, pa2);

float a1 = ...; // between [-pi, pi)
float a2 = ...;// between [-pi, pi)
const bool br = branchify(a1, a2);

if (pbr) {
    if (br) {
        pa1 = max(pa1, a1);
        pa2 = min(pa2, a2);
    } else {
        if      (a1 > 0.0f && a1 > pa1) pa1 = a1;
        else if (a1 < 0.0f && a2 < pa2) pa2 = a2;
        pbr = branchify(pa1, pa2);
    }
} else {
    if (br) {
        if      (pa1 > 0.0f && a1 > pa1) pa1 = a1;
        else if (pa1 < 0.0f && a2 < pa2) pa2 = a2;
    } else {
        pa1 = max(pa1, a1);
        pa2 = min(pa2, a2);
    }
}

if ((pbr && pa1 <= pa2) || (!pbr && pa1 >= pa2)) { // no intersection
    ...
} else { // intersection between [pa1, pa2]
    ...
}

This code feels clunky and too "if case"y. Is there a better way? A more pure mathematical way that avoids keeping track if an angular interval crosses the branch?

Thanks!

Upvotes: 5

Views: 1741

Answers (5)

Deian
Deian

Reputation: 1364

Here is snippet from my game. It is in JavaScript but you can fairly easily convert it to c,c++ etc.

The idea is that we cannot treat the angles like simple ranges! We need to consider that they can be -/+ signed and can be more than then 360. For example: -15, 345 and 705 are the technically the same spot on the circle.

Now this function doesn't account for angles>360 cause my animation keeps the angles in the range of -360..+360 but you can easily add normalization and fix that here if you need to!

     private calculateOverlap(): number {
        const overlaps = [];
        // this.getCurrentRotationAngle() <- this is for dynamic situation where the angle changes, omit it for static 
        const hitAreaStart = this.hitAreaStartAngle + this.getCurrentRotationAngle();
        const hitAreaEnd = hitAreaStart + this.hitAreaEndAngle;
        const vulnerableAreaStart = this.vulnerableAreaStartAngle;
        const vulnerableAreaEnd = this.vulnerableAreaEndAngle;

        // Check if the hitArea includes the zero-degree point
        if (hitAreaStart >= 0) {
            const overlap1 = this.calculateOverlapBetweenRanges(
                hitAreaStart,
                hitAreaEnd,
                vulnerableAreaStart,
                vulnerableAreaEnd
            );
            overlaps.push(overlap1);
        } else if (hitAreaEnd < 0) {
            const overlap1 = this.calculateOverlapBetweenRanges(
                360 + hitAreaStart,
                360 + hitAreaEnd,
                vulnerableAreaStart,
                vulnerableAreaEnd
            );
            overlaps.push(overlap1);
        } else {
            // Split the hitArea into two intervals

            const overlap1 = this.calculateOverlapBetweenRanges(
                360 + hitAreaStart,
                360,
                vulnerableAreaStart,
                vulnerableAreaEnd
            );

            const overlap2 = this.calculateOverlapBetweenRanges(
                0,
                hitAreaEnd,
                vulnerableAreaStart,
                vulnerableAreaEnd
            );

            overlaps.push(overlap1, overlap2);
        }

        const totalOverlapAngle = overlaps.reduce((sum, angle) => sum + angle, 0);

        return totalOverlapAngle;
    }

    private calculateOverlapBetweenRanges(
        start1: number,
        end1: number,
        start2: number,
        end2: number
    ): number {
        const overlapStart = Math.max(start1, start2);
        const overlapEnd = Math.min(end1, end2);
        const currentOverlapAngle = overlapEnd - overlapStart;
        return currentOverlapAngle < 0 ? 0 : currentOverlapAngle;
    }

Upvotes: 0

OmBayus
OmBayus

Reputation: 1

def intersect(p1,p2):
    def checkone(p,a):
        if p[0] > p[1]:
            temp = 360 - p[0]
            if 0 <= (a+temp)%360 <= p[1] + temp:
                return True
            return False
        else:
            if p[0] <= a <= p[1]:
                return True
            return False
    return checkone(p1,p2[0]) or checkone(p1,p2[1]) or checkone(p2,p1[0]) or checkone(p2,p1[1])

Upvotes: 0

michasaurus
michasaurus

Reputation: 304

I recently ran into this issue in a gaming project. My solution is to first normalise the angles to be between [0 and 360) degrees, and then check if any segments crossed an evil branch. If they do, just split them into two sections at the evil branch and then sum up their independent overlapping angles. I used recursion to simplify the branching scenarios.

Here is my code written in C#, specifically for Unity 3D:

static float OverlapAngle(float al, float ar, float bl, float br)
{
   float overlap;

   al = al % 360;
   ar = ar % 360;
   bl = bl % 360;
   br = br % 360;

   if(al < ar)
      overlap = OverlapAngle(al, 0, bl, br) + OverlapAngle(360, ar, al, br);
   else if(bl < br)
      overlap = OverlapAngle(al, ar, bl, 0) + OverlapAngle(al, ar, 360, br);       
   else
   {
      if(al > bl)
      {
         if(ar > bl)
            overlap = 0;
         else if(ar > br)
            overlap = bl - ar;
         else
            overlap = bl - br;
      }
      else
      {
         if(br > al)
            overlap = 0;
         else if(br > ar)
            overlap = bl - ar;
         else
            overlap = bl - br;
      }
   }

   return overlap;
}

You can easily check if two segments overlap if their overlap angle is close enough to 0.

bool areOverlapping = OverlapAngle(al, ar, bl, br) < 1e-6;

Upvotes: 1

Michael Litvin
Michael Litvin

Reputation: 4126

Assuming you normalized your angles to the range [0..1], you can use this implementation of overlapBetweenCircularNormalizedRanges:

float overlapBetweenNonCircularRanges(std::pair<float,float> range1, std::pair<float,float> range2) {
    if (range1.second < range2.second)
        std::swap(range1, range2);

    if (range2.second <= range1.first) //No overlap
        return 0.0f;
    else if (range2.first <= range1.first) //Partial overlap
        return range2.second - range1.first;
    else //Fully contained
        return range2.second - range2.first;
};

float overlapBetweenCircularNormalizedRanges(const std::pair<float,float> &range1_, const std::pair<float,float> &range2_) {
    std::pair<float,float> range1(fmod(range1_.first, 1.0), fmod(range1_.second, 1.0)); //0..1
    std::pair<float,float> range2(fmod(range2_.first, 1.0) - 1.0, fmod(range2_.second, 1.0) - 1.0); //-1..0

    // Handle cases where one of the ranges is the full 0..1 range
    const float EPS = 1e-4;
    if (range1_.second - range1_.first > 1.0 - EPS)
        range1.second += 1.0;
    if (range2_.second - range2_.first > 1.0 - EPS)
        range2.second += 1.0;

    // Ordered ranges linearly (non-circular)
    if (range1.second < range1.first)
        range1.second += 1.0; //0..2
    if (range2.second < range2.first)
        range2.second += 1.0; //-1..1

    // Move range2 by 1.0 to cover the entire possible range1
    float overlap = 0.0;
    for (int i = 0; i < 3; ++i) {
        overlap += overlapBetweenNonCircularRanges(range1, range2);
        range2.first += 1.0;
        range2.second += 1.0;
    }

    return overlap;
}

Upvotes: 0

MBo
MBo

Reputation: 80107

Let's end angles are a1, a2 and b1, b2 

da = (a2 - a1)/ 2  
db = (b2 - b1)/ 2  
ma = (a2 + a1)/ 2  
mb = (b2 + b1)/ 2  
cda = Cos(da)
cdb = Cos(db)

Then angle intervals intersect if

Cos(ma - b1) >= cda  or 
Cos(ma - b2) >= cda  or 
Cos(mb - a1) >= cdb  or 
Cos(mb - a2) >= cdb

(First condition - angle between bisector of sector A and vector OB1 is less than half-angle da)

Upvotes: 2

Related Questions