Your articles have helped me immensely before and so I will gladly contribute back again!
I happen to have code for something similar to your teaser (NOTE: not entirely written by me but with a lot of help from a co-worker/friend a while back). I did some adjustments and it compiled fine, see the example fiddles here, the 1st one -
HoneyTheCodeWitchSample[
^] with no checking for existing rectangles, the second -
HoneyTheCodeWitch2[
^] for existing rectangles.
The first returned 18 tiles and the second 7 tiles -
First example -
using System;
using System.Collections.Generic;
public class Program
{
public static void Main(string[] args)
{
int screenWidth = 800;
int screenHeight = 480;
List<Rectangle> rectangles = new List<Rectangle>();
FillScreen(screenWidth, screenHeight, rectangles);
Console.WriteLine("Number of rectangles used: " + rectangles.Count);
foreach (Rectangle rectangle in rectangles)
{
Console.WriteLine("Rectangle: X=" + rectangle.X + ", Y=" + rectangle.Y + ", Width=" + rectangle.Width + ", Height=" + rectangle.Height);
}
}
static void FillScreen(int screenWidth, int screenHeight, List<Rectangle> rectangles)
{
int maxRectanglesX = screenWidth / 128;
int maxRectanglesY = screenHeight / 128;
for (int y = 0; y < maxRectanglesY; y++)
{
for (int x = 0; x < maxRectanglesX; x++)
{
int rectangleX = x * 128;
int rectangleY = y * 128;
Rectangle rectangle = new Rectangle(rectangleX, rectangleY, 128, 128);
bool overlaps = CheckOverlap(rectangle, rectangles);
if (!overlaps)
{
rectangles.Add(rectangle);
}
}
}
}
static bool CheckOverlap(Rectangle newRectangle, List<Rectangle> rectangles)
{
foreach (Rectangle existingRectangle in rectangles)
{
if (newRectangle.Intersects(existingRectangle))
{
return true;
}
}
return false;
}
}
public class Rectangle
{
public int X { get; set; }
public int Y { get; set; }
public int Width { get; set; }
public int Height { get; set; }
public Rectangle(int x, int y, int width, int height)
{
X = x;
Y = y;
Width = width;
Height = height;
}
public bool Intersects(Rectangle other)
{
return !(X + Width <= other.X || other.X + other.Width <= X || Y + Height <= other.Y || other.Y + other.Height <= Y);
}
}
with an output as -
Number of rectangles used: 18
Rectangle: X=0, Y=0, Width=128, Height=128
Rectangle: X=128, Y=0, Width=128, Height=128
Rectangle: X=256, Y=0, Width=128, Height=128
Rectangle: X=384, Y=0, Width=128, Height=128
Rectangle: X=512, Y=0, Width=128, Height=128
Rectangle: X=640, Y=0, Width=128, Height=128
Rectangle: X=0, Y=128, Width=128, Height=128
Rectangle: X=128, Y=128, Width=128, Height=128
Rectangle: X=256, Y=128, Width=128, Height=128
Rectangle: X=384, Y=128, Width=128, Height=128
Rectangle: X=512, Y=128, Width=128, Height=128
Rectangle: X=640, Y=128, Width=128, Height=128
Rectangle: X=0, Y=256, Width=128, Height=128
Rectangle: X=128, Y=256, Width=128, Height=128
Rectangle: X=256, Y=256, Width=128, Height=128
Rectangle: X=384, Y=256, Width=128, Height=128
Rectangle: X=512, Y=256, Width=128, Height=128
Rectangle: X=640, Y=256, Width=128, Height=128
The second example -
using System;
using System.Collections.Generic;
public class Program
{
public static void Main(string[] args)
{
int screenWidth = 800;
int screenHeight = 480;
List<Rectangle> existingRectangles = new List<Rectangle>
{
new Rectangle(100, 100, 200, 100),
new Rectangle(400, 200, 150, 150),
new Rectangle(600, 300, 100, 50)
};
List<Rectangle> filledRectangles = new List<Rectangle>();
FillScreen(screenWidth, screenHeight, existingRectangles, filledRectangles);
Console.WriteLine("Number of rectangles used: " + filledRectangles.Count);
foreach (Rectangle rectangle in filledRectangles)
{
Console.WriteLine("Rectangle: X=" + rectangle.X + ", Y=" + rectangle.Y + ", Width=" + rectangle.Width + ", Height=" + rectangle.Height);
}
}
static void FillScreen(int screenWidth, int screenHeight, List<Rectangle> existingRectangles, List<Rectangle> filledRectangles)
{
int maxRectanglesX = screenWidth / 128;
int maxRectanglesY = screenHeight / 128;
for (int y = 0; y < maxRectanglesY; y++)
{
for (int x = 0; x < maxRectanglesX; x++)
{
int rectangleX = x * 128;
int rectangleY = y * 128;
Rectangle newRectangle = new Rectangle(rectangleX, rectangleY, 128, 128);
bool overlaps = false;
foreach (Rectangle existingRectangle in existingRectangles)
{
if (newRectangle.Intersects(existingRectangle))
{
overlaps = true;
break;
}
}
if (!overlaps)
{
filledRectangles.Add(newRectangle);
}
}
}
}
}
public class Rectangle
{
public int X { get; set; }
public int Y { get; set; }
public int Width { get; set; }
public int Height { get; set; }
public Rectangle(int x, int y, int width, int height)
{
X = x;
Y = y;
Width = width;
Height = height;
}
public bool Intersects(Rectangle other)
{
return !(X + Width <= other.X || other.X + other.Width <= X || Y + Height <= other.Y || other.Y + other.Height <= Y);
}
}
And the output -
Number of rectangles used: 7
Rectangle: X=384, Y=0, Width=128, Height=128
Rectangle: X=512, Y=0, Width=128, Height=128
Rectangle: X=640, Y=0, Width=128, Height=128
Rectangle: X=640, Y=128, Width=128, Height=128
Rectangle: X=0, Y=256, Width=128, Height=128
Rectangle: X=128, Y=256, Width=128, Height=128
Rectangle: X=256, Y=256, Width=128, Height=128
I hope this will point you in the right direction, thanks for your previous help!
UPDATE
#include <iostream>
#include <vector>
struct Rectangle {
int X;
int Y;
int Width;
int Height;
Rectangle(int x, int y, int width, int height)
: X(x), Y(y), Width(width), Height(height)
{
}
bool Intersects(const Rectangle& other) const
{
return !(X + Width <= other.X || other.X + other.Width <= X || Y + Height <= other.Y || other.Y + other.Height <= Y);
}
};
void FillScreen(int screenWidth, int screenHeight, std::vector<Rectangle>& existingRectangles, std::vector<Rectangle>& filledRectangles)
{
std::vector<Rectangle> availableSpaces = { Rectangle(0, 0, screenWidth, screenHeight) };
for (const Rectangle& availableSpace : availableSpaces)
{
Rectangle bestFit;
bool foundFit = false;
for (const Rectangle& existingRectangle : existingRectangles)
{
if (existingRectangle.Intersects(availableSpace))
continue;
if (existingRectangle.Width <= availableSpace.Width && existingRectangle.Height <= availableSpace.Height)
{
bestFit = existingRectangle;
foundFit = true;
break;
}
}
if (foundFit)
{
filledRectangles.push_back(bestFit);
std::vector<Rectangle> newAvailableSpaces;
if (bestFit.Y - availableSpace.Y > 0)
{
Rectangle topSpace(availableSpace.X, availableSpace.Y, availableSpace.Width, bestFit.Y - availableSpace.Y);
newAvailableSpaces.push_back(topSpace);
}
if (availableSpace.Y + availableSpace.Height - bestFit.Y - bestFit.Height > 0)
{
Rectangle bottomSpace(availableSpace.X, bestFit.Y + bestFit.Height, availableSpace.Width, availableSpace.Y + availableSpace.Height - bestFit.Y - bestFit.Height);
newAvailableSpaces.push_back(bottomSpace);
}
if (bestFit.X - availableSpace.X > 0)
{
Rectangle leftSpace(availableSpace.X, bestFit.Y, bestFit.X - availableSpace.X, bestFit.Height);
newAvailableSpaces.push_back(leftSpace);
}
if (availableSpace.X + availableSpace.Width - bestFit.X - bestFit.Width > 0)
{
Rectangle rightSpace(bestFit.X + bestFit.Width, bestFit.Y, availableSpace.X + availableSpace.Width - bestFit.X - bestFit.Width, bestFit.Height);
newAvailableSpaces.push_back(rightSpace);
}
availableSpaces = newAvailableSpaces;
}
}
}
int main()
{
int screenWidth = 800;
int screenHeight = 480;
std::vector<Rectangle> existingRectangles = {
Rectangle(100, 100, 200, 100),
Rectangle(400, 200, 150, 150),
Rectangle(600, 300, 100, 50)
};
std::vector<Rectangle> filledRectangles;
FillScreen(screenWidth, screenHeight, existingRectangles, filledRectangles);
std::cout << "Number of rectangles used: " << filledRectangles.size() << std::endl;
for (const Rectangle& rectangle : filledRectangles)
{
std::cout << "Rectangle: X=" << rectangle.X << ", Y=" << rectangle.Y << ", Width=" << rectangle.Width << ", Height=" << rectangle.Height << std::endl;
}
return 0;
}