In questo tutorial ci occuperemo di poligoni convessi, ovvero con angoli interni inferiori ai 180°. Anche se probabilmente la cosa non è immediatamente evidente, essere in grado di maneggiare questo tipi di figure agevolmente è fondamentale nella creazione di un videogioco, in particolare per un'efficiente rilevamento delle collisioni. Infatti, nel metodo precedentemente presentato si effettuavano controlli di collisione anche su parti di intersezione dove non potevano certamente esserci, limitandosi a lavorare su rettangoli. In sostanza ci concentreremo su come sia possibile creare un ciclo che invece di muoversi lungo un rettangolo si muova lungo un arbitrario poligono, purché convesso. Se ci si sta chiedendo perché non trattiamo i poligoni concavi, non è per eccessiva difficoltà, ma semplicemente perché richiedono metodi diversi e più dispendiosi di risorse, che, ad esempio, per il rilevamento delle collisioni sarebbero sprecate.
Creeremo quindi un semplice gioco che disegna un poligono pixel per pixel delimitato da vertici forniti dall'utente tramite un click. Infine mostreremo anche una semplice ma efficiente funzione che permette di verificare se un punto, selezionato stavolta con il pulsante destro del mouse, è all'interno del poligono o meno.

MUOVERSI LUNGO L'AREA DI UN POLIGONO CONVESSO
Come creare un ciclo che si muova in maniera efficiente all'interno di un poligono.

Vediamo per prima cosa come prendiamo i vertici del poligono.

public class ConvexPolygonGame : Microsoft.Xna.Framework.Game
{

    // [...]

    // Memorizziamo lo stato del mouse di volta in volta per
    // poter rilevare l'evento di rilascio di un tasto
    private MouseState lastMouseState;
    // Lista dei vertici del poligono
    private List<Vector2> vertexes = new List<Vector2>();

    // [...]

    protected override void Update(GameTime gameTime)
    {
        // [...]
    
        MouseState ms = Mouse.GetState();
    
        // 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);
            }
        }
    
        // [...]
    
        // Memorizziamo lo stato del mouse corrente
        lastMouseState = ms;
        base.Update(gameTime);
    }

    // [...]
}

Nel metodo Update, come già fatto in precedenti articoli rileviamo quando viene rilasciato il pulsante del mouse in modo che non vengano generati un numero eccessivo di vertici dovuti alla accidentale pressione del tasto del mouse per un tempo troppo prolungato. Tutti i vertici sono memorizzati nella variabile vertexes. È importante notare capire subito che i vertici vanno in questo caso forniti dall'utente in senso orario, per convenzione; in un prossimo articolo ci occuperemo di vedere in dettaglio come è possibile ordinare dei vertici forniti in ordine casuale in senso orario, operazione non del tutto banale.
Vediamo ora cosa accade al metodo Draw:

protected override void Draw(GameTime gameTime)
{
    GraphicsDevice.Clear(Color.CornflowerBlue);

    spriteBatch.Begin();
    // Disegniamo il poligono
    DrawPolygon();
    // Disegnamo i vertici
    for (int CVertex = 0; CVertex < vertexes.Count; CVertex++)
    {
        spriteBatch.Draw(redSquare, new Rectangle((int)vertexes[CVertex].X, (int)vertexes[CVertex].Y, 5, 5), 
            Color.White);
    }

    // [...]

    base.Draw(gameTime);
}

Dapprima viene chiamato il metodo DrawPolygon, vero e proprio cuore del tutorial, e poi vengono disegnati tutti vertici come quadratini rossi di 5x5 pixel. Arriviamo dunque al metodo DrawPolygon, a cominciare dalle variabili che utilizza:

private void DrawPolygon()
{
    // Abbiamo bisogno di almeno tre vertici per poter disegnare
    // un poligono
    if (vertexes.Count < 3) return;

    // Lista dei lati
    LinkedList<Side> sides = new LinkedList<Side>();
    // Nodo della lista corrente su cui lavoreremo tra poco
    LinkedListNode<Side> currentNode = null;
    // Nodo della lista che delimita correntemente il poligono
    // a sinistra/destra
    LinkedListNode<Side> leftBoundNode = null;
    LinkedListNode<Side> rightBoundNode = null;
    // Coordinata Y del limite superiore del poligono.
    // Si tenga presente che l'asse Y procede dall'angolo
    // in alto a sinistra verso il basso.
    float topY = float.MaxValue;
    // Coordinata Y del limite inferiore del poligono
    float bottomY = 0;

    // [...]
}

