CODEWITHSUNDEEP
algorithm
relaxxx
relaxxx

Reputation: 7824

intersection of two circular sectors

I am trying to solve simple task, but I am not finding any elegant solution.

I basically solving intersection of two circular sectors. Each sector is given by 2 angles (from atan2 func) within (-pi, pi] range. Each selector occupy maximum angle of 179.999. So it can be tell for every two angles where the circular sector is.

The return value should describe mutual intersection based on following:

value <1 if one angle is contained by second one (value represents how much space occupy percentually)

value >1 if first angle (the dotted one) is outside the other one, value represents how much of dotted angle is out of the other one

basic cases and some examples are on image bellow

enter image description here

the problem is that there are so many cases which should be handled and I am looking for some elegant way to solve it.

I can compare two angles only when they are on the right side of unit circle (cos>0) because on the left side, angle numerically bigger is graphically lower. I tried use some projection on the right half:

if(x not in <-pi/2, pi/2>)
{
    c = getSign(x)*pi/2;
    x = c - (x - c);
}

but there is a problem with sectors which occupy part of both halves of unit circle...

There are so many cases... Does somebody know how to solve this elegantly? (I use c++, but any hint or pseudocode is fine)

Upvotes: 8

Views: 2074

Answers (1)

coproc
coproc

Reputation: 6247

You can do the following:

  1. normalize each sector to the form (s_start, s_end) where s_start is in (-pi,pi] and s_end in [s_start,s_start+pi).
  2. sort (swap) the sectors such that s0_start < s1_start

  3. now we have only 3 cases (a, b1, b2):

    a) s1_start <= s0_end: intersection, s1_start inside s0

    b) s1_start > s0_end:

    b1) s0_start + 2*pi <= s1_end: intersection, (s0_start + 2*pi) inside s1

    b2) s0_start + 2*pi > s1_end: no intersection

Thus we get the following code:

const double PI = 2.*acos(0.);
struct TSector { double a0, a1; };

// normalized range for angle
bool isNormalized(double a)
{ return -PI < a && a <= PI; }
// special normal form for sector
bool isNormalized(TSector const& s)
{ return isNormalized(s.a0) && s.a0 <= s.a1 && s.a1 < s.a0+PI; }

// normalize a sector to the special form:
// * -PI < a0 <= PI
// * a0 < a1 < a0+PI
void normalize(TSector& s)
{
   assert(isNormalized(s.a0) && isNormalized(s.a1));

   // choose a representation of s.a1 s.t. s.a0 < s.a1 < s.a0+2*PI
   double a1_bigger = (s.a0 <= s.a1) ? s.a1 : s.a1+2*PI;
   if (a1_bigger >= s.a0+PI)
     std::swap(s.a0, s.a1);
   if (s.a1 < s.a0)
     s.a1 += 2*PI;

   assert(isNormalized(s));
}

bool intersectionNormalized(TSector const& s0, TSector const& s1,
                            TSector& intersection)
{
  assert(isNormalized(s0) && isNormalized(s1) && s0.a0 <= s1.a0);

  bool isIntersecting = false;
  if (s1.a0 <= s0.a1) // s1.a0 inside s0 ?
  {
    isIntersecting = true;
    intersection.a0 = s1.a0;
    intersection.a1 = std::min(s0.a1, s1.a1);
  }
  else if (s0.a0+2*PI <= s1.a1) // (s0.a0+2*PI) inside s1 ?
  {
    isIntersecting = true;
    intersection.a0 = s0.a0;
    intersection.a1 = std::min(s0.a1, s1.a1-2*PI);
  }
  assert(!isIntersecting || isNormalized(intersection));

  return isIntersecting;
}

main()
{
  TSector s0, s1;
  s0.a0 = ...
  normalize(s0);
  normalize(s1);
  if (s1.a0 < s0.a0)
    std::swap(s0, s1);
  TSection intersection;
  bool isIntersection = intersectionNormalized(s0, s1, intersection);
}

Upvotes: 5

Related Questions