- Come ordinare i vertici di un poligono in senso orario-
 
COSA SERVE PER QUESTO TUTORIAL
Download | Chiedi sul FORUM | Glossario cognizioni basiche di C# e sul framework XNA
Ordinamento dei vertici con un po' di geometria

ORDINARE PUNTI DI UN POLIGONO
Perché è utile ordinare i punti di un poligono e come si può farlo.

Nel precedente tutorial avevamo visto come era possibile muoversi all'interno di un poligono convesso e verificare se un punto selezionato dall'utente si trovasse all'interno o all'esterno. Tuttavia, per questioni di semplicità, avevamo dovuto imporre che i punti del poligono fossero forniti dall'utente in senso orario; questa è una grande limitazione che ci proponiamo di eliminare in questo tutorial. L'ordinamento in particolare ci servirà nel prossimo articolo per poter lavorare con scioltezza con i poligoni risultanti dalle intersezioni di due oggetti di cui si intende rilevare la collisione.
Per fare questo creeremo una classe, chiamata ClockwiseComparer, che ci permetterà di ordinare questi punti in senso orario. Dunque la principale modifica da apportare al progetto dell'articolo precedente è richiamarla dal metodo Update ogni volta che viene aggiunto un nuovo punto al poligono:


protected override void Update(GameTime gameTime)
{
    
	// [...]
	
    // Se nel precedente Update il tasto sinistro del mouse era premuto e ora non lo è più
    if (lastMouseState.LeftButton == ButtonState.Pressed && ms.LeftButton == ButtonState.Released)
    {
        // Punto in cui si è fatto click
        Vector2 ptCurrent = new Vector2(ms.X, ms.Y);

        // Se non è già presente tra i vertici
        if (!vertexes.Contains(ptCurrent))
        {
            // Aggiungiamo il punto cliccato alla lista dei vertici
            vertexes.Add(ptCurrent);
            // Creiamo un ClockwiseComparer tramite il quale ri-ordiniamo
            // la lista
            ClockwiseComparer cmpClockwise = new ClockwiseComparer(vertexes);
            vertexes.Sort(cmpClockwise);
        }
    }

	// [...]
    
    // Memorizziamo lo stato del mouse corrente
    lastMouseState = ms;
    base.Update(gameTime);
}

Non dobbiamo far altro che inizializzare la nostra classe ClockwiseComparer passandogli la lista di punti da ordinare e quindi invocare il metodo Sort sulla lista di vertici perché vengano ordinati secondo i criteri stabiliti da ClockwiseComparer.

LA CLASSE DI ORDINAMENTO IN SENSO ORARIO
Secondo quale regola i vertici vengono ordinati in senso orario.

Vediamo come si presenta la classe che ci permette di ordinare i vertici del poligono:


// Classe che implementa IComparer, di cui ci serviremo per
// ordinare i vertici in senso orario
public class ClockwiseComparer : IComparer<Vector2>
{
    // Variabile che conterrà il centro del poligono
    private Vector2 center;
    public Vector2 VertexCenter
    {
        get { return center; }
    }
    // Primo punto del poligono che useremo come riferimento
    // rispetto al quale calcolare tutti gli angoli per poi
    // poter ordinare.
    private Vector2 firstPoint;
    // Lunghezza del primo segmento, ovvero distanza del 
    // centro dal primo punto
    private float firstSegmentLength;

    public ClockwiseComparer(IList<Vector2> ptVertexes)
    {
        // Calcoliamo il centro come media di tutti i punti
        foreach (Vector2 pt in ptVertexes)
        {
            center.X += pt.X / ptVertexes.Count;
            center.Y += pt.Y / ptVertexes.Count;
        }

        // Memorizziamo il primo punto, che useremo come riferimento
        firstPoint = ptVertexes[0];

        // Calcoliamo la distanza del primo punto dal centro, ci servirà
        // per poter applicare il teorema del coseno (o teorema di Carnot)
        this.firstSegmentLength = Distance(center, firstPoint);
    }

    // Funzione statica che calcola la distanza tra due vettori utilizzando
    // il teorema di Pitagora
    static private float Distance(Vector2 pt1, Vector2 pt2)
    {
        return (float)Math.Sqrt(Math.Pow((pt1.X - pt2.X), 2) + Math.Pow((pt1.Y - pt2.Y), 2));
    }

