Generiere konvexe Polygone aus Rechtecken

Question

Ich arbeite gerade an einem 2D-Beleuchtungssystem für ein Spiel. Die Karten bestehen aus Kacheln, die bestimmte Tags und Eigenschaften haben können. In diesem Fall habe ich einige Kacheln als "undurchsichtig" festgelegt und eine Funktion geschrieben, um für jede undurchsichtige Kachel eine Reihe von Rechtecken zu erzeugen. Ich möchte diese Geometrie optimieren, indem ich große Gruppen von Rechtecken in konvexe Polygone zusammenfüge.

Meine Rechtecke sind als eine Sammlung von Liniensegmenten in einem Array definiert.

Beispiel eines Rechteck Polygon:

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

So ist meine Frage, wie kann ich eine kleinere Gruppe von konvexen Polygonen aus einer großen Gruppe von Rechtecken erzeugen? Ich bin keineswegs ein Experte Coder so bitte fügen Sie eine gründliche Erklärung in Ihre Antwort sowie ein Beispiel, wenn Sie können. Ich habe mehr als ein paar Stunden damit verbracht, das herauszufinden.

Vielen Dank!

Answer 1

Hier ist ein O(n^2) Algorithmus für Ihr Problem, all die einleitenden Informationen, die Sie in diesem topcoder article ist brauchen, ich bin sicher, dass, wenn Sie die Linie Sweep-Algorithmus verwenden Sätze von Rechtecke zu finden, die dann die Zeit Komplexität der Lösung schneiden O(n log n) sein

Hauptidee: ein Satz Gruppe von Rechtecken erstellen dann für jedes Element des Satzes berechnet eine konvexe Hülle

n die Anzahl der Gruppen sein Lassen zunächst n = 0

1. nehmen Sie ein Rechteck a von Ihrem Satz (wenn es Mitglied einer Gruppe ist, springen Sie zum nächsten, wenn es keine Rechtecke mehr gibt, die keine Gruppe haben, dann bearbeiten Sie den Satz von Rechtecken, mehr dazu später)

2. Mark a als Mitglied der Gruppe n, versucht a mit jedem anderen unvisited Rechteck zu schneiden, wenn Sie eine Kreuzung mit dem Rechteck finden b dann läuft rekursiv 2 mit b

3. Sie alle haben werden die Rechtecke, die Teil der Gruppe n sind, die b später verarbeitet e, ließ n = n + 1 und Wiederholung 1 (dieser Algorithmus wird durch die Art und Weise genannt dfs) ​​

4. Nun, da jedes Rechteck zu seinem eigenen Gruppe konvexe Hülle auf der Gruppe lief zugeordnet ist, wird der Ausgang n konvexer Polygone

Das es so etwas wie dieses

// 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) 
    }) 
} 

aussehen Umsetzung