Instantly share code, notes, and snippets.

# KallDrexx/gist:11094250 Created Apr 19, 2014

What would you like to do?
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 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 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(); 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 SortCorners(IEnumerable corners) { return corners.Distinct() .OrderBy(x => x.X) .ThenBy(x => x.Y) .ToList(); } } }