    // Implementiamo la funzione di confronto che servirà per ordinare la lista
    // di vertici
    public int Compare(Vector2 x, Vector2 y)
    {
        // Un vertice viene prima di un altro in senso orario
        // se l'angolo che forma con il segmento di riferimento
        // è minore di quello dell'altro punto
        return GetAngle(x).CompareTo(GetAngle(y));
    }

    public float GetAngle(Vector2 pt)
    {
        // [...]
    }
}

Per prima cosa notiamo che implementa IComparer<Vector2>, il che significa che deve contenere un metodo Compare che restituisca un valore positivo, negativo o nullo a seconda che il primo punto sia maggiore, minore o uguale del secondo, seguendo un certo criterio. In questo caso restituirà +1 se il primo punto viene dopo in senso orario o -1 se viene prima. Il metodo List.Sort potrà grazie a questo metodo ordinare e gli elementi della lista e restituirceli in ordine crescente.
In secondo luogo vediamo che in sostanza la classe memorizza tre variabili: il primo punto della lista (firstPoint), il centro dei vertici (center) calcolato come media di tutti i suoi punti e la distanza tra questi due punti (firstSegmentLength). La funzione Distance non fa altro che calcolare la distanza tra due punti servendosi del teorema di Pitagora.
Infine abbiamo Compare. Come si vede essa non fa altro che restituire il risultato del confronto tra il risultato della funzione GetAngle applicata ai due punti su cui eseguire un confronto. GetAngle è il cuore del metodo di ordinamento e in sostanza restituisce un valore compreso tra -2 e +2 proporzionale all'angolo compreso tra il punto corrente, il centro e il punto iniziale. Ordinando rispetto a questo valore verremo ad avere i punti disposti secondo un ordine crescente di angolo rispetto al primo punto (che è in realtà un riferimento arbitrario) e quindi in senso orario.
Vediamo cosa fa esattamente la funzione GetAngle:


public float GetAngle(Vector2 pt)
{
    // Teorema di Carnot:
    // a^2 = b^2 + c^2 - 2 * b * c * cos(alpha)
    //              b^2 + c^2 - a^2
    // cos(alpha) = ---------------
    //                 2 * b * c

    // Prepariamo le variabili che servono per il teorema
    float a, b, c;
    // Distanza del primo punto del poligono dal punto corrente
    a = Distance(firstPoint, pt);
    // Distanza del primo punto del poligono dal centro
    b = this.firstSegmentLength;
    // Distanza del punto corrente dal centro
    c = Distance(pt, center);

    // Applichiamo il teorema del coseno
    float cos =
        (float)(Math.Pow(b, 2) + Math.Pow(c, 2) - Math.Pow(a, 2)) /
        (2 * b * c);

    // cos è compreso tra -1 e +1, aggiungiamo 1 in modo che sia
    // compreso tra 0 e +2
    cos++;

    // Decidiamo il segno in base alla posizione rispetto al segmento
    // di riferimento, a seconda che siamo prima o dopo in senso orario.
    // Per fare questo vediamo se l'angolo compreso tra il punto corrente,
    // il primo punto del poligono e il centro è positivo o negativo, tramite
    // il prodotto vettore (cross-product)
    if (SortedConvexPolygonGame.CrossProduct(pt - firstPoint, center - firstPoint) > 0)
        cos *= -1;
    return cos;
}

Per prima cosa chiariamo che GetAngle non restituisce il valore di un angolo in gradi, radianti o altro, ma semplicemente un valore compreso tra -2 e +2 proporzionale all'angolo, calcolato come segue:

  • applicando il teorema di Carnot troviamo il valore del coseno dell'angolo compreso tra il punto corrente, il centro e il punto iniziale immaginando il triangolo formato dai tre punti, di cui conosciamo tutte le lunghezze;
  • il coseno dell'angolo è compreso tra -1 e +1, lo aumentiamo di uno per avere solo valori positivi, ottenendo un valore tra 0 e +2;
  • il coseno ci dà dei problemi poiché ad un valore di coseno lungo una circonferenza di 360° corrispondono due angoli, difatti la funzione inversa arcoseno è definita solamente tra 0 e 180°, questo per noi significa che un angolo di +30° avrà lo stesso coseno di -30° (o 330°); per aggirare questo problema verifichiamo se l'angolo tra il punto corrente, il punto iniziale e il centro è negativo o positivo e regoliamo il segno del risultato di conseguenza;

Il risultato, come detto, è un valore compreso tra -2 e +2 proporzionale all'angolo formato, ma non l'angolo esatto, poiché abbiamo evitato di utilizzare funzioni trigonometriche inverse inutilmente.

 

<< INDIETRO by VeNoM00