Per prima cosa verifica se ci sono almeno tre vertici, se così non fosse non stiamo parlando di un poligono. Crea poi una LinkedList di strutture Side (ovvero lati, come vedremo tra poco) che conterrà tutti i lati del poligono collegati tra loro in senso orario. Ad esempio dato un elemento della LinkedList<Side> (quindi di tipo LinkedListNode<Side>) tramite le proprietà Next e Previous sarà possibile ottenere rispettivamente il lato successivo o precedente nell'ordinamento dato.
Vengono poi dichiarate alcune variabili di tipo LinkedListNode<Side> chiamati currentNode, leftBoundNode e rightBoundNode. Il primo ci servirà per muoverci lungo la lista di nodi, mentre per il secondo e il terzo dal loro nome si può già intuire in cose consiste il metodo che stiamo qui illustrando: si tratta in sostanza di scansionare tutta l'area del poligono in verticale (lungo l'asse delle Y), partendo dall'alto e scendendo man mano, muovendosi in orizzontale solamente entro i limiti (destro e sinistro) del poligono, determinati dai due lati (leftBoundNode e rightBoundNode appunto) che per un dato valore di Y delimitano il poligono a destra e a sinistra . Inizialmente questi lati saranno i due più in alto (a desta e a sinistra, ignorando i lati orizzontali) e man mano che si scenderà varieranno fino ad arrivare ai due più in basso.
Le variabili topY e bottomY saranno usate per determinare dove inizia e dove finisce il poligono lungo l'asse delle Y.

Nota: si ricordi che il sistema di coordinate dello schermo ha l'asse delle Y che parte dall'angolo in alto a sinistra e scende verso il basso. Pertanto, per evitare confusione non ci riferiremo alle coordinate Y in termini di valore minore o maggiore ma di limite superiore e o inferiore.

Vediamo dunque come viene popolata la linked-list, come vengono individuati i lati più in alto e i limiti inferiori e superiori del poligono:

// Creiamo una linked-list di lati, individuiamo i due lati più in alto
// che saranno i primi leftBoundNode e rightBoundNode e memorizziamo
// le coordinate Y degli estremi del poligono (topY e bottomY)
for (int C1 = 0; C1 < vertexes.Count; C1++)
{
    // Indica il vertice successivo, ovvero quello con indice 
    // successivo o il primo della lista se quello corrente è
    // l'ultimo, grazie all'operatore modulo.
    int nextIndex = (C1 + 1) % vertexes.Count;
    // Ignoriamo i lati orizzontali
    if (vertexes[C1].Y != vertexes[nextIndex].Y)
    {
        // Aggiungiamo in fondo alla linked-list il lato corrente
        // formato dal vertice corrente e dal successivo.
        currentNode = sides.AddLast(new Side(vertexes[C1], vertexes[nextIndex]));

        // Individuiamo il limite inferiore del poligono
        if (vertexes[C1].Y > bottomY) bottomY = vertexes[C1].Y;

        // Individuiamo il lato destro e sinistro più in alto
        // e al contempo troviamo la coordinata Y del limite
        // superiore del poligono

        // Individuiamo il lato che inizia più in alto
        // che sarà quindi il primo limite destro del poligono.
        if (currentNode.Value.Start <= topY)
        {
            topY = currentNode.Value.Start;
            rightBoundNode = currentNode;
        }
        // Individuiamo il lato che finisce più in alto
        // che sarà quindi il primo limite sinistro del poligono.
        if (currentNode.Value.End <= topY)
        {
            topY = currentNode.Value.End;
            leftBoundNode = currentNode;
        }
    }
}

Sostanzialmente si effettua un ciclo lungo tutti i vertici del poligono e per prima cosa si determina l'indice del vertice successivo, che è sempre quello con indice di valore maggiore di uno eccetto quando siamo giunti all'ultimo vertice: in tal caso prendiamo come vertice successivo il primo vertice. Subito poi imponiamo la condizione di ignorare tutti i lati orizzontali in quanto nella nostra scansione dall'alto al basso non danno alcun contributo.
Aggiungiamo dunque alla LinkedList il lato formato dai due vertici su cui stiamo lavorando, sotto forma di struttura Side. Vediamo come è definita:

// Struttura che contiene informazioni su un lato del poligono
public struct Side
{
    public float Start;
    public float End;
    public float XStep;
    public float StartX;

    // Costruiamo un lato a partire dai suoi vertici
    public Side(Vector2 pt1, Vector2 pt2)
    {
        // Memorizziamo dove inizia e dove finisce sull'asse Y
        Start = pt1.Y;
        End = pt2.Y;

        // Calcoliamo per ogni unità lungo le Y di cui ci muoviamo
        // quanto e in che direzione ci muoviamo sulle X (in sostanza
        // il coefficiente angolare della retta).
        XStep = (pt2.X - pt1.X) / (pt2.Y - pt1.Y);
        // Memorizziamo le coordinata X del punto più in alto, da cui
        // partiremo
        if (pt1.Y < pt2.Y) StartX = pt1.X; else StartX = pt2.X;
    }
}

