从矩形生成凸多边形

Question

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

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

矩形多边形示例：

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

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

谢谢！

Answer 1

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

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

设n为组数，最初n = 0

从你的集合中取出一个矩形a（如果它是某个组的成员跳到下一个，如果没有更多的矩形没有组然后处理一组矩形组，稍后会详细介绍）
将a标记为组n的成员，尝试将a与每个其他未访问的矩形相交，当您发现与矩形的交点时b 然后递归运行 2 与 b
您将拥有组 n 中的所有矩形，稍后将对其进行处理，让 n = n + 1 和 re运行 1（这算法顺便叫dfs)
现在每个矩形都分配给了它自己的组运行组上的凸包，输出将是 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)
  })
}

从矩形生成凸多边形

Generate convex polygons from rectangles

javascript

geometry

polygon

convex