My Rectangle Subdivision Algorithm Skips Half of the Vertical Pixels

Question

I am working on making a rectangle subdivision algorithm for usage with a search tree. However, the rectangles seem to "skip" every one or two vertical pixels, leaving a lot of null space.

This is a visualization of the problem, the red lines don't cover everything as they should.

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

I have looked over my code, trying to find any off-by-one mistakes, but nothing is jumping out at me.

Answer 1

There are conditional off-by-one errors here:

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

If you have a rectangle of height h then two rectangles of height h / 2 do not necessarily add back up to a height of h, it could be h or h - 1 depending on whether h was even or odd. If h is odd then (h / 2) * 2 = h - 1 so it's off-by-one but only when h is odd.

You would need one rectangle of height h / 2 and other of height h - (h / 2) to get rid of that issue (there are variations on how to calculate the two heights but it doesn't really matter, the point is to do something such that the two new heights actually add up to h). All of this also applies to the width, of course.

If the original dimensions of the rectangle were powers of two, then you can get away with being less careful.