La classe Side mantiene informazioni su un lato che ci saranno utili durante la scansione verticale:

• variabili Start ed End: range di coordinate Y lungo le quali si estende il lato, e quindi entro il quale il lato in questione andrà tenuto in considerazione prima di passare al successivo;
• variabile XStep: passo lungo l'asse X di cui spostarsi per ogni avanzamento lungo l'asse Y, è in sostanza il coefficiente angolare del lato;
• variabile StartX: coordinata X da cui inizia il segmento nel suo limite superiore, da cui partire per poi spostarsi di XStep ogni volta che si scende di un'unità lungo l'asse Y;

Torniamo ora al nostro ciclo. Dopo aver aggiunto alla lista il nuovo lato, cerchiamo con un semplice if il limite inferiore del poligono. Per individuare i lati più in alto a sinistra e a destra invece basta cercare quelli che, rispettivamente, finiscono e iniziano più in alto. Usiamo questo controllo anche per determinare il punto più alto del poligono.

Non ci resta ora che impostare quello che potremmo definire un "for poligonale":

// Cursori che useremo per muoverci all'interno del poligono
// sui due assi.
float CY = topY;
float CX = 0;
// Limiti destro e sinistro entro il quale il cursore
// lungo l'asse X dovrà muoversi.
float xRightLimit = rightBoundNode.Value.StartX;
float xLeftLimit = leftBoundNode.Value.StartX;

// Effettuiamo una scansione dal limite superiore
// a quello inferiore del poligono
while (CY < bottomY)
{
    // Posizioniamo il cursore X sul limite sinistro
    CX = xLeftLimit;
    // Ci muoviamo lungo l'asse X fino al limite destro
    while (CX <= xRightLimit)
    {
        // Disegniamo il pixel corrente
        spriteBatch.Draw(redSquare, new Rectangle((int)CX, (int)CY, 1, 1), Color.White);
        // Avanziamo lungo l'asse X
        CX += 1;
    }

    // Avanziamo lungo l'asse Y
    CY += 1;

    // Spostiamo i limiti sinistro e destro di un passo
    // a destra o a sinistra a seconda dell'inclinazione
    // del lato corrente.
    xLeftLimit += leftBoundNode.Value.XStep;
    xRightLimit += rightBoundNode.Value.XStep;

    // Se la coordinata Y a cui siamo giunti è al di fuori
    // del range di valori che copre il segmento destro
    // corrente passiamo al successivo
    if (CY > rightBoundNode.Value.End)
    {
        rightBoundNode = rightBoundNode.Next;
        // Se siamo giunti all'ultimo lato, passiamo al primo della lista
        if (rightBoundNode == null) rightBoundNode = sides.First;
        xRightLimit = rightBoundNode.Value.StartX;
    }
    // Come sopra, ma tutto è invertito per il lato sinistro
    if (CY > leftBoundNode.Value.Start)
    {
        leftBoundNode = leftBoundNode.Previous;
        if (leftBoundNode == null) leftBoundNode = sides.Last;
        xLeftLimit = leftBoundNode.Value.StartX;
    }

}

Una volta definiti due cursori, un per le coordinate X (variabile CX) e uno per le Y (variabile CY), dichiariamo due variabili che indicheranno i valori limite destro e sinistro entro cui si potrà muovere la coordinata X. Il cursore Y parte dal valore del limite superiore del poligono.
Abbiamo due cicli uno dentro l'altro, il primo while si muove lungo l'asse Y da topY fino a bottomY, quello più interno lungo l'asse X dal limite destro imposto dal lato a quello sinistro. È importante capire che i limiti destro e sinistro variano in due modi: il primo modo è quello che li fa spostare del valore XStep del lato a cui si riferiscono ogni volta che scendono di un'unità lungo le Y, il secondo è quando si cambia lato, ovvero quando il valore della coordinata Y è andato oltre il vertice inferiore del lato corrente e si passa quindi al lato immediatamente successivo. Grazie a questa tecnica è possibile passare per tutti e soli i punti all'interno del poligono.

ALGORITMO PER CONTROLLARE SE UN PUNTO È ALL'INTERNO DI UN POLIGONO
PLa funzione IsInsideConvexPolygon.

Vediamo ora la seconda funzionalità che presentiamo in questo tutorial: un semplice algoritmo per determinare se un punto selezionato dall'utente si trova all'interno o all'esterno del poligono, senza dover effettuare una scansione pixel per pixel.

public class ConvexPolygonGame : Microsoft.Xna.Framework.Game
{
    // [...]
    
