4

我必须根据与同心圆的交点绘制具有不同填充颜色的矩形。显示的图片将使您对场景有更好的了解， 在此处输入图像描述 （仅代表目的）

目前我正在通过应用毕达哥拉斯定理检查每个点的状态

伪代码：

SquareOf Point 距中心的距离 (sqrOfDistance) = square(point X - Circle center X) + square(point Y- Circle center Y)

将这些值与半径平方 (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(x){ return x*x;} PointStatus 和 RectState 是用来确定点的状态的枚举。

4

4 回答 4

2

如果您正在处理很多矩形，并且大多数矩形大部分时间都在圆圈之外，那么以提前退出方式优化检查的一种方法是首先想象一个包围圆圈的正方形，从 (- r,-r) 到 (r,r)，其中 r 是圆的半径，圆的中心是 (0,0)，并检查矩形是否在这个正方形内。这应该要快得多，并且只有在成功的情况下才需要检查与圆的碰撞。

编辑：@hvd 为提前退出正面检查添加了一个绝妙的主意。如果矩形在内部正方形内，它肯定在圆内。

根据矩形与圆形的大小，您还可以更深一层并在内部正方形和圆形之间制作矩形。但是你需要检查查询到的矩形的点是否都在任何一个矩形（+内正方形）中，并且不需要都在同一个矩形中。

于 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

只需评论@Karthik T的建议即可。用矩形表示圆形，您可以使用以下方法检查它：

  • 忽略顶部边界高于圆顶部边界的矩形
  • 忽略底部边界低于圆形底部边界的矩形
  • 在圆的左边界之前忽略左边界的矩形
  • 在圆的右边界之后忽略右边界的矩形
  • 休息是里面的

因此，您只有 4 张支票而不是 8 张支票。

之后，您可以在象限中分割圆并将矩形分类为案例：

  • 如果右下角位于左上象限 - 仅检查左上角（按距离）
  • 如果左下角位于右上象限 - 仅检查右上角
  • 如果右上角在左下象限 - 仅检查左下角
  • 如果左上角在右下象限 - 仅检查右下角
  • 如果右下角和左下角在正方形的上半部分 - 仅检查左上角和右上角
  • ...
  • 休息（每个角落都在自己的象限中）按距离检查所有角落。

更新：实际上最好先对矩形进行分类，然后在正方形之外过滤掉，然后按案例过滤掉。

代码示例： 

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()));
        }
    }

}

顺便说一句：考虑在四叉树中组织矩形

于 2012-11-28T10:13:21.210 回答
-1

如果你检查4个角（x，y）是否更接近球心然后半径的长度会快得多？例子

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

如果有任何不符合条件，则打破正方形每个角的计算。

于 2012-11-28T09:07:17.213 回答