Qualsiasi buona struttura dati per eseguire operazioni di ricerca e modifica efficienti su quali sono le forme che contengono la posizione corrente del cursore

0

Penso di trovarmi di fronte a un problema piuttosto comune, ma non ricordo quale sia la soluzione più adatta.

Mettiamola così: posso, in una determinata, determinata lingua, ottenere alcuni eventi ogni volta che l'utente muove il mouse. Pertanto ottengo la posizione dell'attuale posizione del cursore in un sistema basato su coordinate assolute.

Considerando ora che questo sistema è anche in grado di contenere fino a migliaia di migliaia di oggetti di forma (con un certo punto e dimensione di posizione). In una prima approssimativa approssimazione, possiamo considerarli come i relativi riquadri di delimitazione al fine di rendere l'operazione di ricerca e la classificazione un po 'più semplici, aggiungiamo anche un'altra semplificazione omettendo il fatto che le forme possono sovrapporsi l'una con l'altra.

Quali possono essere le migliori strutture dati per recuperare le forme sotto la posizione del cursore e consentire le relative operazioni di inserimento / cancellazione / modifica veloci?

Grazie,

ps: stavo pensando ad una sorta di alberi ordinati ma penso che siano piuttosto impegnativi quando si tratta di mantenere il loro ordinamento interno.

Una curiosità aggiuntiva: come funziona in Winforms? Voglio dire che la classe Control in .NET Framework è correlata all'HWANDLE sottostante in Windows e in grado di generare eventi quando il cursore sta entrando o esce da un Control. Non penso davvero che ci sia un thread assegnato per eseguire alcuni hit test fittizi ... e attivare gli eventi correlati.

    
posta Ehouarn Perret 26.03.2015 - 07:00
fonte

1 risposta

1

Se lo spazio non è preoccupante e la tua applicazione può permettersi di utilizzare tutto lo spazio che vuoi, sto pensando alla struttura a 3 dimensioni (o per essere più precisi, array di liste bidimensionali) La matrice bidimensionale rappresenterà lo schermo. Ogni pixel è un elemento dell'array. Ogni posizione nell'array contiene un puntatore a un elenco di identificatore di forma

es. ci sono 2 forme con id 4, 5 in posizione {10, 12}, quindi l'elemento {10, 12} della matrice bidimensionale contiene un elenco di 2 elementi (4 e 5). Si noti che id forma è un numero che identifica in modo univoco quell'istanza di forma. Anche se 2 forme sono entrambe quadrate, avranno un ID di forma diverso

  • Per trovare in una posizione specifica del mouse, quali forme sono presenti, è sufficiente una sola ricerca di array + elenco di viaggi per ottenere tutte le forme in quella posizione
  • Per inserire: dipenderà da quanto è grande la forma, dovrà passare attraverso tutti i pixel nella forma, aggiungere quell'id della forma nella struttura
  • Per eliminare: per eliminare più velocemente, penso che possa mantenere una ricerca che abbia una chiave sia id di forma, il valore è la posizione di un pixel all'interno di quella forma. quando si desidera eliminare la forma, cercare la posizione del pixel in base all'id della forma, quindi utilizzare l'algoritmo di riempimento integrale per rimuovere l'ID della forma dalla struttura

Spero di descriverlo bene, ecco un esempio della matrice 3x3. Ci sono 2 quadrati di dimensione 2x2 nella matrice con ID 1, 2. Questi 2 quadrati si sovrappongono nel mezzo della matrice

[1] - [1] - []

[1] - [1,2] - [2]

[] - [2] - [2]

    
risposta data 26.03.2015 - 08:17
fonte

Leggi altre domande sui tag