La linea di intersezione con AABB Rettangolo?

Preferibilmente senza l’utilizzo di alcun tipo di ciclo, in quanto questo sarà utilizzato in un gioco.

Auguro ad intersecare una linea con un rettangolo di dimensione arbitraria.
Ma desidero, inoltre, per il punto di intersezione[s] per essere restituito.

È possibile, ho fatto un po ‘ di ricerche su google, ma ancora non ho lavorato fuori.

La linea è definita utilizzando (x1,y1,x2,y2).
Il rettangolo ha due punti di troppo.

  • Inizia con un semplice problema. Sapete come intersezione di una linea infinita con un’altra linea infinita?
  • Non è che io pensi di imparare meglio il metodo Socratico; capisco che non tutti lo fanno. Piuttosto, sto cercando di misurare il vostro livello di conoscenza attuale. Se non sai come intersezione di due linee allora probabilmente stai andando ad avere per imparare che prima si tenta di intersezione geometrie più complesse.
  • Io fondamentalmente non sono d’accordo. A volte è meglio implementare qualcun altro la soluzione in codice, verificare che le opere e dimenticare tutto su di esso, di imparare la teoria dietro la soluzione e applicare voi stessi. Non imparare tanto, ma non tutti vogliono o necessità di imparare tutto.
InformationsquelleAutor Steffan Donal | 2010-09-19



One Reply
  1. 43

    Vorrei raccomandare semplicemente facendo un line-segmento-linea di intersezione del segmento di controllo su ogni segmento di linea (edge) che compongono il rettangolo. Qui è un segmento di linea di intersezione algoritmo di rilevamento che ho scritto tempo fa, dragato da uno dei miei vecchi XNA progetti:

    //a1 is line1 start, a2 is line1 end, b1 is line2 start, b2 is line2 end
    static bool Intersects(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersection)
    {
        intersection = Vector2.Zero;
    
        Vector2 b = a2 - a1;
        Vector2 d = b2 - b1;
        float bDotDPerp = b.X * d.Y - b.Y * d.X;
    
        //if b dot d == 0, it means the lines are parallel so have infinite intersection points
        if (bDotDPerp == 0)
            return false;
    
        Vector2 c = b1 - a1;
        float t = (c.X * d.Y - c.Y * d.X) / bDotDPerp;
        if (t < 0 || t > 1)
            return false;
    
        float u = (c.X * b.Y - c.Y * b.X) / bDotDPerp;
        if (u < 0 || u > 1)
            return false;
    
        intersection = a1 + t * b;
    
        return true;
    }

    Lascio inserimento di ogni bordo con il metodo di cui sopra e che raccoglie i risultati di un esercizio per il lettore 🙂


    Modifica 1 anno più tardi, ora sono andato all’università, e, fatto un corso di Grafica:

    Dare un’occhiata al Cohen–Sutherland algoritmo per fare questo in modo efficiente quando si dispone di un grande insieme di linee in cui la maggior parte non interseca il rettangolo. Esso utilizza un 9 segmento griglia e si svolge ogni punto finale della linea in una regione che ha detto griglia:

    La linea di intersezione con AABB Rettangolo?

    Utilizza questo possiamo dire se non ci saranno le intersezioni di linee:

    La linea di intersezione con AABB Rettangolo?

    Per esempio qui CD non interseca il rettangolo (mostrato in rosso nella prima immagine) sia come C e D sono in cima alla fila e nemmeno AB. Per quelli in cui la linea interseca il rettangolo che abbiamo per provare la linea-linea di intersezione.

    Che modo le sezioni sono numerate/etichettato ci permette di fare semplicemente x AND y != 0 (dove x e y sono le etichette delle sezioni per ogni linea dell’endpoint) per determinare se non ci sarà un incrocio.

    Utilizzando questo metodo significa che ci sono molti, molti meno linea-linea intersezioni che velocizza il tutto in maniera massiccia.

    • Che sarà abbastanza facile da fare. Vi ringrazio molto.
    • Nell’esempio di codice precedente, quelli sono in realtà prodotti trasversali, non dot prodotti.
    • Cohen–Sutherland algoritmo sembra essere di circa il ritaglio e la ricerca di intersezione piuttosto che c’è qualche incrocio – quindi sicuramente questo sarebbe più lento?
    • Hmm, la Cohen-Sutherland algoritmo assume un numero finito lo spazio è diviso in 9 pari regioni (o 27 in 3d). Cosa succede se il vostro spazio è infinito?
    • Direi che basta fare l’esterno di 8 (26) regioni infinito.
    • Che cosa succede se le linee sono infinite?
    • Poi hai a che fare con halfspaces e halfspace intersezioni.
    • Se ci pensate, un rettangolo è everything subtract [intersection of four halfspaces]. Se si rimuove uno di quei halfspaces (per ottenere linee infinite), è ancora un rettangolo?
    • (…Ho appena capito probabilmente significa che le LINEE sono infinite, piuttosto che il rettangolo linee. In questo caso, c’è sicuramente un modo per capire quale delle regioni esterne della linea di intersezione.)
    • Hai la mia upvote per la modifica

Lascia un commento