Skip to content

@KallDrexx /gist:11094250
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Daily Programmer 4/18/2014 challenge
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Scratchpad.DailyProgrammer
{
public class Dp20140418
{
public struct Point
{
public Point(decimal x, decimal y)
{
X = x;
Y = y;
}
public decimal X, Y;
public override string ToString()
{
return string.Format("Point: ({0},{1})", X, Y);
}
}
public struct Rectangle
{
public Rectangle(decimal x1, decimal y1, decimal x2, decimal y2)
{
X1 = x1;
Y1 = y1;
X2 = x2;
Y2 = y2;
}
public Rectangle(Point bottomLeftCorner, Point topRightCorner)
{
X1 = bottomLeftCorner.X;
Y1 = bottomLeftCorner.Y;
X2 = topRightCorner.X;
Y2 = topRightCorner.Y;
}
public decimal X1, Y1, X2, Y2;
public decimal Width { get { return Math.Abs(X2 - X1); } }
public decimal Height { get { return Math.Abs(Y2 - Y1); } }
public decimal Area { get { return Width * Height; } }
public Point[] Corners
{
get
{
return new Point[]
{
new Point(X1, Y1),
new Point(X1, Y2),
new Point(X2, Y1),
new Point(X2, Y2)
};
}
}
public override string ToString()
{
return string.Format("Rectangle: ({0}, {1}), ({2}, {3})", X1, Y1, X2, Y2);
}
public bool ContainsPoint(Point point)
{
return point.X >= X1 &&
point.X <= X2 &&
point.Y >= Y1 &&
point.Y <= Y2;
}
public bool ContainsRectangle(Rectangle rectangle)
{
return rectangle.Corners.All(ContainsPoint);
}
}
public static decimal ComputeArea(IEnumerable<Rectangle> rectangles)
{
var allRectangles = rectangles.ToList();
// Loop through each rectangle and if it intesects with any other rectangle, replace both of them
// with split rectangles
while (true)
{
bool intersectingRectanglesFound = false;
for (int x = 0; x < allRectangles.Count; x++)
{
for (int y = x + 1; y < allRectangles.Count; y++)
{
var rectangle1 = allRectangles[x];
var rectangle2 = allRectangles[y];
var splitRectangles = SplitIntersectingRectangles(rectangle1, rectangle2).ToArray();
if (splitRectangles.Length > 2)
{
// Rectangles intersected, remove both and add the split rectangles, and start again
allRectangles.RemoveAt(y);
allRectangles.RemoveAt(x);
allRectangles.AddRange(splitRectangles);
intersectingRectanglesFound = true;
break;
}
// If one rectangle is within the other, disregard the inner one
if (allRectangles[x].ContainsRectangle(allRectangles[y]))
{
allRectangles.RemoveAt(y);
y--;
}
else if (allRectangles[y].ContainsRectangle(allRectangles[x]))
{
allRectangles.RemoveAt(x);
x--;
break;
}
}
if (intersectingRectanglesFound)
break;
}
// If we found intersecting rectangles, begin the checks again
if (intersectingRectanglesFound)
continue;
break;
}
return allRectangles.Distinct().Sum(r => r.Area);
}
private static IEnumerable<Rectangle> SplitIntersectingRectangles(Rectangle rectangle1, Rectangle rectangle2)
{
var intersectingRectangle = GetIntersectingRectangle(rectangle1, rectangle2);
if (intersectingRectangle.Area == 0)
return new Rectangle[] {rectangle1, rectangle2}; // Rectangles don't intersect
// Get a list of all corners of all resulting rectangle
var initialRectangles = new[] {rectangle1, rectangle2, intersectingRectangle};
var corners = initialRectangles.SelectMany(x => x.Corners)
.ToList();
corners = SortCorners(corners);
// Cycle through all the points to pick out rectangles, starting from the 0,0
// Pick out the bottom left and top right corners to form rectangles on
var resultingRectangles = new List<Rectangle>();
for (int x = 0; x < corners.Count - 3; x++ )
{
var bottomLeftCorner = corners[x];
// FInd the next corner on the same X axis.
var topLeftCorner = corners[x + 1];
if (topLeftCorner.X != bottomLeftCorner.X)
continue;
// Find the next corner to the right
Point? topRightCorner = null;
for (int y = x + 2; y < corners.Count; y++)
{
// Ignore if we haven't moved beyond the current X plane
if (corners[y].X == bottomLeftCorner.X)
continue;
// Next corner we come up against will either be the top right corner,
// or an intersection point. If it's an intersection point we need to create
// a new corner from that point on the same Y axis as our last corner
if (corners[y].Y == topLeftCorner.Y)
{
topRightCorner = corners[y];
}
else
{
topRightCorner = new Point(corners[y].X, topLeftCorner.Y);
}
break;
}
if (topRightCorner == null)
continue;
// Add a new corner (if it doesn't exist) for the bottom right
var bottomRightCorner = new Point(topRightCorner.Value.X, bottomLeftCorner.Y);
// Note down the resulting rectangle
var splitRectangle = new Rectangle(bottomLeftCorner, topRightCorner.Value);
// Verify all 4 points are within the original rectangles
if (splitRectangle.Corners.Any(c => !rectangle1.ContainsPoint(c)) &&
splitRectangle.Corners.Any(c => !rectangle2.ContainsPoint(c)))
{
continue;
}
// Add the new corners and store the rectangle
corners.Add(topRightCorner.Value);
corners.Add(bottomRightCorner);
corners = SortCorners(corners);
resultingRectangles.Add(splitRectangle);
}
return resultingRectangles;
}
private static Rectangle GetIntersectingRectangle(Rectangle rectangle1, Rectangle rectangle2)
{
decimal resultX1 = 0, resultY1 = 0, resultX2 = 0, resultY2 = 0;
// Get the boundaries of the intersection rectangle
resultX1 = Math.Max(rectangle1.X1, rectangle2.X1);
resultY1 = Math.Max(rectangle1.Y1, rectangle2.Y1);
resultX2 = Math.Min(rectangle1.X2, rectangle2.X2);
resultY2 = Math.Min(rectangle1.Y2, rectangle2.Y2);
// If an invalid rectangle was created, the two rectangles don't intersect
if (resultX1 >= resultX2 || resultY1 >= resultY2)
return new Rectangle(0,0,0,0);
return new Rectangle(resultX1, resultY1, resultX2, resultY2);
}
private static List<Point> SortCorners(IEnumerable<Point> corners)
{
return corners.Distinct()
.OrderBy(x => x.X)
.ThenBy(x => x.Y)
.ToList();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.