CODEWITHSUNDEEP
algorithmmathgeometrycomputational-geometry
Diamond Block
Diamond Block

Reputation: 159

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

Upvotes: 0

Views: 737

Answers (3)

RaffleBuffle
RaffleBuffle

Reputation: 5455

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))

Upvotes: 2

Sơn Ninh
Sơn Ninh

Reputation: 331

There are 2 cases in total. Let say A and B are the number of corners on the left and right side of the red line, respectively.
Case 1: A = B = 2, then there are 2 trapezoids.
Case 2: A = 1 or B = 1, then there is at least 1 triangle.

Upvotes: 0

SomeDude
SomeDude

Reputation: 14228

Given two points of the straight line, you can pick the other two points from the corners of the rectangle to get the quadrilateral and then you could use the shoelace formula to compute the area of that quadrilateral.

If you find one quadrilateral area, you can find the other area just by subtracting first quadrilateral's area from the area of the whole rectangle.

Upvotes: 0

Related Questions