    // Memorizziamo lo stato del mouse di volta in volta per
    // poter rilevare l'evento di rilascio di un tasto
    private MouseState lastMouseState;
    // Punto che conterrà le coordinate del punto che si
    // intende verificare se sia all'interno del poligono.
    // Per cambiarlo fare click destro nella finestra del gioco.
    private Vector2 checkPoint = new Vector2();
    // Memorizziamo se il checkPoint è all'interno del poligono
    private bool isCheckPointInside = false;

    protected override void Update(GameTime gameTime)
    {
        // [...]
        
        MouseState ms = Mouse.GetState();

        // [...]

        // Se nel precedente Update il tasto destro del mouse era premuto e ora non lo è più
        if (lastMouseState.RightButton == ButtonState.Pressed && ms.RightButton == ButtonState.Released)
        {
            // Aggiorniamo il checkPoint
            checkPoint = new Vector2(ms.X, ms.Y);
            // Verifichiamo se è all'interno del poligono o no
            isCheckPointInside = ConvexPolygonGame.IsInsideConvexPolygon(vertexes, checkPoint);
        }

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

    static bool IsInsideConvexPolygon(IList<Vector2> vertexes, Vector2 checkPoint) {
        // [...]
    }

    protected override void Draw(GameTime gameTime)
    {
        GraphicsDevice.Clear(Color.CornflowerBlue);

        spriteBatch.Begin();

        // [...]

        // Disegniamo il checkPoint
        spriteBatch.Draw(redSquare, new Rectangle((int)checkPoint.X, (int)checkPoint.Y, 5, 5), Color.White);
        spriteBatch.DrawString(arialFont, isCheckPointInside ? "in" : "out", 
            new Vector2(checkPoint.X, checkPoint.Y) + new Vector2(3, 3), Color.Green);
        spriteBatch.End();
        base.Draw(gameTime);
    }
}

Sostanzialmente abbiamo una variabile pointCheck che viene impostata nel metodo Update quando si clicca con il tasto destro del mouse; sempre in Update viene richiamata la funzione IsInsideConvexPolygon, il cui risultato viene salvato nella variabile isCheckPointInside che influirà sul metodo Draw per disegnare sotto il punto selezionato la scritta "in" o "out".
Vediamo il metodo IsInsideConvexPolygon:

static bool IsInsideConvexPolygon(IList<Vector2> vertexes, Vector2 checkPoint)
{
    // Variabile in cui, dopo il primo ciclo, memorizzeremo
    // se il punto si trova a destra o a sinsitra del lato
    // così da poter verificare che sia così per ogni lato.
    sbyte sign = 0;
    // Cicliamo lungo tutti i vertici
    for (int C1 = 0; C1 < vertexes.Count; C1++)
    {
        // Prendiamo il punto corrente e il successivo
        Vector2 pt1 = vertexes[C1];
        Vector2 pt2 = vertexes[(C1 + 1) % vertexes.Count];
        // Sottraiamo (traslazione) al checkPoint e 
        // e ad un vertice del lato corrente l'altro vertice
        // così da poter calcolare il segno dell'angolo 
        // compreso tra il lato e il checkPoint tramite il
        // prodotto vettore (cross-product)
        Vector2 translatedCheckPoint = checkPoint - pt1;
        pt2 -= pt1;
        // Prendiamo il segno dell'angolo ottenuto tramite il 
        // prodotto vettore.
        sbyte angleSign = (sbyte)Math.Sign(CrossProduct(pt2, translatedCheckPoint));

        // Se è il primo ciclo
        if (sign == 0)
        {
            sign = angleSign;
        }
        else if (angleSign != sign)
        {
            // Se non è il primo ciclo e il segno dell'angolo
            // è differente dagli altri, siamo fuori dal poligono
            return false;
        }
    }
    // Abbiamo controllato tutti i lati, siamo all'interno del poligono
    return true;
}

L'algoritmo funziona come segue: dato un punto per controllare se è all'interno di un poligono convesso basta percorrere tutti i lati del poligono in senso orario o anti-orario e verificare che stia, rispettivamente, sempre a destra o a sinistra di ciascuno di essi. Se così non fosse, il punto è esterno.
Muovendoci di coppia di vertici in coppia di vertici, chiamiamo pt1 il primo vertice del lato e pt2 il secondo; quindi sottraiamo pt1 (effettuando dunque una traslazione) a pt2 e al punto che vogliamo controllare, e verifichiamo se l'angolo che si forma tra questi due punti traslati è positivo o negativo (tramite il prodotto vettore o cross-product). Alla prima iterazione del ciclo memorizziamo se il punto sta sopra o sotto nella variabile sign, mentre nei successivi ci assicuriamo che la sua posizione rispetto al lato corrente sia uguale a quella rispetto al primo, in sostanza che stia sempre sopra o sempre sotto. Se così non fosse il punto è esterno al poligono.