Io ti consiglierei di cambiare la struttura dati, perchè se mantieni un semplice array di triangoli per trovare le adiacenze la complessità diventa lineare nel numero dei triangoli.
Io userei una struttura dati che ho visto in un corso universitario, che ti permette di fare diverse query in tempo lineare rispetto al numero di elementi coinvolti (decisamente meno del totale quindi):
Memorizzi due tipi di entità: vertici e triangoli.
Ogni vertice ha l'indice di uno dei triangoli incidenti e le coordinate.
Ogni triangolo ha il riferimento ai 3 vertici ed ai 3 triangoli adiacenti. Ordina i triangoli T1 T2 e T3 adiacenti in modo che T1 sia quello opposto al vertice V1, T2 opposto a V2, T3 opposto a V3.

Le relazioni che ti permettono di ottenere i vertici dal triangolo e i triangoli adiacenti dal triangolo sono memorizzate. Puoi inoltre recuperare in tempo lineare rispetto al numero di entità coinvolte sia i triangoli incidenti in un vertice, sia i vertici adiacenti ad un vertice.

Spero di aver capito più o meno quello che ti serviva e di averti dato uno spunto buono.


edit: dimenticavo, ricordati che devi anche avere una convenzione sull'ordine di salvataggio dei vertici (in senso orario, o antiorario).