7

単純なタスクを解決しようとしていますが、エレガントな解決策が見つかりません。

私は基本的に2つの円形セクターの交差点を解決しています。各セクターは、(-pi, pi] の範囲内の 2 つの角度 (atan2 func から) によって指定されます. 各セレクターは最大角度 179.999 を占有します. したがって、2 つの角度ごとに円形セクターがどこにあるかがわかります.

戻り値は、以下に基づいて相互交差を表す必要があります。

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

基本的なケースといくつかの例は以下の画像にあります

ここに画像の説明を入力

問題は、処理する必要があるケースが非常に多く、それを解決するエレガントな方法を探していることです。

2 つの角度を比較できるのは、2 つの角度が単位円 (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_starts_ends_starts_start+pi
  2. s0_start<のようにセクターをソート (交換)s1_start

  3. 現在、3 つのケース (a、b1、b2) しかありません。

    a) s1_start <= s0_end: 交差点、s0 内の s1_start

    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);
}
于 2012-11-22T20:24:43.830 に答える