c# - 确定矩形是否在圆内的最佳算法

Question

我必须根据与同心圆的交点绘制具有不同填充颜色的矩形。显示的图片将使您更好地了解场景， (仅代表目的)

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

伪代码:

SquareOf Point Distance from center (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 是确定点状态的枚举。

Answer 1

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

编辑:@hvd 添加了一个极好的想法，用于提前退出肯定检查。如果矩形在内部正方形内，则它肯定在圆内。

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