intersezioni tra 2 rettangoli

[omniaforever]

salve, avrei bisogno di un semplice algoritmo che, dati 2 rettangoli, mi verifica se si intersecano o meno..
ogni rettangolo è semplicemente individuato da x,y (la x va da sinistra a destra, la y dall'alto al basso) e da width e hight...
quindi i punti sono (x,y) (x,y+height), (x+width,y), (x+width,y+height)
grazie

[black_wizard]

algoritmo per quale linguaggio? php, c++ etc etc

[Freaxxx]

io sfrutterei le proiezioni sugli assi e la distanza dal centro, ma questo è solo il primo input che mi viene in mente.

[SerMagnus]

forse geometricamente puoi sfruttare qualche calcolo con matrici o delle proprietà dei vettori

[black_wizard]

dovresti fare il confronto tra le coordinate
Cioè rettangolo A(x1,y1) (x2,y2) e rettangolo B(x1,y1) (x2,y2)
Ax1 <= Bx1 <= Ax2 AND Ay1 <= By1 <= Ay2
e anche per l'altra coordinata
Ax1 <= Bx2 <= Ax2 AND Ay1 <= By2 <= Ay2

se una delle 2 è verificata..i rettangoli intersecano

[PGI-Bis]

La questione è un po' più banale.

Dati i due rettangoli R1 e R2, allineati con gli assi, puoi verificare l'intersezione come verifica dell'intersezione delle proiezioni dei due rettangoli sugli assi. Il che si traduce in una verifica di interesezione tra due coppie di segmenti in uno spazio unidimensionale:

S0X(R0.X, R0.X + R0.W) interseca S1X(R1.X, R1.X + R1.W)
S0Y(R0.Y, R0.Y + R0.H) intereseca S1Y(R1.Y, R1.Y + R1.H)

Se entrambe le intersezioni sono vere, allora i due rettangoli si intersecano.
E quand'è che due segmenti SA e SB si intersecano? Quando:

(SA.inizio >= SB.inizio && SA.inizio < SB.fine) oppure
(SB.inizio >= SA.inizio && SB.inizio < SB.fine)

Da cui deriva che, detti R1 e R2 i rettangoli, x, y, w e h le loro proprietà:

S0X0 = R0X
S0X1 = R0X + R0W
S0Y0 = R0Y
S0Y1 = R0Y + R0H
S1X0 = R1X
S1X1 = R1X + R1W
S1Y0 = R1Y
S1Y1 = R1Y + R1H
XINT = (S0X0 >= S1X0 && S0X0 < S1X1) || (S1X0 >= S0X0 && S1X0 < S0X1)
YINT = (S0Y0 >= S1Y0 && S0Y0 < S1Y1) || (S1Y0 >= S0Y0 && S1Y0 < S0Y1)
INTERSEZIONE = XINT && YINT

Magari si può anche risparmiare qualche confronto ma il principio è quello.

[Freaxxx]

Originariamente inviato da PGI-Bis

La questione è un po' più banale.

Dati i due rettangoli R1 e R2, allineati con gli assi, puoi verificare l'intersezione come verifica dell'intersezione delle proiezioni dei due rettangoli sugli assi. Il che si traduce in una verifica di interesezione tra due coppie di segmenti in uno spazio unidimensionale:

S0X(R0.X, R0.X + R0.W) interseca S1X(R1.X, R1.X + R1.W)
S0Y(R0.Y, R0.Y + R0.H) intereseca S1Y(R1.Y, R1.Y + R1.H)

Se entrambe le intersezioni sono vere, allora i due rettangoli si intersecano.
E quand'è che due segmenti SA e SB si intersecano? Quando:

(SA.inizio >= SB.inizio && SA.inizio < SB.fine) oppure
(SB.inizio >= SA.inizio && SB.inizio < SB.fine)

Da cui deriva che, detti R1 e R2 i rettangoli, x, y, w e h le loro proprietà:

S0X0 = R0X
S0X1 = R0X + R0W
S0Y0 = R0Y
S0Y1 = R0Y + R0H
S1X0 = R1X
S1X1 = R1X + R1W
S1Y0 = R1Y
S1Y1 = R1Y + R1H
XINT = (S0X0 >= S1X0 && S0X0 < S1X1) || (S1X0 >= S0X0 && S1X0 < S0X1)
YINT = (S0Y0 >= S1Y0 && S0Y0 < S1Y1) || (S1Y0 >= S0Y0 && S1Y0 < S0Y1)
INTERSEZIONE = XINT && YINT

Magari si può anche risparmiare qualche confronto ma il principio è quello.

grazie al pippolo, se sono allineati con gli assi lo sa fare pure il pesce rosso nell'ampolla

[PGI-Bis]

E' evidente nella richiesta: neanche Euclide riuscirebbe ad individuare un rettangolo non allineato con gli assi dati un punto e due estensioni.

[banryu79]

Originariamente inviato da PGI-Bis

...neanche Euclide riuscirebbe ad individuare un rettangolo non allineato con gli assi dati un punto e due estensioni.

Buona questa