Created
September 27, 2012 16:39
-
-
Save seburgi/3795015 to your computer and use it in GitHub Desktop.
Find missing rectangles
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Drawing; | |
using System.Linq; | |
namespace FillEmptySpaceWithRectangles | |
{ | |
internal class Program | |
{ | |
private static void Main(string[] args) | |
{ | |
// Defining the problem | |
var p = new Problem(300, 113, new[] | |
{ | |
new Rectangle(12, 26, 60, 30), | |
new Rectangle(12, 62, 60, 30), | |
new Rectangle(82, 27, 37, 30), | |
new Rectangle(82, 63, 37, 30), | |
new Rectangle(159, 11, 60, 30), | |
new Rectangle(194, 62, 24, 30), | |
new Rectangle(227, 12, 60, 30), | |
new Rectangle(227, 62, 60, 30), | |
}); | |
IEnumerable<Rectangle> result = Solve(p); | |
foreach (var rectangle in result) | |
{ | |
Console.WriteLine(rectangle); | |
} | |
} | |
private static IEnumerable<Rectangle> Solve(Problem problem) | |
{ | |
// Putting all edge coordinates in two sorted lists | |
// one for the x coordinates (left, right) | |
var interestingXs = new List<int> {0, problem.Width}; | |
interestingXs.AddRange(problem.Rectangles.Select(x => x.Left)); | |
interestingXs.AddRange(problem.Rectangles.Select(x => x.Right)); | |
interestingXs = interestingXs.Distinct().OrderBy(x => x).ToList(); | |
// one for the y coordinates (top, bottom) | |
var interestingYs = new List<int> {0, problem.Height}; | |
interestingYs.AddRange(problem.Rectangles.Select(x => x.Top)); | |
interestingYs.AddRange(problem.Rectangles.Select(x => x.Bottom)); | |
interestingYs = interestingYs.Distinct().OrderBy(x => x).ToList(); | |
// initialize solution with given rectangles | |
var solution = new List<Rectangle>(problem.Rectangles); | |
// this is the area of our blue rectangle | |
int targetArea = problem.Width * problem.Height; | |
// iterating over every possible combination of coordinates | |
for (int il = 0; il < interestingXs.Count; il++) | |
{ | |
for (int ir = interestingXs.Count - 1; ir > il; ir--) | |
{ | |
for (int it = 0; it < interestingYs.Count; it++) | |
{ | |
for (int ib = interestingYs.Count - 1; ib > it; ib--) | |
{ | |
int left = interestingXs[il]; | |
int top = interestingYs[it]; | |
int width = interestingXs[ir] - left; | |
int height = interestingYs[ib] - top; | |
var rect = new Rectangle(left, top, width, height); | |
// check if new rectangle intersects with any other of our rectangles | |
if (solution.Any(x => x.IntersectsWith(rect))) continue; | |
// add new rectangle to solution | |
solution.Add(rect); | |
// check if the sum of all rectangle areas equals the area of our problems blue (main) rectangle | |
// return result if it is equal | |
int sum = solution.Sum(x => x.Width*x.Height); | |
if (sum == targetArea) return solution; | |
} | |
} | |
} | |
} | |
throw new Exception("If you ever reach this point something went horribly wrong!"); | |
} | |
} | |
internal class Problem | |
{ | |
private readonly int _height; | |
private readonly Rectangle[] _rectangles; | |
private readonly int _width; | |
public Problem(int width, int height, Rectangle[] rectangles) | |
{ | |
_width = width; | |
_height = height; | |
_rectangles = rectangles; | |
} | |
public int Height | |
{ | |
get { return _height; } | |
} | |
public Rectangle[] Rectangles | |
{ | |
get { return _rectangles; } | |
} | |
public int Width | |
{ | |
get { return _width; } | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Quite naive solution for the following problem: http://inder-gnu.blogspot.co.at/2012/09/find-missing-rectangles.html