矩形细分算法漏绘半数纵向像素问题排查

我正在开发用于搜索树的矩形细分算法，但该算法生成的矩形会漏过每1-2个纵向像素，留下大量空白区域。可视化图中红线未完全覆盖应覆盖区域。

相关代码如下：

public void Insert(GameObject go, Vector2 location)
{
    SearchTreeNode node = Search(location);
    if(node != null)
    {
        node.gameObject = go;
    }
}

public SearchTreeNode Search(Vector2 location)
{
    foreach(SearchTreeNode node in root.children)
    {
        if (node.bounds.Contains(location.ToPoint()))
        {
            return SearchStep(location, node);
        }
    }
    return null;
}

public SearchTreeNode SearchStep(Vector2 location, SearchTreeNode node)
{
    foreach (SearchTreeNode n in node.children)
    {
        if (n.bounds.Contains(location.ToPoint()) && n.children.Count > 0)
        {
            return SearchStep(location, n);
        }
        else if(n.bounds.Contains(location.ToPoint()))
        {
            return n;
        }
    }
    return null;
}

public void HorizontalSplit(Rectangle rect, SearchTreeNode parent)
{
    for(int i = 0; i < rect.Width; i++)
    {
        SearchTreeNode newNode = new SearchTreeNode(parent, new List<SearchTreeNode>(), new Rectangle(rect.Left + i, rect.Top, 1, 1));
        parent.children.Add(newNode);
    }
}

public void VerticalSplit(Rectangle rect, SearchTreeNode parent)
{
    for (int i = 0; i < rect.Height; i++)
    {
        SearchTreeNode newNode = new SearchTreeNode(parent, new List<SearchTreeNode>(), new Rectangle(rect.Left, rect.Top + i, 1, 1));
        parent.children.Add(newNode);
    }
}

private Rectangle? Divide(Rectangle? rect, SearchTreeNode parent)
{
    if (rect == null) return null;
    Rectangle newRect = (Rectangle)rect;
    SearchTreeNode parentNode = new SearchTreeNode(parent, new List<SearchTreeNode>(), newRect);
    parent.children.Add(parentNode);
    if (newRect.Size.X == 1 || newRect.Size.Y == 1)
    {
        TestSpatial newTest = new TestSpatial(newRect);
        quadTree.Insert(newTest);
        if(newRect.Width > 1)
        {
            HorizontalSplit(newRect, parentNode);
        }
        if(newRect.Height > 1)
        {
            VerticalSplit(newRect, parentNode);
        }
        return rect;
    }

    Rectangle topLeft = new Rectangle(newRect.Left, newRect.Top, (newRect.Width / 2), newRect.Height / 2);
    Rectangle topRight = new Rectangle(newRect.Left + (newRect.Width / 2), newRect.Top, newRect.Width / 2, newRect.Height / 2);
    Rectangle bottomLeft = new Rectangle(newRect.Left, newRect.Top + (newRect.Height / 2), newRect.Width / 2, newRect.Height / 2);
    Rectangle bottomRight = new Rectangle(newRect.Left + (newRect.Width / 2), newRect.Top + (newRect.Height / 2), (newRect.Width / 2), (newRect.Height / 2));

    Divide(topLeft, parentNode);
    Divide(topRight, parentNode);
    Divide(bottomLeft, parentNode);
    Divide(bottomRight, parentNode);

    return null;
}

问题根源 #

核心问题出在Divide方法的四等分逻辑上：当矩形的宽或高为奇数时，使用整数除法newRect.Width / 2会丢失像素。比如宽度为5时，5/2=2，左右两部分各取2，总和只有4，漏掉了1个像素；纵向高度为奇数时同理，这直接导致边缘区域的像素未被覆盖，出现空白。

修正方案 #

调整四等分的宽度和高度计算，确保奇数尺寸的矩形能被完全分割，没有像素遗漏：

private Rectangle? Divide(Rectangle? rect, SearchTreeNode parent)
{
    if (rect == null) return null;
    Rectangle newRect = (Rectangle)rect;
    SearchTreeNode parentNode = new SearchTreeNode(parent, new List<SearchTreeNode>(), newRect);
    parent.children.Add(parentNode);
    if (newRect.Size.X == 1 || newRect.Size.Y == 1)
    {
        TestSpatial newTest = new TestSpatial(newRect);
        quadTree.Insert(newTest);
        if(newRect.Width > 1)
        {
            HorizontalSplit(newRect, parentNode);
        }
        if(newRect.Height > 1)
        {
            VerticalSplit(newRect, parentNode);
        }
        return rect;
    }

    // 处理奇数尺寸，确保分割后无像素遗漏
    int halfWidth = (newRect.Width + 1) / 2;
    int remainingWidth = newRect.Width - halfWidth;
    int halfHeight = (newRect.Height + 1) / 2;
    int remainingHeight = newRect.Height - halfHeight;

    Rectangle topLeft = new Rectangle(newRect.Left, newRect.Top, halfWidth, halfHeight);
    Rectangle topRight = new Rectangle(newRect.Left + halfWidth, newRect.Top, remainingWidth, halfHeight);
    Rectangle bottomLeft = new Rectangle(newRect.Left, newRect.Top + halfHeight, halfWidth, remainingHeight);
    Rectangle bottomRight = new Rectangle(newRect.Left + halfWidth, newRect.Top + halfHeight, remainingWidth, remainingHeight);

    Divide(topLeft, parentNode);
    Divide(topRight, parentNode);
    Divide(bottomLeft, parentNode);
    Divide(bottomRight, parentNode);

    return null;
}

补充说明 #

• 用(newRect.Width + 1) / 2计算左半部分宽度，确保奇数宽度时左半部分多占1像素，右半部分取剩余值，总和正好等于原宽度；高度同理。
• 原HorizontalSplit和VerticalSplit方法逻辑正确，循环从0到rect.Width/Height -1，能覆盖所有像素，无需修改。

内容的提问来源于stack exchange，提问作者slastine