从矩形生成凸多边形

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

所以我的问题是我怎么能产生从一大群矩形的一小批凸多边形？我绝不是专家的编码员，所以请在答案中包括一个详尽的解释，并且如果可以的话，请举例。我花了超过几个小时试图自己解决这个问题。

谢谢！

来源

2016-04-23 Derek de la Peza

这里有一个O(n^2)算法的问题，所有你需要的介绍性的信息就是在这个topcoder article，我敢肯定，如果你使用的线扫描算法找到套矩形相交，则解决方案的时间复杂度将是O(n log n)

主要思想：创建一组矩形的组然后对于该组的每个元素计算一个凸包

让n是基的数目，最初n = 0

从你的集合中取一个矩形a（如果它是某个组的成员，则跳到下一个组，如果没有更多的矩形没有组，则处理该组矩形，稍后再处理该组）
马克a作为组n的成员，试图相交a与其他所有未访问的矩形，当你发现用矩形b一个路口，然后递归地b
运行2你必须全部属于组n的部分的矩形将会b ë处理后，让n = n + 1并重新运行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) 
    }) 
}

实施

来源

2016-04-23 04:58:24

从矩形生成凸多边形

回答

相关问题