4

同心円との交点に応じて、塗りつぶしの色が異なる長方形を描画する必要があります。示されている画像は、シナリオについてのより良いアイデアを提供します ここに画像の説明を入力してください （表現目的のみ）

現在、ピタゴラスの定理を適用して、各ポイントのステータスを確認しています。

擬似コード：

SquareOf Point中心からの距離（sqrOfDistance）= square（point X-Circle center X）+ square（point Y-Circle center Y）

これらの値を半径の2乗（sqrOfInnerR）と比較します

if  sqrOfDistance == sqrOfInnerR
    Inline
else if sqrOfDistance > sqrOfInnerR
    Out
else 
    In

現在のロジックは機能しますが、これらのチェックを各ポイント（4回または8回）で実行し、最後に一緒に実行して状態を判別する必要があります。私の実際のアプリケーションでは、約3,000,000個の長方形が画像に表示されます。

private RectState CheckTheRectangleState(Rect rect, double radius, bool firstCall = true)
        {
            double SquareOfRadius = Square(radius);
            var _x = rect.X - ControlCenter.X;
            var _y = rect.Y - ControlCenter.Y;

            var squareOfDistanceToTopLeftPoint = Square(_x) + Square(_y);
            var squareOfDistanceToTopRight = Square(_x + rect.Width) + Square(_y);
            var squareOfDistanceToBottonLeft = Square(_x) + Square(_y + rect.Height);
            var squareOfDistanceToBottonRight = Square(_x + rect.Width) + Square(_y + rect.Height);

            var topLeftStatus = squareOfDistanceToTopLeftPoint == SquareOfRadius ? PointStatus.Inline : (squareOfDistanceToTopLeftPoint > SquareOfRadius ? PointStatus.Out : PointStatus.In);
            var topRightStatus = squareOfDistanceToTopRight == SquareOfRadius ? PointStatus.Inline : (squareOfDistanceToTopRight > SquareOfRadius ? PointStatus.Out : PointStatus.In);
            var bottonLeftStatus = squareOfDistanceToBottonLeft == SquareOfRadius ? PointStatus.Inline : (squareOfDistanceToBottonLeft > SquareOfRadius ? PointStatus.Out : PointStatus.In);
            var bottonRightStatus = squareOfDistanceToBottonRight == SquareOfRadius ? PointStatus.Inline : (squareOfDistanceToBottonRight > SquareOfRadius ? PointStatus.Out : PointStatus.In);

            if ((topLeftStatus == PointStatus.In || topLeftStatus == PointStatus.Inline) &&
                (topRightStatus == PointStatus.In || topRightStatus == PointStatus.Inline) &&
                (bottonLeftStatus == PointStatus.In || bottonLeftStatus == PointStatus.Inline) &&
                (bottonRightStatus == PointStatus.In || bottonRightStatus == PointStatus.Inline))
            {
                return firstCall ? RectState.In : RectState.Partial;
            }
            else
            {
                if (firstCall)
                    CheckTheRectangleState(rect, outCircleRadius, false);
            }
            return RectState.Out;
        }
    }

ここで、Square（）はsquareを取得するためのカスタム関数です。 Square(x){ return x*x;} PointStatusとRectStateは、ポイントのステータスを判別するための列挙型です。

4

4 に答える 4

2

多くの長方形を扱っていて、それらのほとんどがほとんどの場合円の外側にある場合、早期終了方法でチェックを最適化する 1 つの方法は、最初に円を囲む正方形を(- から)想像することです。r,-r) から (r,r) まで、ここで r は円の半径、円の中心は (0,0) で、四角形がこの正方形内にあるかどうかを確認します。これははるかに高速で、円との衝突のチェックは、これが成功した場合にのみ行う必要があります。

編集: @hvd は、早期終了のポジティブ チェックに関する優れたアイデアを追加しました。長方形が内側の正方形の中にある場合、それは間違いなく円の中にあります。

長方形と円のサイズによっては、1 レベル深くして、内側の正方形と円の間に長方形を作成することもできます。ただし、クエリされた長方形のポイントがすべて任意の長方形 (+ 内側の正方形) 内にあることを確認する必要があり、それらすべてが同じ長方形内にある必要はありません。

于 2012-11-28T08:58:07.920 に答える
1

したがって、ほとんどの場合、正方形は円であると判断でき、作業がより簡単になります。そんな風に見えるだろう

float distance = Distance(LargeCircle.center, square.center);
if (distance > LargeCircle.radius){
    //two cases here, we can be outside of circle, or intersect it
} else {
    //two cases again. We can be inside a circle, or intersect it
}

