Generate convex polygons from rectangles

Question

I am currently working on a 2D lighting system for a game. The maps are composed of tiles which can have certain tags and traits. In this case I have set some tiles as "opaque" and written a function to generate a bunch of rectangles for each opaque tile. I would like to optimize this geometry by merging large groups of rectangles into convex polygons.

My rectangles are defined as a collection of line segments in an array.

Example of a rectangle polygon:

var polygon = [
{a:{x:0,y:0}, b:{x:640,y:0}},
{a:{x:640,y:0}, b:{x:640,y:360}},
{a:{x:640,y:360}, b:{x:0,y:360}},
{a:{x:0,y:360}, b:{x:0,y:0}}];

So my question is how can I generate a smaller group of convex polygons from a large group of rectangles? I am by no means an expert coder so please include a thorough explanation in your answer as well as an example if you can. I have spent more than a few hours trying to figure this out on my own.

Thank you!

Mauricio Poppe Mauricio Poppe · Accepted Answer · 2016-04-23T04:58:24

Here's a O(n^2) algorithm for your problem, all the introductory info you need is at this topcoder article, I'm sure that if you use the line sweep algorithm to find sets of rectangles that intersect then the solution's time complexity will be O(n log n)

Main idea: create a set of group of rectangles then for each element of the set compute a convex hull

Let n be the number of groups, initially n = 0

take a rectangle a from your set (if it's member of some group skip to the next one, if there are no more rectangles that don't have a group then process the set of group of rectangles, more on this later)
Mark a as a member of the group n, try to intersect a with every other unvisited rectangle, when you find an intersection with the rectangle b then recursively run 2 with b
You'll have all the rectangles that are part of the group n which will be processed later, let n = n + 1 and rerun 1 (this algorithm is called dfs by the way)
Now that each rectangle is assigned to it's own group run convex hull on the group, the output will be n convex polygons

The implementation it look something like this

// input
var rectangles = [ ... ];

function dfs(a, group, n) {
  assignRectangleToGroup(a, n)
  group.push(a)
  rectangles.forEach(function (b) {
    if ( rectangleDoesntHaveGroup(b) &&
        rectangleIntersects(a, b)) {
      dfs(b, group, n)
    }
  })
}

function generateConvexPolygons() {
  var n = 0;
  var set = []
  rectangles.forEach(function (a) {
    if (rectangleDoesntHaveGroup(a)) {
      var group = []
      dfs(a, group, n)
      set.push(group)
      n += 1
    }
  })

  return set.map(function (group) {
    return convexHull(group)
  })
}

Generate convex polygons from rectangles

1 Answers