從矩形生成凸多邊形

我目前正在爲一款遊戲開發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

從矩形生成凸多邊形

回答

相關問題