Search code examples
algorithmmathgeometrycomputational-geometry

Finding two areas of a rectangle separated by a line

Given a rectangle and two points on the borders of the rectangle, where these two points will never share the same border, draw a line connecting these two points. Find the area of the two polygons formed by dividing the rectangle with this line. I am looking for an algorithm to find these two areas.

This seems like an easy problem but I couldn't find a consistent way to write the algorithm.

Here is an illustration of the problem with some example cases:

enter image description here

Solution

  • If we examine the 6 possible configurations we see that in all cases the area of one polygon is equal to half the area of the rectangle formed by the endpoints of the line (red), plus an additional rectangle (green) in the case where the line spans the width or height of the outer rectangle.

    enter image description here

    The area of one polygon is therefore given by:

    r1, r2 : corner points of the rectangle
p1, p2 : endpoints of the line

area = abs(p1.x - p2.x) * abs(p1.y - p2.y) / 2

if abs(p1.x - p2.x) == abs(r1.x - r2.x)
  area = area + abs(r1.x - r2.x) * (min(p1.y, p2.y) - min(r1.y, r2.y))
else if abs(p1.y - p2.y) == abs(r1.y - r2.y)
  area = area + abs(r1.y - r2.y) * (min(p1.x, p2.x) - min(r1.x, r2.x))