最佳算法：判断矩形是否在圆内

Question

我需要根据矩形与同心圆相交的情况来绘制不同填充颜色的矩形。下面的图片可以更好地说明这种情况（仅用于表示）。

目前，我正在通过应用勾股定理来检查每个点的状态。

伪代码如下：

点到中心的距离的平方(sqrOfDistance) = (点X坐标 - 圆心X坐标)的平方 + (点Y坐标 - 圆心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是枚举类型，用于确定点的状态。

- Riju

---

只是出于好奇，你介意告诉我这是干什么用的吗？ - Tharwen

首先，您可以通过检查矩形是否在正方形（(-r,-r)至(r,r)）内来进行优化，该正方形包围了圆形（半径为r，中心点为(0,0)）。 - Karthik T

@MatthewWatson 在代码中，我认为他是指正方形。 - Karthik T

不要微观优化交叉检查，考虑将正方形组织在一些空间划分结构中 - 四叉树、k-d树... - chill

@Tharwen 这是半导体晶片，矩形区域就是芯片。 - Riju

Answer 1

如果你需要处理许多矩形，并且大部分时间这些矩形都在圆外，那么一种优化方式是首先想象一个正方形包含圆，从(-r,-r)到(r,r)，其中r是圆的半径，圆心是(0,0)，并检查矩形是否在这个正方形内。这应该会更快，只有在此检查成功后才需要进行与圆的碰撞检查。

编辑：@hvd提出了一个很好的早期退出正检查的想法。如果矩形在内部正方形内，则它肯定在圆内。

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

- Karthik T

---

根据最常见的正方形，类似的逻辑也可以用于内部正方形（仅在四个点处接触内圆），如果您预先计算其边界，则也可能很有用。 - user743382

@hvd 我的矩形可能会变得非常小，因此假设并不总是有效。 - Riju

Answer 2

所以，在大多数情况下，我们可以决定将正方形视为圆形，这样我们的任务就会变得更容易。 它会看起来像这样

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
}

希望能有所帮助

- Dmitry Zheshinsky

---

这可能适用于较小的矩形，但对于较大的矩形则失败了。顺便说一下，我正在设计一个支持从1到3,000,000个矩形的控件。 - Riju

你说的不对。如果矩形很小，它更像圆形。真正的问题是大矩形，因为它的角落（不符合圆形的地方）面积更大。但在你的情况下，这不是问题。 - Dmitry Zheshinsky

Answer 3

只需评论@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()));
        }
    }

}

顺便提一下：考虑在四叉树中组织矩形

- ony

---

抱歉回复晚了，我被其他任务占用了。我会在周末查看您的建议。 - Riju

Answer 4

如果您检查4个角（x，y）是否更靠近球体的中心，则速度会更快，而不是半径的长度？ 例如

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

如果有任何一个角落不符合条件，就中断正方形每个角落的计算。

- Gustav Klimt

---

我想你应该仔细阅读问题描述。已经有解决方案，而且不需要使用那个缓慢的 sqrt 函数。 - ony

那么如果不是使用sqrt(a^2 + b^2)，你认为距离是如何计算的呢？很简单，就是基础的数学运算。对于他所进行的计算，即使他发现第一个角在外面，也不会中断计算，而是无论之前的计算结果如何，都会计算所有的角... - Gustav Klimt

你可以计算距离的平方。也就是说，你可以使用(dx^2 + dy^2) < R^2代替sqrt(dx^2 + dy^2) < R。请注意，R^2只需要计算一次即可。 - ony