Ritaglio di un rettangolo in JavaScript

Sto provando a scrivere una funzione che prende due rettangoli sovrapposti e restituisce una matrice di rettangoli che copre l'area del rettangolo A, ma esclude l'area del rettangolo B. Sto avendo difficoltà a capire come appare questo algoritmo dato che il numero di possibili collisioni è enorme e difficile da spiegare.Ritaglio di un rettangolo in JavaScript

tl; dr Sto provando a ritagliare un rettangolo utilizzando un altro rettangolo creando un insieme di rettangoli che coprono l'area rimanente.

|-------------|        |-------------| 
|A   |        |R1   | 
|  |-------|----|       |-----|-------| 
|  |B  | |   To    |R2 | 
|  |  | |   ====>   |  | 
|  |  | |       |  | 
|-----|-------| |       |-----| 
     |   | 
     |------------| 

POSSIBLE OVERLAP PATTERNS 

|-----|   |-----|  |-----|  |-----| 
| |---|-|  |-|---| |  | |-| |  | |-| | 
|-|---| |  | |---|-|  |-|-|-|  | |-| | 
    |-----|  |-----|   |-|   |-----| 

    |-|   |-----|   |-----| 
|-|-|-|  | |---|-|  |-|---| | 
| |-| |  | |---|-|  |-|---| | 
|-----|  |-----|   |-----|

noti che i possibili modelli di sovrapposizione è doppia rispetto a quella visualizzata perché rettangolo A e B potrebbero essere rettangolo etere in qualsiasi dei modelli di sovrapposizione sopra.

fonte

2013-05-18 Robert Hurst

Potrebbe essere possibile utilizzare i punti di vertice per questo. È possibile calcolare le nuove coordinate del rettangolo in base alla distanza tra i vertici in B da A. – Nikki

C'è un altro problema, il risultato a volte più di un rettangolo. tra uno e nove penso. –

Sicuramente esiste un algoritmo standard? Comunque; un'idea. Ci sono 4 coordinate xe 4 coordinate y, le tue nuove zone saranno sempre una combinazione di queste. Le 4 x coords dividono la tela in 5 bande verticali, le y si coordinano in 5 bande orizzontali, se la peggiore viene al peggio ci sono 25 rettangoli non sovrapposti che appartengono ad A, B, nessuno dei due o entrambi. Mantieni quelli appartenenti a solo A ed escludi tutti gli altri. – boisvert

Non ci sarà una soluzione unica per una particolare messa a punto, ma si può facilmente trovare una delle soluzioni con questo algoritmo:

Trova un rettangolo all'interno di un rettangolo che è al di sopra B. Se la parte superiore A è più alto di B (cioè ha un valore inferiore in px), c'è un tale rettangolo. Questo rettangolo è definito da: (bordo sinistro di A, bordo superiore di A) (bordo destro di A, bordo superiore di B).
Se il margine sinistro di B si trova a destra del bordo sinistro di A, il prossimo rettangolo è: (bordo sinistro di A, min (bordo superiore di A, bordo superiore di B)) a (bordo sinistro di B , max (bordo inferiore di a, bordo inferiore B))
Se il bordo destro di B è a sinistra del bordo destro di B, simile al precedente
... e l'eventuale rettangolo sotto B

In totale, otterrete da 0 a 4 rettangoli.

pseudocodice con un po 'insolita, ma per questo scopo chiaro, definizione di rettangolo:

function getClipped(A, B) { 
    var rectangles = []; 
    if (A.top < B.top) { 
     rectangles.push({ left: A.left, top: A.top, right: A.right, bottom: B.top }); 
    } 
    if (A.left < B.left) { 
     rectangles.push({ left: A.left, top: max(A.top, B.top), right: B.left, bottom: min(A.bottom, B.bottom) }); 
    } 
    if (A.right > B.right) { 
     rectangles.push({ left: B.right, top: max(A.top, B.top), right: A.right, bottom: min(A.bottom, B.bottom) }); 
    } 
    if (A.bottom > B.bottom) { 
     rectangles.push({ left: A.left, top: B.bottom, right: A.right, bottom. A.bottom }); 
    } 

    return rectangles; 
} 

var rectA = { left: nn, top: nn, right: nn, bottom: nn}; 
var rectB = { left: nn, top: nn, right: nn, bottom: nn}; 

var clipped = getClipped(rectA, rectB) ;

fonte

2013-05-18 08:24:04

Alcuni casi non sono coperti - ad es. se B è più largo di A e taglia A in due ... – boisvert

@boisvert, è coperto. Tutte le tue nove regioni sono completamente coperte. Non matematicamente elegante come la tua spiegazione, ma con un algoritmo molto semplice. –

Oops ... Non ho prestato attenzione al tuo uso di min e max. Hai ragione, funziona molto bene. Non vedere nulla di inelegante a riguardo. – boisvert

I due rettangoli dividono lo schermo in 9 zone (non 14). Pensare ancora di configurazioni:

y1 -> |-------------|  
     |A   |   
y2 -> |  |-------|----| 
     |  |B  | | 
     |  |  | | 
     |  |  | | 
y3 -> |-----|-------| | 
      |   | 
y4 ->  |------------| 
    ^ ^ ^^
     x1 x2  x3 x4

Le coordinate x definire 5 bande verticali, ma la prima (a sinistra) e l'ultimo (a destra) sono poco interessanti, in modo che solo bisogno di lavorare sulle 3 bande da x1 a x4. Lo stesso per le coordinate y: tre bande orizzontali da y1 a y4.

Quindi si tratta di 9 zone rettangolari che appartengono a A, B, nessuna o entrambe. Il vostro esempio è suddiviso in questo modo:

|-----|-------|----|  
    |A |A  |none| 
    |-----|-------|----| 
    |A |Both |B | 
    |  |  | | 
    |  |  | | 
    |-----|-------|----| 
    |none |B  |B | 
    |-----|-------|----|

Quindi confrontando le coordinate di A e B, si trova quale delle 9 zone appartengono a solo R. Sono le zone da tenere.

fonte

2013-05-18 08:21:05 boisvert

Grazie, questo è molto utile. Saluti! –

Ma vedi la risposta di dan.p che ti dà una soluzione completa ... – boisvert

Ritaglio di un rettangolo in JavaScript

risposta

Problemi correlati