Rettangolo nel piano cartesiano

[gabry]

Il mio problema e' il seguente: dati i 4 punti che compongono un rettangolo nel piano cartesiano, e dato un quinto punto, esiste un algoritmo per capire se il punto e' contenuto nel rettangolo?

[Cheguevilla]

Certo.
Sono necessari solo due vertici del rettangolo, cioè quelli di una diagonale.
Supponendo che il punto a sia quello in alto a sinistra, condizione ottenibile con un semplice algoritmo:
Chiamiamoli ax, ay, bx, by.

Codice:

if(ax<xx && xx<bx && by<yy && yy<ay) return VERO
else return FALSO


Se il problema e' ordinare i punti in modo da trovare quello in alto a sinistra e quello in basso a destra:
Supponiamo che le coordinate del rettangolo siano contenute in una matrice 4x2, in riga i punti, in colonna x e y.

Codice:

for(punto=1;punto<=3;punto++)
   {
    a=b=0;
    if(rettangolo[punto][0]<=rettangolo[a][0] && rettangolo[punto][1]>=rettangolo[a][1]) a=punto;
    if(rettangolo[punto][0]>=rettangolo[a][0] && rettangolo[punto][1]<=rettangolo[a][1]) b=punto;
   }


[gabry]

troppo facile... in realta' io non ho detto "un rettangolo con i lati paralleli agli assi"
l'idea e' quella di trovare le rette parallele ai lati passanti per il centro e poi misurare se la distanza da tali rette al punto e' maggiore della meta' del lato opposto, ma algoritmicamente parlando viene complicata, in piu' e' difficile gestire la m dell'equazione canonica perche' puo' andare ad infinito, ma un linguaggio di programmazione, per come gestisce la costante infinito, crea un gap notevole tra l'ultimo punto prima di infinito e l'infinito stesso.

[Cheguevilla]

Si, esiste.
Ora me ne viene in mente uno un po' violento, ma forse ne esistera' uno piu' semplice.
Calcola il coefficiente angolare dei due segmenti.
Considera un punto qualsiasi come giacente su una retta con lo stesso coefficiente angolare di uno dei due segmenti.
Trova l'intersezione con l'asse x di questa retta.
La differenza tra l'intersezione e l'origine e' pari alla differenza (orizzontale o verticale) tra il punto e il segmento in considerazione.

[gabry]

Ok! fatto! praticamente trovo la retta passante per il centro che attraversa il lato più lungo, poi traccio una perpendicolare a tale retta a partire dal punto del quale controllo la giacenza nel rettangolo, ora faccio distanza retta/punto. Se tale distanza è minore della metà del lato più corto e l'intersezione della retta passante per il centro con la perpendicolare giace tra le due rette su cui giacciono i lati più corti (si capisce controllando se l'intersezione tra la retta passante per il centro e la perpendicolare passante per il punto sta fra i punti di intersezione tra la retta passante per il centro e i lati più corti) il punto è all'interno del rettangolo.

[mircoFN]

@gabry

i punti del rettangolo sono ordinati oppure no? Mi spiego meglio, quando fornisci i dati del rettangolo sai già quali sono i due lati che formano un angolo retto (e quindi basterebbero solo tre punti come dati) oppure i 4 punti sono forniti 'in disordine?

ciao

[gabry]

Scusa, ma non serve sapere se i punti sono ordinati, in ogni caso se ne prendi 3 essi formeranno sempre un triangolo rettangolo, per capire in qual'e' l'angolo basta vedere quali sono i due piu' distanti tra loro (con la formula della distanza punto punto) che saranno i due appartenenti all'ipotenusa, e quindi prendere il rimanente. Poi a cosa ti serve quell'informazione?