7

我正在尝试解决简单的任务，但我没有找到任何优雅的解决方案。

我基本上解决了两个圆形扇区的交集。每个扇区由 (-pi, pi] 范围内的 2 个角度 (来自 atan2 func) 给出。每个选择器占据的最大角度为 179.999。因此每两个角度就可以知道圆形扇区在哪里。

返回值应基于以下描述相互交集：

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

基本案例和一些例子在下面的图片中

在此处输入图像描述

问题是有太多的案例需要处理，我正在寻找一些优雅的方法来解决它。

只有当它们位于单位圆的右侧（cos> 0）时，我才能比较两个角度，因为在左侧，数值较大的角度在图形上较低。我尝试在右半部分使用一些投影：

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

但是占据单位圆两半部分的扇区存在问题......

有很多案例......有人知道如何优雅地解决这个问题吗？（我使用 c++，但任何提示或伪代码都可以）

4

1 回答 1

4

您可以执行以下操作：

  1. 将每个扇区标准化为 ( s_start, s_end) 形式，其中s_start位于 (-pi,pi] 和s_end[ s_start, s_start+pi) 中。
  2. 对扇区进行排序（交换），使得s0_start<s1_start

  3. 现在我们只有 3 个案例（a、b1、b2）：

    a) s1_start <= s0_end: 交点，s1_start 内 s0

    乙）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);
}
于 2012-11-22T20:24:43.830 回答