0

我目前正在为游戏开发 2D 照明系统。地图由可以具有某些标签和特征的图块组成。在这种情况下，我将一些图块设置为“不透明”，并编写了一个函数来为每个不透明图块生成一堆矩形。我想通过将大组矩形合并成凸多边形来优化这个几何形状。

我的矩形被定义为数组中线段的集合。

矩形多边形示例：

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}}];

所以我的问题是如何从一大群矩形中生成一小群凸多边形？我绝不是专业的编码人员，因此请在您的答案中包含详尽的解释，并在可能的情况下提供示例。我花了几个多小时试图自己解决这个问题。

谢谢！

4

1 回答 1

0

这是O(n^2)针对您的问题的算法，您需要的所有介绍性信息都在这篇topcoder 文章中，我敢肯定，如果您使用线扫描算法来查找相交的矩形集，那么解决方案的时间复杂度将为O(n log n)

主要思想：创建一组矩形，然后为集合中的每个元素计算一个凸包

让n是组的数量，最初n = 0

  1. 从您的集合中取出一个矩形a（如果它是某个组的成员，则跳到下一个，如果没有更多没有组的矩形，则处理该组矩形组，稍后会详细介绍）

  2. 标记a为组的成员n，尝试a与所有其他未访问的矩形相交，当您找到与矩形的交点时，b然后递归运行 2b

  3. 您将拥有属于该组的所有矩形，这些矩形n将在稍后处理，让n = n + 1并重新运行 1（顺便说一下，此算法称为 dfs）

  4. 现在每个矩形都被分配给它自己的组在组上运行凸包，输出将是n凸多边形

它的实现看起来像这样

// 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)
  })
}
于 2016-04-23T04:58:24.663 回答