Individuazione della posizione del rettangolo che consente di coprire i punti massimi nello spazio 2D

Dato uno spazio 2D con punti X, come posso trovare in modo efficiente dove posizionare un rettangolo a dimensione fissa, in modo che copra il maggior numero possibile di quei punti X?Individuazione della posizione del rettangolo che consente di coprire i punti massimi nello spazio 2D

Ho bisogno di qualcosa in questo senso per posizionare una finestra in un gioco 2D che sto costruendo.

fonte

2015-09-06 Harry Mexican

È consentito di trasformare il vostro rettangolo o sono i lati paralleli per assi X e Y? – dasblinkenlight

Perché non determinare il minimo e il massimo X e Y dei punti e costruire il suo rettangolo di estensione. Se gli assi del rettangolo vengono ruotati, è un rettangolo di limitazione dell'area minimo, coprirà tutti i punti come il rettangolo di estensione, ma avrà un'area più piccola. La prima opzione è semplice da implementare, la seconda è più difficile. –

non è consentito ruotare il rettangolo –

Ordinare i punti da sinistra a destra. Imposta un puntatore left nel punto più a sinistra e un puntatore right nel punto più a destra che rientra in left + width. Quindi scorrere tutti i punti, ricalcolando la posizione del puntatore right ogni volta finché non si trova all'ultimo punto.
Ordina ogni sottoinsieme di punti tra sinistra e destra dall'alto verso il basso. Imposta un puntatore top nel punto più alto e un puntatore bottom nel punto più basso che rientra in top + height. Quindi scorrere tutti i punti, ricalcolando la posizione del puntatore bottom ogni volta finché non si trova all'ultimo punto.
Per ogni sottogruppo di punti tra sinistra, destra, alto e basso, verificare quanti punti ha e memorizzare il sottoinsieme ottimale.
Una volta trovato il sottoinsieme ottimale, il centro del rettangolo si trova a metà tra il punto più a sinistra e quello più a destra e a metà tra il punto più alto e quello più basso.

Di seguito è una semplice implementazione in Javascript, che può essere ottimizzata su molti punti. Esegui lo snippet di codice per visualizzare i risultati con dati casuali.

function placeRectangle(p, width, height) { 
 
    var optimal, max = 0; 
 
    var points = p.slice(); 
 
    points.sort(horizontal); 
 

 
    for (var left = 0, right = 0; left < points.length; left++) { 
 
     while (right < points.length && points[right].x <= points[left].x + width) ++right; 
 
     var column = points.slice(left, right); 
 
     column.sort(vertical); 
 

 
     for (var top = 0, bottom = 0; top < column.length; top++) { 
 
      while (bottom < column.length && column[bottom].y <= column[top].y + height) ++bottom; 
 
      if (bottom - top > max) { 
 
       max = bottom - top; 
 
       optimal = column.slice(top, bottom); 
 
      } 
 
      if (bottom == column.length) break; 
 
     } 
 
     if (right == points.length) break; 
 
    } 
 

 
    var left = undefined, right = undefined, top = optimal[0].y, bottom = optimal[optimal.length - 1].y; 
 
    for (var i = 0; i < optimal.length; i++) { 
 
     var x = optimal[i].x; 
 
     if (left == undefined || x < left) left = x; 
 
     if (right == undefined || x > right) right = x; 
 
    } 
 
    return {x: (left + right)/2, y: (top + bottom)/2}; 
 

 
    function horizontal(a, b) { 
 
     return a.x - b.x; 
 
    } 
 

 
    function vertical(a, b) { 
 
     return a.y - b.y; 
 
    } 
 
} 
 

 
var width = 160, height = 90, points = []; 
 
for (var i = 0; i < 10; i++) points[i] = {x: Math.round(Math.random() * 300), y: Math.round(Math.random() * 200)}; 
 
var rectangle = placeRectangle(points, width, height); 
 

 
// SHOW RESULT IN CANVAS 
 
var canvas = document.getElementById("canvas"); 
 
canvas.width = 300; canvas.height = 200; 
 
canvas = canvas.getContext("2d"); 
 
paintRectangle(canvas, rectangle.x - width/2, rectangle.y - height/2, width, height, 1, "red"); 
 
for (var i in points) paintDot(canvas, points[i].x, points[i].y, 2, "blue"); 
 
function paintDot(canvas, x, y, size, color) { 
 
    canvas.beginPath(); 
 
    canvas.arc(x, y, size, 0, 6.2831853); 
 
    canvas.closePath(); 
 
    canvas.fillStyle = color; 
 
    canvas.fill(); 
 
} 
 
function paintRectangle(canvas, x, y, width, height, line, color) { 
 
    canvas.beginPath(); 
 
    canvas.rect(x, y, width, height); 
 
    canvas.closePath(); 
 
    canvas.lineWidth = line; 
 
    canvas.strokeStyle = color; 
 
    canvas.stroke(); 
 
}

<BODY STYLE="margin: 0; border: 0; padding: 0;"> 
 
<CANVAS ID="canvas" STYLE="width: 300px; height: 200px; float: left; background-color: #F8F8F8;"></CANVAS> 
 
</BODY>

fonte

2015-09-08 06:42:47 m69

Questa è una risposta ridicolmente completa. Esecuzione di codice su cui è possibile fare clic! Buon lavoro, accettandolo. Non sembra che lo userò anche perché ho apportato alcune modifiche al gameplay in modo che non sia più necessario soddisfare i requisiti della domanda. Penso che sarebbe stato troppo costoso comunque. Ha bisogno di eseguire ogni frame a 60fps + tutti i punti sono in costante movimento. L'ordinamento potrebbe averlo ucciso. In ogni caso, grazie. –

@HarryMexican Ho scritto il codice per dimostrare l'idea, ma se si può effettivamente farlo in questo modo dipende in realtà da quanti punti ci sono e quanto velocemente deve essere; eseguirlo al framerate del gioco sarebbe probabilmente problematico con qualcosa di più di una manciata di punti. L'algoritmo si basa sull'ordinamento, quindi non c'è modo di ignorarlo per aumentare l'efficienza. Un algoritmo che guarda solo i punti che stanno per lasciare il rettangolo e che quindi lo spostano gradualmente probabilmente sarebbe più efficiente nel tuo caso. – m69

Sì, è un interessante esperimento mentale in ogni caso. Spero che tu abbia qualcosa da scrivere e che aiuti qualcun altro a cercare un algoritmo di questo tipo.:) –

Individuazione della posizione del rettangolo che consente di coprire i punti massimi nello spazio 2D

risposta

Problemi correlati