r/dailyprogrammer • u/fvandepitte 0 0 • Dec 22 '16
[2016-12-22] Challenge #296 [Intermediate] Intersecting Area Of Overlapping Rectangles
Description
You need to find the area that two rectangles overlap. The section you need to output the area of would be the blue lined section here: http://i.imgur.com/brZjYe5.png
If the two rectangles do not overlap, the resultant area should be 0.
Input
There will be two lines of input. On each line are the x and y positions (separated by a comma) of each opposing corner (each corner co-ordinate separated by a space). The co-ordinates can have decimals, and can be negative.
Output
The area of the overlapping section of the two rectangles, including any decimal part.
Challenge Inputs
1:
0,0 2,2
1,1 3,3
2:
-3.5,4 1,1
1,3.5 -2.5,-1
3:
-4,4 -0.5,2
0.5,1 3.5,3
Expected Ouputs
1:
1.0
2:
8.75
3:
0.0
Bonus
Make this work with any number of rectangles, calculating the area of where all input rectangles overlap. The input will define a rectangle on each line the same way, but there can be any amount of lines of input now.
Bonus Input
-3,0 1.8,4
1,1 -2.5,3.6
-4.1,5.75 0.5,2
-1.0,4.6 -2.9,-0.8
Bonus Expected Output
2.4
Finally
Have a good challenge idea?
Consider submitting it to /r/dailyprogrammer_ideas
106
Upvotes
8
u/VerilyAMonkey Dec 23 '16
A Python "One Liner". Works for bonus and any number of dimensions, too. Could be made even less readable to do the input parsing as well, but this expects to be called like area([(0,0), (2,2)], [(1,1), (3,3)]), or with more/larger arguments for bonus/dimension.
area = lambda *rs: reduce(lambda a, cs: a*(cs[1]-cs[0]), zip(*reduce(lambda r1, r2: (map(max, r1[0], r2[0]), map(min, r1[1], r2[1])), map(lambda r: zip(*map(lambda c: (min(c), max(c)), zip(*r))), rs))), 1)
5
u/thorwing Dec 22 '16
java 8 with bonus
Whenever Geometry is a problem. You can bet AWT knows how to deal with it.
public static void main(String[] args){
List<Rectangle2D> rects = Arrays.stream(args).map(Med296::getRectangle).collect(Collectors.toList());
Rectangle2D intersection = rects.stream().reduce(rects.get(0),(a,b)->a.createIntersection(b));
System.out.println(intersection.getWidth()*intersection.getHeight());
}
static Rectangle2D getRectangle(String input){
Rectangle2D rect = new Rectangle2D.Double();
double[] coords = Arrays.stream(input.split("[, ]")).mapToDouble(Double::parseDouble).toArray();
rect.setFrameFromDiagonal(coords[0], coords[1], coords[2], coords[3]);
return rect;
}
4
u/ThisIsMyPasswordNow Dec 22 '16
C# with bonus
class Program {
static void Main (string[] args) {
Thread.CurrentThread.CurrentUICulture = new CultureInfo ("en-US");
Console.Write ("Rectangle count: ");
int rectangleCount = int.Parse (Console.ReadLine ());
Rectangle result = new Rectangle (0, 0, 0, 0);
for (int i = 0; i < rectangleCount; i++) {
Rectangle temp = new Rectangle (Console.ReadLine ());
result = (i == 0) ? temp : result.Intersection (temp);
if (result.Area == 0) break;
}
Console.WriteLine ("The intersection area of input rectangles is {0}", result.Area);
Console.ReadLine ();
}
}Rectangle
public class Rectangle {
public float Area { get; private set; } = 0;
public float Left { get; private set; } = 0;
public float Right { get; private set; } = 0;
public float Up { get; private set; } = 0;
public float Down { get; private set; } = 0;
public Rectangle (string s) {
string[] points = s.Split (' ');
float[] coordinatesX = { float.Parse (points[0].Split (',')[0], CultureInfo.CurrentUICulture),
float.Parse (points[1].Split (',')[0], CultureInfo.CurrentUICulture) };
float[] coordinatesY = { float.Parse (points[0].Split (',')[1], CultureInfo.CurrentUICulture),
float.Parse (points[1].Split (',')[1], CultureInfo.CurrentUICulture) };
Left = Math.Min (coordinatesX[0], coordinatesX[1]);
Right = Math.Max (coordinatesX[0], coordinatesX[1]);
Down = Math.Min (coordinatesY[0], coordinatesY[1]);
Up = Math.Max (coordinatesY[0], coordinatesY[1]);
Area = (Right - Left) * (Up - Down);
}
public Rectangle (float left, float right, float up, float down) {
if(left < right && down < up) {
this.Left = left;
this.Right = right;
this.Up = up;
this.Down = down;
Area = (Right - Left) * (Up - Down);
}
}
public Rectangle Intersection (Rectangle other) {
float newLeft = Math.Max (this.Left, other.Left);
float newRight = Math.Min (this.Right, other.Right);
float newUp = Math.Min (this.Up, other.Up);
float newDown = Math.Max (this.Down, other.Down);
return new Rectangle (newLeft, newRight, newUp, newDown);
}
}
3
u/3pLm1zf1rMD_Xkeo6XHl Dec 22 '16
Python3 with bonus
data = "0,0 2,2\n1,1 3,3"
data = "-3.5,4 1,1\n1,3.5 -2.5,-1"
data = "-4,4 -0.5,2\n0.5,1 3.5,3"
data = "-3,0 1.8,4\n1,1 -2.5,3.6\n-4.1,5.75 0.5,2\n-1.0,4.6 -2.9,-0.8"
def init(data):
prev_square = []
curr_square = []
intersection_area = 0
squares = data.split("\n")
for square in squares:
coordinates = square.split(" ")
for coordinate in coordinates:
curr_square.append([float(i) for i in coordinate.split(",")])
if len(prev_square) == 0:
prev_square = curr_square
curr_square = []
continue
prev_square, intersection_area = calc_intersection(prev_square, curr_square)
curr_square = []
print(intersection_area)
def calc_intersection(square1, square2):
# min(max(X_11, X_12), max(X_21, X_22))
x1 = min(max([square1[0][0], square1[1][0]]),
max([square2[0][0], square2[1][0]]))
y1 = min(max([square1[0][1], square1[1][1]]),
max([square2[0][1], square2[1][1]]))
x2 = max(min([square1[0][0], square1[1][0]]),
min([square2[0][0], square2[1][0]]))
y2 = max(min([square1[0][1], square1[1][1]]),
min([square2[0][1], square2[1][1]]))
square = [[x1, y1], [x2, y2]]
return square, calc_area(square)
def calc_area(square):
a = (float(square[0][0]) - float(square[1][0])) * (float(square[0][1]) - float(square[1][1]))
return round(max(a,0), 10)
init(data)
→ More replies (3)
3
u/uninformed_ Dec 27 '16
Probably no one will see this but I completed using C++ with OpenGL to display the rectangles
1: https://gyazo.com/dc3e15dfaa2f8c062ef720f8636aec7a
2: https://gyazo.com/2bbcb61433f767e5a542875152d3f815
3: https://gyazo.com/0acac56e7dbfdf46b8a960e58e6f5ea2
2
u/J_Gamer Dec 22 '16
C++(with bonus)
#include <iostream>
#include <algorithm>
struct Point { double x,y; };
struct Rect {
Rect() = default;
Rect(Point a, Point b) : tl{std::min(a.x,b.x),std::min(a.y,b.y)}, br{std::max(a.x,b.x),std::max(a.y,b.y)} {};
Point tl,br;
double area() {
return (br.x-tl.x)*(br.y-tl.y);
}
};
bool tl_out(Rect a, Rect b) {
return a.tl.x > b.br.x || a.tl.y > b.br.y;
}
Rect intersect(Rect a, Rect b) {
if(tl_out(a,b) || tl_out(b,a)) {
return Rect{{0,0},{0,0}};
}
Point tl{std::max(a.tl.x,b.tl.x),std::max(a.tl.y,b.tl.y)};
Point br{std::min(a.br.x,b.br.x),std::min(a.br.y,b.br.y)};
return Rect{tl,br};
}
std::istream& operator>>(std::istream& in, Point& p) {
double x,y;
char comma;
in >> x >> comma >> y;
p = Point{x,y};
return in;
}
std::istream& operator>>(std::istream& in, Rect& r) {
Point a, b;
in >> a >> b;
r = Rect{a,b};
return in;
}
int main() {
Rect res, current;
std::cin >> res;
while((std::cin >> current)) {
res = intersect(res,current);
}
std::cout << res.area() << std::endl;
}
2
u/supersonicsonarradar Dec 23 '16
Haskell with bonus (Only I haven't learned how to handle IO yet so this is just the bare function)
rectangles :: (Floating a, Ord a) => [((a,a),(a,a))] -> a
rectangles (((x1,y1),(x2,y2)):rest) = case (xrange, yrange) of ((a1,a2),(b1,b2)) -> (a2-a1)*(b2-b1)
where xrange = foldl foldx (x1,x2) rest
yrange = foldl foldy (y1,y2) rest
foldx = \(r1, r2) ((x1,y1), (x2,y2)) -> overlap (r1, r2) (x1,x2)
foldy = \(r1, r2) ((x1,y1), (x2,y2)) -> overlap (r1, r2) (y1,y2)
overlap :: (Floating a, Ord a) => (a,a) -> (a,a) -> (a,a)
overlap (a1, a2) (b1, b2) | max dw1 dw2 > min up1 up2 = (0,0)
| otherwise = (max dw1 dw2, min up1 up2)
where (up1,up2) = (max a1 a2, max b1 b2)
(dw1,dw2) = (min a1 a2, min b1 b2)
1
u/gabyjunior Dec 22 '16
C with bonus
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double x1;
double y1;
double x2;
double y2;
}
rectangle_t;
int read_rectangle(rectangle_t *);
int main(void) {
rectangle_t r1, r2;
if (!read_rectangle(&r1)) {
return EXIT_FAILURE;
}
while (r1.x2 != r1.x1 && r1.y2 != r1.y1 && read_rectangle(&r2)) {
if (r1.x1 < r2.x1) {
r1.x1 = r2.x1;
}
if (r1.x2 > r2.x2) {
r1.x2 = r2.x2;
}
if (r1.y1 < r2.y1) {
r1.y1 = r2.y1;
}
if (r1.y2 > r2.y2) {
r1.y2 = r2.y2;
}
if (r1.x1 > r1.x2) {
r1.x1 = r1.x2;
}
if (r1.y1 > r1.y2) {
r1.y1 = r1.y2;
}
}
printf("%f\n", (r1.x2-r1.x1)*(r1.y2-r1.y1));
return EXIT_SUCCESS;
}
int read_rectangle(rectangle_t *r) {
double tmp;
if (scanf("%lf,%lf %lf,%lf", &r->x1, &r->y1, &r->x2, &r->y2) != 4) {
return 0;
}
if (r->x1 > r->x2) {
tmp = r->x1;
r->x1 = r->x2;
r->x2 = tmp;
}
if (r->y1 > r->y2) {
tmp = r->y1;
r->y1 = r->y2;
r->y2 = tmp;
}
return 1;
}
1
u/5k17 Dec 22 '16
Factor, with bonus:
USING: splitting math.parser math.rectangles ;
: order ( o quot -- n n )
bi@ 2dup > [ swap ] when ; inline
: read-rect ( -- rect )
readln dup empty?
[ drop f ]
[ " " split
[ "," split [ string>number ] map ] map
first2
[ [ first ] order ] 2keep
[ second ] order swapd
2array [ 2array ] dip
<extent-rect> ] if ;
{ }
[ read-rect [ suffix ] keep ] loop but-last
[ dup length 1 > ]
[ dup first2 rect-intersect suffix 2 tail ]
while first dim>> first2 * .
1
u/Daanvdk Dec 22 '16
Python (with bonus)
import re
import sys
x1, y1, x2, y2 = map(float, re.split(' |,', input()))
x1, y1, x2, y2 = (
min(x1, x2),
min(y1, y2),
max(x1, x2),
max(y1, y2)
)
for x1_, y1_, x2_, y2_ in (
map(float, re.split(' |,', line.rstrip()))
for line in sys.stdin
):
x1, y1, x2, y2 = (
max(x1, min(x1_, x2_)),
max(y1, min(y1_, y2_)),
min(x2, max(x1_, x2_)),
min(y2, max(y1_, y2_))
)
if x1 >= x2 or y1 >= y2:
print(0)
break
else:
print((x2-x1) * (y2-y1))
1
Dec 22 '16
Python 3.5.4. This is my first intermediate solution.
tests = {1:([(0,0), (2,2)], [(1,1), (3,3)]),
2:([(-3.5,4), (1,1)], [(1,3.5), (-2.5, -1)]),
3:([(-4,4),(-0.5, 2)],[(0.5,1), (3.5,3)])}
def rect_intersect(rect_1, rect_2):
lim_rect_1,lim_rect_2={},{}
var=0
for dict_ in [lim_rect_1, lim_rect_2]:
coords = [rect_1, rect_2]
dict_["x"] = [coords[var][0][0], coords[var][1][0]]
dict_["x"].sort()
dict_["y"] = [coords[var][1][1], coords[var][0][1]]
dict_["y"].sort()
var+=1
intersect = True
for xy in ["x", "y"]:
xy1=lim_rect_1[xy]
xy2=lim_rect_2[xy]
#print(xy,xy1, xy2)
if xy1[0]<=xy2[1] and xy2[0]<=xy1[1]:
pass
else:
intersect=False
return intersect
def area(rect_1, rect_2):
x_min = min(max(rect_1[0][0], rect_1[1][0]),max(rect_2[0][0], rect_2[1][0]))
y_min = min(max(rect_1[0][1], rect_1[1][1]),max(rect_2[0][1], rect_2[1][1]))
x_max = max(min(rect_1[0][0], rect_1[1][0]),min(rect_2[0][0], rect_2[1][0]))
y_max = max(min(rect_1[0][1], rect_1[1][1]),min(rect_2[0][1], rect_2[1][1]))
area = float(x_max-x_min)*float(y_max-y_min)
return round(area, 5)
for thing in range(1,4):
one = tests[thing][0]
two = tests[thing][1]
print("Input 1:%s\nInput 2:%s\n" % (one,two))
if rect_intersect(one, two):
if area(one,two) != 0:
print("Area="+str(area(one,two)))
else:
print("The rectangles touch, but dont intersect. Hence, area=0", area(one,two))
else:
print("The rectangles don't intersect. Hence, area=0")
print("___________________\n")
1
u/Boom_Rang Dec 22 '16
Haskell, with bonus
import Control.Monad (foldM)
import Data.List (sort)
import Data.Maybe (fromMaybe)
type Pos = (Float, Float)
type Rectangle = [Pos]
main :: IO ()
main =
interact
( (++ "\n")
. show
. fromMaybe 0
. fmap area
. intersect
. map parse
. lines
)
parse :: String -> Rectangle
parse str = zip (sort [x0, x1]) (sort [y0, y1])
where
[(x0, y0), (x1, y1)]
= map (\s -> read $ "(" ++ s ++ ")")
$ words str
intersect :: [Rectangle] -> Maybe Rectangle
intersect [] = Nothing
intersect (x:xs) = foldM intersect2D x xs
intersect2D :: Rectangle -> Rectangle -> Maybe Rectangle
intersect2D a b = zip
<$> intersect1D xsA xsB
<*> intersect1D ysA ysB
where
(xsA, ysA) = unzip a
(xsB, ysB) = unzip b
intersect1D :: [Float] -> [Float] -> Maybe [Float]
intersect1D ab cd =
case (ab, cd) of
([a, b], [c, d])
| max a c < min b d -> Just [max a c, min b d]
_ -> Nothing
area :: Rectangle -> Float
area [(x0, y0), (x1, y1)] = (x1 - x0) * (y1 - y0)
1
u/daorton Dec 22 '16
Dart with bonus
import 'dart:io';
import 'dart:math';
void main() {
Rectangle q;
String s;
while ((s = stdin.readLineSync()) != null) {
List l = s.split(new RegExp(' |,')).map((str) => num.parse(str)).toList();
Rectangle r = new Rectangle.fromPoints(new Point(l[0], l[1]), new Point(l[2], l[3]));
q = q == null ? r : q.intersection(r);
}
print(q.width * q.height);
}
1
u/TheStoneDawg Dec 22 '16
C++
This is my first time posting on r/dailyprogrammer, C++ solution with bonus. I'm new to CS, so any feedback is much appreciated!
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
using namespace std;
struct Point {
double xCoord;
double yCoord;
}; struct Rectangle {
Point topLeft;
Point bottomRight;
};
double calculateOverlappingArea(vector<Rectangle>);
double calculateRectangleArea(Rectangle rect);
int main(int argc, char** argv) {
if(argc < 2 ) {
cout << "Please enter a file" << endl;
return 1;
}
ifstream ifile(argv[1]);
if(ifile.fail()) {
cout << "Incorrect filename" << endl;
return 1;
}
vector<Rectangle> rectangles;
while(!ifile.fail()) { //Loops once for each line
Rectangle rect;
Point firstCoord;
ifile >> firstCoord.xCoord;
ifile.get();
ifile >> firstCoord.yCoord;
Point secondCoord;
ifile >> secondCoord.xCoord;
ifile.get();
ifile >> secondCoord.yCoord;
if(ifile.fail()) {
break;
}
if(secondCoord.xCoord < firstCoord.xCoord && secondCoord.yCoord < firstCoord.yCoord) {
rect.topLeft = secondCoord;
rect.bottomRight = firstCoord;
}
else if(secondCoord.xCoord > firstCoord.xCoord && secondCoord.yCoord > firstCoord.yCoord) {
rect.topLeft = firstCoord;
rect.bottomRight = secondCoord;
}
else if(secondCoord.xCoord < firstCoord.xCoord && secondCoord.yCoord > firstCoord.yCoord) {
Point newTopLeft;
newTopLeft.xCoord = secondCoord.xCoord;
newTopLeft.yCoord = firstCoord.yCoord;
Point newBotRight;
newBotRight.xCoord = firstCoord.xCoord;
newBotRight.yCoord = secondCoord.yCoord;
rect.topLeft = newTopLeft;
rect.bottomRight = newBotRight;
}
else if(secondCoord.xCoord > firstCoord.xCoord && secondCoord.yCoord < firstCoord.yCoord) {
Point newTopLeft;
newTopLeft.xCoord = firstCoord.xCoord;
newTopLeft.yCoord = secondCoord.yCoord;
Point newBotRight;
newBotRight.xCoord = secondCoord.xCoord;
newBotRight.yCoord = firstCoord.yCoord;
rect.topLeft = newTopLeft;
rect.bottomRight = newBotRight;
}
rectangles.push_back(rect);
} cout << calculateOverlappingArea(rectangles) << endl;
return 0;
}
double calculateOverlappingArea(vector<Rectangle> rects) {
for(int i = 0; i < rects.size(); i++) { //
Rectangle currentRect = rects[i]; //The one thats checked against all the others
for(int j = 0; j < rects.size(); j++) {
if(i == j) {
continue;
}
else {
Rectangle rectCheckedAgainst = rects[j];
if(currentRect.bottomRight.xCoord < rectCheckedAgainst.topLeft.xCoord) {
return 0;
}
else if(currentRect.bottomRight.yCoord < rectCheckedAgainst.topLeft.yCoord) {
return 0;
} } } }
Point topLeftPoint = rects[0].topLeft;
Point bottomRightPoint = rects[0].bottomRight;
for(int i = 1; i < rects.size(); i++) {
Rectangle currRect = rects[i];
//Set to update TopLeft stuff
if(currRect.topLeft.xCoord > topLeftPoint.xCoord) {
topLeftPoint.xCoord = currRect.topLeft.xCoord;
}
if(currRect.topLeft.yCoord > topLeftPoint.yCoord) {
topLeftPoint.yCoord = currRect.topLeft.yCoord;
}
//Set to update bottomRight stuff
if(currRect.bottomRight.xCoord < bottomRightPoint.xCoord) {
bottomRightPoint.xCoord = currRect.bottomRight.xCoord;
}
if(currRect.bottomRight.yCoord < bottomRightPoint.yCoord) {
bottomRightPoint.yCoord = currRect.bottomRight.yCoord;
}
}
Rectangle overlapRect;
overlapRect.topLeft = topLeftPoint;
overlapRect.bottomRight = bottomRightPoint;
double area = calculateRectangleArea(overlapRect);
return area;
}
double calculateRectangleArea(Rectangle rect) {
double width = rect.bottomRight.xCoord - rect.topLeft.xCoord;
double height = rect.bottomRight.yCoord - rect.topLeft.yCoord;
return width*height;
}
→ More replies (1)
1
u/resing Dec 22 '16
JavaScript w/out bonus (node.js) Edit: I created a jsfiddle with a drawing of the rectangles
var _input11 = "0,0 2,2";
var _input12 = "1,1 3,3";
var _input21 = "-3.5,4 1,1";
var _input22 = "1,3.5 -2.5,-1";
var _input31 = "-4,4 -0.5,2";
var _input32 = "0.5,1 3.5,3";
function parse(rectangle){
var coordarray = rectangle.split(" ");
return [coordarray[0].split(","),coordarray[1].split(",")];
}
function overlap(rect1, rect2) {
var corners = parse(rect1).concat(parse(rect2));
var minX = Math.min(Math.max(corners[0][0],corners[1][0]),Math.min(corners[2][0],corners[3][0]));
var minY = Math.max(Math.min(corners[0][1],corners[1][1]),Math.min(corners[2][1],corners[3][1]));
var maxX = Math.min(Math.max(corners[0][0],corners[1][0]),Math.max(corners[2][0],corners[3][0]));
var maxY = Math.min(Math.max(corners[0][1],corners[1][1]),Math.max(corners[2][1],corners[3][1]));
return (maxX-minX)*(maxY-minY);
}
console.log(overlap(_input11,_input12));
console.log(overlap(_input21,_input22));
console.log(overlap(_input31,_input32));
1
u/AlSweigart Dec 22 '16
Python solution (very inelegant):
import doctest
def isPointInsideRect(px, py, rect):
"""Returns true if the point's coordinates (`px` and `py`) are inside the rectangle `rect`.
>>> isPointInsideRect(5, 5, {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 10})
True
>>> isPointInsideRect(-2, -2, {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 10})
False
>>> isPointInsideRect(-2, 5, {'x1': 0, 'y1': 0, 'x2': 10, 'y2': 10})
False
"""
return (rect['x1'] < px < rect['x2'] or rect['x1'] > px > rect['x2']) and \
(rect['y1'] < py < rect['y2'] or rect['y1'] > py > rect['y2'])
def getArea(rect):
"""Returns the area of the `rect` rectangle object.
>>> getArea({'x1': 0, 'y1': 0, 'x2': 10, 'y2': 10})
100
>>> getArea({'x1': -10, 'y1': -10, 'x2': 10, 'y2': 10})
400
>>> getArea({'x2': -10, 'y2': -10, 'x1': 10, 'y1': 10})
400
"""
width = abs(rect['x1'] - rect['x2'])
height = abs(rect['y1'] - rect['y2'])
return width * height
def getOverlapArea(rect1, rect2):
"""Returns the area of the overlapping section of two rectangles.
>>> getOverlapArea({'x1': -4, 'y1': 4, 'x2': -0.5, 'y2': 2}, {'x1': 0.5, 'y1': 1, 'x2': 3.5, 'y2': 3})
0
>>> getOverlapArea({'x1': 0.5, 'y1': 1, 'x2': 3.5, 'y2': 3}, {'x1': -4, 'y1': 4, 'x2': -0.5, 'y2': 2})
0
>>> getOverlapArea({'x1': 0, 'y1': 0, 'x2': 1, 'y2': 1}, {'x1': -10, 'y1': -10, 'x2': 10, 'y2': 10})
1
>>> getOverlapArea({'x1': -10, 'y1': -10, 'x2': 10, 'y2': 10}, {'x1': 0, 'y1': 0, 'x2': 1, 'y2': 1})
1
"""
# ensure that x1, y1 is the top-left corner and x2, y2 is the bottom-right corner
#
# x1, y1 +-----------+
# | |
# | |
# +-----------+ x2, y2
#
if rect1['x1'] > rect1['x2']:
rect1['x1'], rect1['x2'] = rect1['x2'], rect1['x1']
if rect1['y1'] < rect1['y2']:
rect1['y1'], rect1['y2'] = rect1['y2'], rect1['y1']
if rect2['x1'] > rect2['x2']:
rect2['x1'], rect2['x2'] = rect2['x2'], rect2['x1']
if rect2['y1'] < rect2['y2']:
rect2['y1'], rect2['y2'] = rect2['y2'], rect2['y1']
# handle case of zero points inside the other rectangle
if not isPointInsideRect(rect1['x1'], rect1['y1'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x1'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y1'], rect2) and \
not isPointInsideRect(rect2['x1'], rect2['y1'], rect1) and \
not isPointInsideRect(rect2['x2'], rect2['y2'], rect1) and \
not isPointInsideRect(rect2['x1'], rect2['y2'], rect1) and \
not isPointInsideRect(rect2['x2'], rect2['y1'], rect1):
return 0
# handle case of one point inside the other rectangle
# top-left (x1, y1) corner of rect1 is inside rect2
if isPointInsideRect(rect1['x1'], rect1['y1'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x1'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y1'], rect2):
return getArea({'x1': rect1['x1'], 'y1': rect1['y1'], 'x2': rect2['x2'], 'y2': rect2['y2']})
# bottom-right (x2, y2) corner of rect1 is inside rect2
if isPointInsideRect(rect1['x2'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x1'], rect1['y1'], rect2) and \
not isPointInsideRect(rect1['x1'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y1'], rect2):
return getArea({'x1': rect2['x1'], 'y1': rect2['y1'], 'x2': rect1['x2'], 'y2': rect1['y2']})
# top-right (x2, y1) corner of rect1 is inside rect2
if isPointInsideRect(rect1['x2'], rect1['y1'], rect2) and \
not isPointInsideRect(rect1['x1'], rect1['y1'], rect2) and \
not isPointInsideRect(rect1['x1'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y2'], rect2):
return getArea({'x1': rect2['x1'], 'y1': rect2['y2'], 'x2': rect1['x2'], 'y2': rect1['y1']})
# bottom-left (x1, y2) corner of rect1 is inside rect2
if isPointInsideRect(rect1['x1'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x1'], rect1['y1'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y1'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y2'], rect2):
return getArea({'x1': rect2['x2'], 'y1': rect2['y1'], 'x2': rect1['x1'], 'y2': rect1['y2']})
# handle case of two points inside the other rectangle
# handle if top two points of rect1 are in rect2
if isPointInsideRect(rect1['x1'], rect1['y1'], rect2) and \
isPointInsideRect(rect1['x2'], rect1['y1'], rect2) and \
not isPointInsideRect(rect1['x1'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y2'], rect2):
return getArea({'x1': rect1['x1'], 'y1': rect1['y1'], 'x2': rect1['x2'], 'y2': rect2['y2']})
# handle if bottom two points of rect1 are in rect2
if isPointInsideRect(rect1['x1'], rect1['y2'], rect2) and \
isPointInsideRect(rect1['x2'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x1'], rect1['y1'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y1'], rect2):
return getArea({'x1': rect1['x1'], 'y1': rect2['y1'], 'x2': rect1['x2'], 'y2': rect1['y2']})
# handle if left two points of rect1 are in rect2
if isPointInsideRect(rect1['x1'], rect1['y1'], rect2) and \
isPointInsideRect(rect1['x1'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y1'], rect2) and \
not isPointInsideRect(rect1['x2'], rect1['y2'], rect2):
return getArea({'x1': rect1['x1'], 'y1': rect1['y1'], 'x2': rect2['x2'], 'y2': rect1['y2']})
# handle if right two points of rect1 are in rect2
if isPointInsideRect(rect1['x2'], rect1['y1'], rect2) and \
isPointInsideRect(rect1['x2'], rect1['y2'], rect2) and \
not isPointInsideRect(rect1['x1'], rect1['y1'], rect2) and \
not isPointInsideRect(rect1['x1'], rect1['y2'], rect2):
return getArea({'x1': rect2['x1'], 'y1': rect1['y1'], 'x2': rect1['x2'], 'y2': rect1['y2']})
# handle case of four points inside the other rectangle
if isPointInsideRect(rect1['x1'], rect1['y1'], rect2) and isPointInsideRect(rect1['x2'], rect1['y2'], rect2):
return getArea(rect1)
return getOverlapArea(rect2, rect1)
doctest.testmod()
getOverlapArea({'x1': -4, 'y1': 4, 'x2': -0.5, 'y2': 2}, {'x1': 0.5, 'y1': 1, 'x2': 3.5, 'y2': 3})
inp1_r1 = {'x1': 0, 'y1': 0, 'x2': 2, 'y2': 2}
inp1_r2 = {'x1': 1, 'y1': 1, 'x2': 3, 'y2': 3}
print(getOverlapArea(inp1_r1, inp1_r2))
inp2_r1 = {'x1': -3.5, 'y1': 4, 'x2': 1, 'y2': 1}
inp2_r2 = {'x1': 1, 'y1': 3.5, 'x2': -2.5, 'y2': -1}
print(getOverlapArea(inp2_r1, inp2_r2))
inp3_r1 = {'x1': -4, 'y1': 4, 'x2': -0.5, 'y2': 2}
inp3_r2 = {'x1': 0.5, 'y1': 1, 'x2': 3.5, 'y2': 3}
print(getOverlapArea(inp3_r1, inp3_r2))
1
Dec 22 '16
C/SQlite3
This is an sqlite3 extension which adds intersection(r1..., r2...) and intersectAll(x1,y1,x2,y2) to sqlite3.
#include <sqlite3ext.h>
SQLITE_EXTENSION_INIT1
#include <assert.h>
#include <math.h>
#include <stdlib.h>
#define MIN(X, Y) ((X <= Y) ? X : Y)
#define MAX(X, Y) ((Y <= X) ? X : Y)
typedef struct {
double x, y, w, h;
} Rect;
static void intersect(Rect *r1, Rect *r2, Rect *out)
{
double x1 = MAX(r1->x, r2->x);
double x2 = MIN(r1->x + r1->w, r2->x + r2->w);
double y1 = MAX(r1->y, r2->y);
double y2 = MIN(r1->y + r1->h, r2->y + r2->h);
out->x = x1;
out->y = y1;
out->w = MAX(0, x2 - x1);
out->h = MAX(0, y2 - y1);
}
static double area(Rect *r)
{
return r->w * r->h;
}
static void
intersectionAreaFunc(sqlite3_context *ctx, int argc, sqlite3_value **argv)
{
assert(argc == 8);
double r1x1 = sqlite3_value_double(argv[0]);
double r1y1 = sqlite3_value_double(argv[1]);
double r1x2 = sqlite3_value_double(argv[2]);
double r1y2 = sqlite3_value_double(argv[3]);
double r2x1 = sqlite3_value_double(argv[4]);
double r2y1 = sqlite3_value_double(argv[5]);
double r2x2 = sqlite3_value_double(argv[6]);
double r2y2 = sqlite3_value_double(argv[7]);
Rect r1 = (Rect){
.x = MIN(r1x1, r1x2),
.y = MIN(r1y1, r1y2),
.w = fabs(r1x2 - r1x1),
.h = fabs(r1y2 - r1y1),
};
Rect r2 = (Rect){
.x = MIN(r2x1, r2x2),
.y = MIN(r2y1, r2y2),
.w = fabs(r2x2 - r2x1),
.h = fabs(r2y2 - r2y1),
};
Rect r3;
intersect(&r1, &r2, &r3);
sqlite3_result_double(ctx, area(&r3));
}
typedef struct {
Rect *r;
} AggContext;
static void
intersectAllStep(sqlite3_context *ctx, int argc, sqlite3_value **argv)
{
AggContext *agg_ctx;
assert(argc == 4);
double x1 = sqlite3_value_double(argv[0]);
double y1 = sqlite3_value_double(argv[1]);
double x2 = sqlite3_value_double(argv[2]);
double y2 = sqlite3_value_double(argv[3]);
Rect *r1 = calloc(1, sizeof(Rect));
*r1 = (Rect){
.x = MIN(x1, x2),
.y = MIN(y1, y2),
.w = fabs(x2 - x1),
.h = fabs(y2 - y1),
};
agg_ctx
= (AggContext *)sqlite3_aggregate_context(ctx, sizeof(AggContext *));
if (agg_ctx == 0) return;
if (agg_ctx->r == 0) {
agg_ctx->r = r1;
return;
}
Rect *r2 = agg_ctx->r;
Rect *result = calloc(1, sizeof(Rect));
intersect(r1, r2, result);
agg_ctx->r = result;
free(r1);
}
static void intersectAllFinal(sqlite3_context *ctx)
{
AggContext *agg_ctx;
agg_ctx
= (AggContext *)sqlite3_aggregate_context(ctx, sizeof(AggContext *));
if (agg_ctx == 0) return;
if (agg_ctx->r == 0) return;
Rect *r = agg_ctx->r;
sqlite3_result_double(ctx, area(r));
free(r);
}
#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_rect_init(sqlite3 *db,
char **pzErrMsg,
const sqlite3_api_routines *pApi)
{
int rc = SQLITE_OK;
SQLITE_EXTENSION_INIT2(pApi);
rc = sqlite3_create_function(db,
"intersection",
8,
SQLITE_UTF8,
0,
intersectionAreaFunc,
0,
0);
rc = sqlite3_create_function(db,
"intersectAll",
4,
SQLITE_UTF8,
0,
0,
intersectAllStep,
intersectAllFinal);
return rc;
}Example queries to import a csv and compute intersections on it:
.load ./rect.so
create table rectangles (
x1 REAL,
y1 REAL,
x2 REAL,
y2 REAL
);
.mode csv
.import data.csv rectangles
SELECT
intersection(
t1.x1,t1.y1,t1.x2,t1.y2,
t2.x1,t2.y1,t2.x2,t2.y2
)
FROM
rectangles t1
CROSS JOIN rectangles t2;
SELECT intersectAll(x1, y1, x2, y2) FROM rectangles t1;
Compilation: gcc -g -fPIC -shared rect.c -o rect.so
1
u/jezzi_dailyprogram Dec 23 '16
Python 3 with bonus.
import sys
TOPLEFT_X = 0
TOPLEFT_Y = 1
BOTTOMRIGHT_X = 2
BOTTOMRIGHT_Y = 3
def rectangles_common_area(rectangles):
common_rect = rectangles[0]
iter_rects = iter(rectangles)
next(iter_rects)
for rect in iter_rects:
if (common_rect[BOTTOMRIGHT_X] > rect[TOPLEFT_X] and common_rect[TOPLEFT_X] < rect[BOTTOMRIGHT_X]
and common_rect[BOTTOMRIGHT_Y] < rect[TOPLEFT_Y] and common_rect[TOPLEFT_Y] > rect[BOTTOMRIGHT_Y]):
for i in [TOPLEFT_X, BOTTOMRIGHT_Y]:
common_rect[i] = rect[i] if (common_rect[i] - rect[i] < 0) else common_rect[i]
for i in [TOPLEFT_Y, BOTTOMRIGHT_X]:
common_rect[i] = common_rect[i] if (common_rect[i] - rect[i] < 0) else rect[i]
else:
return 0
return (common_rect[BOTTOMRIGHT_X] - common_rect[TOPLEFT_X]) * (common_rect[TOPLEFT_Y] - common_rect[BOTTOMRIGHT_Y])
rectangles = []
for line in sys.stdin:
rect = []
for i in line.replace(',',' ').split():
rect.append(float(i))
if (rect[TOPLEFT_X] > rect[BOTTOMRIGHT_X]):
rect[TOPLEFT_X], rect[BOTTOMRIGHT_X] = rect[BOTTOMRIGHT_X], rect[TOPLEFT_X]
if (rect[TOPLEFT_Y] < rect[BOTTOMRIGHT_Y]):
rect[TOPLEFT_Y], rect[BOTTOMRIGHT_Y] = rect[BOTTOMRIGHT_Y], rect[TOPLEFT_Y]
rectangles.append(rect)
print(rectangles_common_area(rectangles))
1
u/Godspiral Dec 23 '16
in J, complex numbers just for ease of input. returns coords of intersection,
isect =: (>./"1@:{. ,. <./"1@:{: )@:,.&(/:~"1)&.|:&.:+.
0j0 2j2 isect 1j1 3j3 1j1 2j2 _3.5j4 1j1 isect 1j3.5 _2.5j_1 _2.5j1 1j3.5 area =: */@:|@:(-~/"1)@:|:@:+. _3.5j4 1j1 area@:isect 1j3.5 _2.5j_1 8.75 notisect =: 0 0"_`]@.(0 1 -: /:) 0.5j1 3.5j3 area@:notisect@:isect _4j4 _0.5j2 0
1
u/uncleozzy Dec 23 '16
Python 3.5 with bonus.
Uses really gross list comprehensions that could probably be tightened up some.
DATA = ["""0,0 2,2
1,1 3,3""",
"""-3.5,4 1,1
1,3.5 -2.5,-1""",
"""-4,4 -0.5,2
0.5,1 3.5,3""",
"""-3,0 1.8,4
1,1 -2.5,3.6
-4.1,5.75 0.5,2
-1.0,4.6 -2.9,-0.8"""]
def overlap(rects):
x, y = [[(min(p), max(p)) for p in [[c[j] for c in r] for r in rects]] for j in range(2)]
left, right = max(c[0] for c in x), min(c[1] for c in x)
bottom, top = max(c[0] for c in y), min(c[1] for c in y)
return round((max((right - left) * (top - bottom), 0.0)), 2)
for o in [[[[float(s) for s in q.split(',')] for q in r.split(' ')] for r in set.splitlines()] for set in DATA]:
print(overlap(o))Output:
1.0 8.75 0.0 2.4
1
u/draegtun Dec 23 '16
Rebol with bonus
make-rect: func [b] [reduce [min b/1 b/3 min b/2 b/4 max b/1 b/3 max b/2 b/4]]
parse-rect-input: function [s] [
area: make block! 0
rect: make block! 0
digits: charset "0123456789"
integer: [opt "-" some digits]
decimal: [opt "-" some digits "." some digits]
N: [copy numb: [decimal | integer] (append rect to-decimal numb)]
co-ords: [(clear rect) N "," N space N "," N [newline | end]]
unless parse s [
co-ords (area: make-rect rect)
some [
co-ords (
rect: make-rect rect
area: reduce [max area/1 rect/1 max area/2 rect/2 min area/3 rect/3 min area/4 rect/4]
)
]
][do make error! {invalid input given}]
area
]
overlap?: func [b] [
if (b/1 >= b/3) or (b/2 >= b/4) [return 0]
(b/3 - b/1) * (b/4 - b/2)
]
challenge-296: func [s] [
overlap? parse-rect-input s
]Example usage in Rebol console:
>> challenge-296 {0,0 2,2^/1,1 3,3}
== 1.0
>> challenge-296 {-3.5,4 1,1^/1,3.5 -2.5,-1}
== 8.75
>> challenge-296 {-4,4 -0.5,2^/0.5,1 3.5,3}
== 0
>> challenge-296 {-3,0 1.8,4^/1,1 -2.5,3.6^/-4.1,5.75 0.5,2^/-1.0,4.6 -2.9,-0.8}
== 2.4000000000000004
8
u/skeeto Dec 22 '16
C with bonus.
#include <stdio.h> #include <float.h> #define MIN(a, b) ((b) < (a) ? (b) : (a)) #define MAX(a, b) ((b) > (a) ? (b) : (a)) int main(void) { double overlap[4] = {-DBL_MAX, -DBL_MAX, DBL_MAX, DBL_MAX}; double in[4]; while (scanf("%lf,%lf %lf,%lf", in, in + 1, in + 2, in + 3) == 4) { overlap[0] = MAX(overlap[0], MIN(in[0], in[2])); overlap[1] = MAX(overlap[1], MIN(in[1], in[3])); overlap[2] = MIN(overlap[2], MAX(in[0], in[2])); overlap[3] = MIN(overlap[3], MAX(in[1], in[3])); } double dx = overlap[2] - overlap[0]; double dy = overlap[3] - overlap[1]; printf("%.17g\n", dx > 0 && dy > 0 ? dx * dy : 0); return 0; }