两个圆形扇形的交集

Question

两个圆形扇形的交集

7

我正在尝试解决一个简单的任务，但是我没有找到任何优雅的解决方案。我主要在解决两个圆形扇区的交集问题。每个扇区由2个角度（从atan2函数）给出，范围为(-pi，pi]。每个选择器占据最大角度为179.999。因此，可以告诉每两个角度之间的圆形扇区所在位置。根据以下内容，返回值应描述互相交叉：如果一个角度包含在第二个角度中，则value＜1（value表示百分比占用空间的大小）如果第一个角度（虚线）在另一个角度外部，则value＞1（value表示虚线角度超出另一个角度的程度）下面是一些基本情况和示例图像。问题在于有许多需要处理的情况，我正在寻找一些优雅的方法来解决它。只有当两个角在单位圆的右侧（cos> 0）时，我才能比较它们，因为在左侧，数值上更大的角在图形上更低。我尝试在右侧使用一些投影：

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

但是有一个问题，涉及到占据单位圆的两个半部分的扇形...

有很多情况需要考虑... 有人知道怎样优雅地解决这个问题吗？（我使用c++，但任何提示或伪代码都可以）

- relaxxx

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- coproc · Accepted Answer

你可以执行以下操作：

将每个扇形标准化为形式 (s_start, s_end>)，其中 s_start 在 (-pi,pi] 范围内，而 s_end 在 [s_start,s_start+pi] 范围内。


交换扇形，使得 s0_start < s1_start
现在我们只有三种情况 (a, b1, b2):
a) s1_start <= s0_end：相交，s1_start 在 s0 中
b) s1_start > s0_end:
b1) s0_start + 2*pi <= s1_end：相交，(s0_start + 2*pi) 在 s1 中
b2) s0_start + 2*pi > s1_end: 不相交



因此我们得到以下代码:
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);
}