从矩形生成凸面

Generate convex polygons from rectangles

本文关键字：      更新时间：2023-09-26

我目前正在为游戏开发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}}];

所以我的问题是我如何从一大组矩形生成一小组凸多边形？我绝不是专业的编码人员，所以请在您的答案中包含详尽的解释以及示例（如果可以的话）。我花了几个小时试图自己解决这个问题。

谢谢！

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

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

n组数，最初n = 0

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

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

    3. 并带有b

  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)
  })
}
相关文章：
  • 没有找到相关文章