Algoritmi - [Algoritmo] Algoritmo per il filtraggio di cordinate

CIAO

Ho costruito in vb.net un selecter, che si occupa per la selezione, deselezione e la verifica di cordinate selezionate

Ho implementato selecter combinando una griglia(X,Y) e List(point)

Devo creare una funzione che mi restituisce un array(vettori) di punti appartenenti a un rettangolo passato come argomento.
Es ho una griglia di 4x4 di punti selezionati o no
1001
0101
0010
1011
lista di punti selezionati:
[0,0]
[3,0]
[1,1]
[3,1]
[2,2]
[0,3]
[2,3]
[3,3]
(i punti 1 sono quelli selezionati e quelli 0 no)
Il problema è come selezionare i punti all' interno es del rettangolo [1,1] con dimensioni 2,2. Mi deve restituire [1,1] e [2,2].

Devo scegliere il miglior algoritmo (più veloce). 2 possibili algoritmi sono

FUNZIONE getPuntiSelezionatiInRettangolo(sel, rett) punto[]
   //Dichiara la lista dei punti
   punti[]
   //controlla ogni punto appartenente al rettangolo
   per x = rett.x a rett.x + rett.width - 1
      per y = rett.y a rett.y + rett.height - 1
         //verifica se è selezionato 
         se (sel.isSelected(x,y)) allora punti.aggiungi(new punto(x,y))
     fine per
   fine per
   restituisce punti
FINE FUNZIONE

Questo algoritmo funziona ciclando x e y e verificando ogni punto se è selezionato

Invece questo cicla la lista

FUNZIONE getPuntiSelezionatiInRettangolo(sel, rett) punto[]
   //Dichiara la lista dei punti
   punti[]
   //controlla ogni punto selezionato
   per ogni p in sel.getPuntiSelezionati()
      //verifica se appartiene al rettangolo
      se rett.intersecaPunto(p) allora punti.aggiungi(p)
   fine per 
   restituisci punti
FINE FUNZIONE

entrambi hanno i pro e contro:
PRO per il primo: il massimo tempo è rett.width*rett.height,però se non c'è nessun punto selezionato, la funzione in pratica fa pardere tempo
PRO per il secondo: se la lista è abbastanza corta(< rett.width*rett.height) può essere conveniente, ma se è lunghissima(per esempio 1000 item) può impiegarci un sacco di tempo per la ricerca.

L'idea che mi è appena venuto in mente è quello di verificare la dimensione della lista e l'area del rettangolo, scegliendo il primo algoritmo se l'area è minore, altrimenti l'altro

I punti sono dati tramite un input del tipo "mappa"

1001 
0101 
0010 
1011

oppure del tipo "elenco di coordinate"?

[0,0] 
[3,0] 
[1,1] 
[3,1] 
[2,2] 
[0,3] 
[2,3] 
[3,3]

Lo chiedo perché l'algoritmo 1 (quella che cicla su x e y) va bene se l'input è del tipo "mappa". Infatti conoscendo le coordinate del rettangolo vai subito a vedere i punti che ti interessano e ignori i restanti.

Invece se l'input è come "l' elenco di coordinate" conviene il secondo algoritmo in quanto in ogni caso dovrai leggere per forza tutto il file (altrimenti rischi di perderti qualche punto) e di verificare per ogni riga se il punto è compreso o meno nel rettangolo.

Spero di essere stato chiaro

Ho cercato soluzioni alternative ma non me ne sono venute in mente. Sono curioso di vedere le idee degli altri

entrambi. nella reale implementazione la mappa è di tipo linkedListNode(of point)()() che puntano alla lista linkedList(of point). Ho usate entrambe le strutture per migliore le operazioni.
Per es, per selezionare un punto, se uso la mappa è O(1), invece la lista O(n), altri es se uso getPuntiSelezionati() (nome nel codice GetSelections()), se uso la mappa è O(n), invece la lista O(1).

Quando uso select mi crea un nuovo nodo della linkedList e la aggiunge alla lista, poi copia il link alla mappa.