Algoritmo di rilevamento intersezione linea

Question

Algoritmo di rilevamento intersezione linea

#1 da (1 voti)
#2 da (1 voti)

2

Sto provando a rilevare se una linea disegnata dall'utente si interseca. Sto usando un algoritmo di rilevamento di intersezioni di linee che attraversa ogni waypoint della linea e controlla se si interseca con qualsiasi altro punto della linea.

Questo è un metodo costoso e ha iniziato a produrre problemi di prestazioni. Quale sarebbe l'algoritmo consigliato per questo problema? Esiste un esempio di codice?

La linea è rappresentata con wayPoints che sono le coordinate che sono state raccolte dallo spostamento degli utenti sullo schermo.

Grazie mille per aver letto fin qui! Tutto l'aiuto apprezzato!

    for i in 1 ..<(wayPoints.count-1) {
            for j in 0 ..< i-1 {
                   if let intersection = intersectionBetweenSegments(wayPoints[i], wayPoints[i+1], wayPoints[j], wayPoints[j+1]){
  ...}
   }
  }

    func intersectionBetweenSegments(p0: CGPoint, _ p1: CGPoint, _ p2: CGPoint, _ p3: CGPoint) -> CGPoint? {
        var denominator = (p3.y - p2.y) * (p1.x - p0.x) - (p3.x - p2.x) * (p1.y - p0.y)
        var ua = (p3.x - p2.x) * (p0.y - p2.y) - (p3.y - p2.y) * (p0.x - p2.x)
        var ub = (p1.x - p0.x) * (p0.y - p2.y) - (p1.y - p0.y) * (p0.x - p2.x)
        if (denominator < 0) {
            ua = -ua; ub = -ub; denominator = -denominator
        }

        if ua >= 0.0 && ua <= denominator && ub >= 0.0 && ub <= denominator && denominator != 0 {
            return CGPoint(x: p0.x + ua / denominator * (p1.x - p0.x), y: p0.y + ua / denominator * (p1.y - p0.y))
        }

        return nil
    }

game-development performance algorithms math

posta user594883 06.03.2015 - 06:03

fonte

2 risposte

Leggi altre domande sui tag game-development performance algorithms math

Come gestire il codice legacy nelle filiali? Tecnica per sincronizzare i codici di errore in un'API dello stesso progetto

score 1 · Answer 1

This is a costly method and has started to produce performance problems. What would be the recommended algorithm for this problem? Is there a code example of it?

Dipende molto da come rappresenti la linea stessa. Sembra che tu usi una linea spezzata, cioè una giustapposizione di linee rette.

La prima idea che mi viene in mente è fare un semplice controllo della regione. Puoi impacchettare ogni linea in un piccolo rettangolo (il suo rettangolo di selezione) ed è molto facile controllare se due caselle di delimitazione si sovrappongono o no - puoi farlo facendo alcune sottrazioni, che è molto più economico del calcolo di un determinante! Se il controllo della regione fallisce, le linee certamente non si incrociano, quindi non è necessario calcolare il determinante.

Con questo dovresti passare dalla complessità (n4) a (n2) dove n è il numero di piccole linee rette nella tua linea.

Se ciò non è sufficiente, una seconda tecnica comune è quella di dividere la tela in regioni e rappresentare questa regione come un albero binario. Si inizia con la tela intera, quindi si taglia a metà e poi si suddivide ogni metà in due, ancora e ancora, finché non si raggiunge un numero di spaccature che si sceglie in anticipo. (È possibile eseguire test empirici per determinare un valore adatto ai dati.) Quindi è possibile collegare ciascun segmento di linea a un'area in cui si adatta il riquadro di delimitazione - Tipicamente una foglia, ma può essere un nodo di livello superiore se un segmento di linea taglia un confine regionale Una volta impacchettato ogni segmento di linea nell'albero delle regioni, è facile recuperare vicini di una linea di segmento, dove può avvenire l'intersezione.

score 1 · Answer 2

Questo è in origine un commento alla ricerca di chiarimenti, ma è troppo lungo per adattarsi. Così ho postato ogni domanda qui, insieme con le mie risposte "what-if" per ogni domanda in base alle possibili risposte.

Prima di chiedere chiarimenti, tutti dovrebbero vedere che l'attuale implementazione ha una complessità temporale quadratica nel numero di waypoint. La notazione è O(N^2) .

Per dirla semplicemente, se il numero di waypoint è raddoppiato (aumentato a due volte), il tempo di esecuzione sarà approssimativamente quadruplicato (aumentato a quattro volte).

(1) Qual è il numero tipico di waypoint che devi gestire? Se non esiste un numero tipico, indicare il numero massimo possibile di waypoint che il proprio codice deve supportare.

Ad esempio, se si scopre che il problema di prestazioni non si verifica quando N (numero di waypoint) è inferiore a diverse centinaia, è possibile imporre una restrizione software che il movimento del mouse non può essere più lungo di quel numero di pixel. Se questo è accettabile o meno dipende dallo scopo del tuo software.

(2) Ti è permesso usare tecniche di semplificazione della linea per ridurre il numero di waypoint prima di verificare le intersezioni?

La tecnica di semplificazione della linea può ridurre il numero di waypoint di dieci volte (un decimo) o più (meno), quando il movimento del mouse viene utilizzato come input. L'utente dovrà spostare il mouse molto freneticamente per far fallire questa riduzione.

(3) Sai come implementare e utilizzare QuadTree da solo?

Un quadrilatero consente una query O(log N) caso medio in una raccolta (struttura ad albero) di riquadri di delimitazione che si sovrappongono alla casella di delimitazione della query. Per trovare tutti i riquadri di delimitazione sovrapposti a coppie, prima si aggiungono tutti i riquadri di delimitazione e quindi si esegue una query su ciascun riquadro di delimitazione. Questo dà un totale che è in media caso O(N log N) , che è migliore dell'implementazione originale che è O(N^2) .

(4) Qual è la larghezza e l'altezza dell'area di movimento, misurata in pixel, che devi supportare?

Se l'area di movimento totale (in pixel quadrati, ovvero il prodotto di larghezza e altezza) è inferiore a qualche milione, e se è consentito allocare un array che può contenere alcuni milioni di byte (o bit) solo bisogno che ogni elemento sia vero o falso), quindi si può allocare una tale matrice per agire come una bitmap (letteralmente una mappa di bit).

La bitmap verrà inizializzata con false. Quindi, mentre l'utente "dipinge" con il movimento del mouse, i pixel corrispondenti nella bitmap verranno impostati su true.

Avvertenza Si noti che se la traccia pixel dell'utente è di un solo pixel (1 per 1) di larghezza, si verificherà il seguente caso limite:

Supponiamo che la traccia vada da (10, 10) a (11, 11) . Più avanti nella traccia, attraversa quel segmento passando (10, 11) a (11, 10) . Poiché i pixel stessi non si sovrappongono, questo schema basato su bitmap non riuscirà a rilevare un'intersezione di questo tipo.

La soluzione al caveat è che si deve controllare un quartiere 3 per 3 per i pixel che sono stati dipinti prima. Mentre lo fai, devi anche ricordare di ignorare i pixel che sono appena stati dipinti di recente. È possibile che sia necessario utilizzare un byte per pixel (anziché un bit per pixel) per archiviare informazioni aggiuntive per aiutare a risolvere questo avvertimento.