CODEWITHSUNDEEP
algorithmgeometrycomputational-geometry
Keloo
Keloo

Reputation: 1408

How to find the border length created from a conglomeration of various 2D rectangles?

You are given a set of rectangles and you are asked to determine the length of the perimeter of the complex polygon formed by the silhouette of the overlapping rectangles.

Upvotes: 3

Views: 505

Answers (3)

MBo
MBo

Reputation: 80325

In the book "Computational Geometry" of Preparata and Shamos the 8th chapter is devoted to rectangles union problems. The problem of union perimeter is solved with sweep line algorithm (link one link two) and segment tree in O(NLogN) time

Addition

Upvotes: 2

Anton Knyazyev
Anton Knyazyev

Reputation: 474

Are the rectangles axis-aligned? If so, you can try this. Sort starts and ends along one axis (let's say x), then maintain a list of consecutive intervals - points, sorted by y, with each interval having an integer 'winding number' (initially ymin..ymax, 0). Then when you process the next edge along x, you find what existing intervals it overlaps with, splitting the ones on the ends, and update (++ for front edges, -- for back edges) their winding numbers. For instance:

 0000111111122222111000
+000++++++++++000000000
=0001222222233222111000
    1                   (perimeter update)

For opening eges, add new intervals with winding number 1 to the perimeter. For closing - with 0. For efficiency, you can also merge intervals with identical winding numbers.

Then do the same for y.

Upvotes: 0

John Doe
John Doe

Reputation: 971

  • We start with the positions (of all 4 points) of each of the various smaller overlapping rectangles.
  • We construct the new polygon by walking through the corner points of the various rectangles.
  • We find the most outlying points (farthest North/South/East/West) encountered for any given row or column of the matrix, storing these in a separate array.
  • Once we have gathered all the points for our new polygon, we sort its points in a clockwise order around the center of the grid (if not already sorted).
  • We measure its perimeter by measuring the distance of each line (between each set of consecutive points) on its surface and adding it to the total.
 .  .  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  *  x  x  *  .  .  .  .
 .  .  .  .  x  .  .  x  .  .  .  .
 .  .  .  .  x  .  .  x  .  .  .  .
 .  .  *  z  *  z  .  x  .  .  .  .
 .  .  z  .  x  z  .  x  .  .  .  .
 .  .  z  .  x  z  .  x  .  .  .  .
 .  *  *  y  y  y  y  *  y  y  *  .
 .  y  z  .  x  z  .  x  .  .  y  .
 .  *  *  y  y  y  y  *  y  y  *  .
 .  .  z  .  x  z  .  x  .  .  .  .
 .  .  z  .  x  *  x  *  .  .  .  .
 .  .  z  .  .  z  .  .  .  .  .  .
 .  .  *  z  z  *  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .

In the diagram above, we have rectangles x, y, and z. Asterisks the are outlying corners of our new polygon.

Upvotes: 0

Related Questions