それが役立つことを願っています

于 2012-11-28T09:08:13.590 に答える
0

@KarthikTの提案にコメントしてください。長方形で円を表すと、次のように確認できます。

  • 円の上限より上に上限がある長方形を無視する
  • 円の下限よりも下限が低い長方形は無視してください
  • 円の左境界の前に左境界を持つ長方形を無視します
  • 円の右境界の後に右境界を持つ長方形を無視します
  • 残りは中にあるものです

したがって、チェックは8つではなく4つだけです。

その後、円を象限に分割し、長方形をケースに分類できます。

  • 右下隅が左上の象限にある場合-左上隅のみを確認します（距離で）
  • 左下隅が右上の象限にある場合-右上隅のみを確認します
  • 右上隅が左下の象限にある場合-左下隅のみを確認します
  • 左上隅が右下の象限にある場合-右下隅のみを確認します
  • 右下隅と左下隅が正方形の上半分にある場合-左上隅と右上隅のみを確認します
  • ..。
  • 残り（各コーナーが独自の象限にあるもの）は、距離によってすべてのコーナーをチェックします。

更新：実際には、最初のターンで長方形を分類し、次に正方形の外側でフィルターアウトしてから、ケースごとにフィルターアウトする方がはるかに優れています。

コードのサンプル： 

struct Vec {
    public double X, Y;
    public Vec Offset(Vec d) { return new Vec { X = X + d.X, Y = Y + d.Y }; }
    public Vec Negate() { return new Vec { X = -X, Y = -Y }; }
    public Vec OrthX() { return new Vec { X = X }; }
    public Vec OrthY() { return new Vec { Y = Y }; }
}
struct Rect { public Vec TopLeft, Size; }

Vec NextVec(Random rng)
{ return new Vec { X = rng.Next(), Y = rng.Next() }; }

Rect NextRect(Random rng)
{
    var topLeft = NextVec(rng);
    return new Rect { TopLeft = NextVec(rng), Size = NextVec(rng) };
}

Vec Center;
double R, SqR;

private static double Square(double X) { return X*X; }
private bool Contains(Vec point)
{ return (Square(point.X - Center.X) + Square(point.Y - Center.Y)) < SqR; }

private bool Contains(Rect rect)
{
    var a = rect.TopLeft;
    var c = rect.TopLeft.Offset(rect.Size);
    if (c.Y < Center.Y) // in upper half
    {
        if (c.X < Center.X) // in upper-left quadrant
        {
            return Contains(a);
        }
        else if (a.X > Center.X) // in upper-right quadrant
        {
            return Contains(rect.TopLeft.Offset(rect.Size.OrthX()));
        }
        else // spans over upper half
        {
            return Contains(a) &&
                Contains(rect.TopLeft.Offset(rect.Size.OrthX()));
        }
    }
    else if (a.Y > Center.Y) // in lower half
    {
        if (c.X < Center.X) // in lower-left quadrant
        {
            return Contains(rect.TopLeft.Offset(rect.Size.OrthY()));
        }
        else if (a.X > Center.X) // in lower-right quadrant
        {
            return Contains(c);
        }
        else // spans over lower half
        {
            return Contains(c) &&
                Contains(rect.TopLeft.Offset(rect.Size.OrthY()));
        }
    }
    else // rect spans over upper and lower halfs
    {
        if (c.X < Center.X) // spans over left half
        {
            return Contains(a) &&
                Contains(rect.TopLeft.Offset(rect.Size.OrthY()));
        }
        else if (a.X > Center.X) // spans over right half
        {
            return Contains(rect.TopLeft.Offset(rect.Size.OrthX())) &&
                Contains(c);
        }
        else // rect spans over all quadrants
        {
            return Contains(a) &&
                Contains(c) &&
                Contains(rect.TopLeft.Offset(rect.Size.OrthX())) &&
                Contains(rect.TopLeft.Offset(rect.Size.OrthY()));
        }
    }

}

ところで：Quadtreeで長方形を作成することを検討してください

于 2012-11-28T10:13:21.210 に答える
-1

4 つのコーナー (x、y) が半径よりも球の中心に近いかどうかを確認すると、はるかに高速になりますか? 例

sqrt((Xcorner - Xcenter)^2 + (Ycorner - Ycenter)^2) <= R

条件を満たさない場合は、正方形の各コーナーの計算を中断します。

于 2012-11-28T09:07:17.213 に答える