CODEWITHSUNDEEP
javascriptalgorithm
Alexander Tsepkov
Alexander Tsepkov

Reputation: 4186

Determine whether a region defined by a group of rectangular elements is rectangular

I have a set of elements (they're DOM elements with absolute coordinates, but the problem is more about the algorithm than JavaScript, once I get their coordinates with getBoundingClientRect() the rest of the problem is generic enough that it's applicable in other domains). I need to determine if the area defined by these rectangles is rectangular or not. Here are a few examples:

enter image description here

The elements would never overlap, I'm trying to figure out an efficient algorithm for determining whether the region is rectangular, preferably in linear time. Although it's not the end of the world if it's higher time complexity as long as it's perceived to be instantaneous to the user with say... 50 tiles. My use case is basically a game that would reject user operation if selected elements don't align.

Upvotes: 2

Views: 71

Answers (1)

moreON
moreON

Reputation: 2008

Since you can guarantee no overlaps, you could:

  • find a minimal bounding rectangle
    • by finding most extreme left/right/top/bottom coordinates
  • find that bounding rectangle's area
  • find the sum of the areas of the rectangles.

If the bounding rectangle has the same area as the sum of all the rectangles areas then the rectangles all fit neatly in the bounding rectangle.

Upvotes: 3

Related Questions