Punti di conteggio all'interno di triangolo veloce

Question

Ho bisogno di trovare il numero di punti in una lista data che si trovano all'interno di un triangolo. Il problema qui è che possono esserci fino a un milione di punti.

Ho provato un approccio semplice: se l'area del triangolo è uguale alla somma delle aree di 3 triangoli formati prendendo 2 dei punti del triangolo alla volta e il punto da controllare, è all'interno. Questo non ha errori di precisione, dal momento che non divido per due per trovare l'area.

Ma ho bisogno di qualcosa più veloce. L'obiettivo è la velocità. Può essere reso più veloce da una sorta di pre-elaborazione, ignorando alcuni punti in base ad alcuni criteri o qualcosa di simile?

MODIFICA: Hai dimenticato di aggiungere un dettaglio critico. I punti dati una volta, sono corretti. Quindi i punti sono statici e devono essere controllati per un massimo di un milione di triangoli ...

MODIFICA 2: Si scopre che un buon modo (forse troppo ottimale) per farlo era usare uno sweep di linea. Comunque grazie per le tue risposte!

Answer 1

In base alla geometria computazionale, il modo più rapido per eseguire questa operazione è la trasformazione di coordinate baricentriche. In un caso in cui hai un triangolo fisso e molti punti di prova, allora questo approccio sarà particolarmente veloce, perché una volta calcolate le coordinate baricentriche dei 3 punti del triangolo hai fatto la maggior parte del lavoro. Ecco l'algoritmo completo in cui sono ABC il triangolo e P è il punto in prova:

// Compute vectors   
v0 = C - A 
v1 = B - A 
v2 = P - A 

// Compute dot products 
dot00 = dot(v0, v0) 
dot01 = dot(v0, v1) 
dot02 = dot(v0, v2) 
dot11 = dot(v1, v1) 
dot12 = dot(v1, v2) 

// Compute barycentric coordinates 
invDenom = 1/(dot00 * dot11 - dot01 * dot01) 
u = (dot11 * dot02 - dot01 * dot12) * invDenom 
v = (dot00 * dot12 - dot01 * dot02) * invDenom 

// Check if point is in triangle 
return (u >= 0) && (v >= 0) && (u + v < 1) 

qui le coordinate baricentriche vengono calcolate rispetto ad A, ma B o C avrebbe funzionato pure.

Per testare punti aggiuntivi è necessario ricalcolare solo v2, dot02, dot12, uev. Le quantità come invDenom rimangono invariate.

Answer 2

Il prefiltro semplice serve per eliminare tutti i punti le cui coordinate si trovano ovviamente al di fuori dei limiti degli angoli del triangolo. per esempio.

a 
+ 
|\ 
| \ b 
|c \ 
+---+ d 

A e D sono ovviamente all'esterno. Il coordame Y è molto al di sopra del massimo Y del triangolo e D è ovviamente oltre il massimo X del triangolo.

Questo lascia B e C per il test.

Answer 3

Un punto si trova all'interno di un triangolo se si trova a sinistra (destra) di ogni lato. Puoi calcolare i prodotti trasversali (in realtà solo un componente di esso) di un vettore costituito da un punto da testare e uno dei vertici triangolari e i 3 vettori che si trovano sui lati del triangolo (tutti in senso orario o tutti in senso antiorario). Verifica se il componente calcolato di tutti e 3 ha lo stesso segno (tutti 3 negativi o tutti 3 positivi). Questo ti dirà il punto è. Veloce, nessun problema con precisione, almeno, se usi gli interi per l'attività.

È possibile interrompere ulteriori calcoli per ogni punto una volta che si vede sul lato sbagliato di uno dei lati del triangolo.

codice di esempio in C:

#include <stdio.h> 

#define SCREEN_HEIGHT 22 
#define SCREEN_WIDTH 78 

// Simulated frame buffer 
char Screen[SCREEN_HEIGHT][SCREEN_WIDTH]; 

void SetPixel(int x, int y, char color) 
{ 
    if ((x < 0) || (x >= SCREEN_WIDTH) || 
     (y < 0) || (y >= SCREEN_HEIGHT)) 
    return; 

    Screen[y][x] = color; 
} 

void Visualize(void) 
{ 
    int x, y; 

    for (y = 0; y < SCREEN_HEIGHT; y++) 
    { 
    for (x = 0; x < SCREEN_WIDTH; x++) 
     printf("%c", Screen[y][x]); 

    printf("\n"); 
    } 
} 

typedef struct 
{ 
    int x, y; 
} Point2D; 

int main(void) 
{ 
    // triangle vertices 
    Point2D vx0 = { SCREEN_WIDTH/2, SCREEN_HEIGHT/7 }; 
    Point2D vx1 = { SCREEN_WIDTH * 6/7, SCREEN_HEIGHT * 2/3 }; 
    Point2D vx2 = { SCREEN_WIDTH/7, SCREEN_HEIGHT * 6/7 }; 
    // vectors lying on triangle sides 
    Point2D v0, v1, v2; 
    // current point coordinates 
    int x, y; 

    // calculate side vectors 

    v0.x = vx1.x - vx0.x; 
    v0.y = vx1.y - vx0.y; 

    v1.x = vx2.x - vx1.x; 
    v1.y = vx2.y - vx1.y; 

    v2.x = vx0.x - vx2.x; 
    v2.y = vx0.y - vx2.y; 

    // process all points 

    for (y = 0; y < SCREEN_HEIGHT; y++) 
    for (x = 0; x < SCREEN_WIDTH; x++) 
    { 
     int z1 = (x - vx0.x) * v0.y - (y - vx0.y) * v0.x; 
     int z2 = (x - vx1.x) * v1.y - (y - vx1.y) * v1.x; 
     int z3 = (x - vx2.x) * v2.y - (y - vx2.y) * v2.x; 

     if ((z1 * z2 > 0) && (z1 * z3 > 0)) 
     SetPixel(x, y, '+'); // point is to the right (left) of all vectors 
     else 
     SetPixel(x, y, '-'); 
    } 

    // draw triangle vertices 

    SetPixel(vx0.x, vx0.y, '0'); 
    SetPixel(vx1.x, vx1.y, '1'); 
    SetPixel(vx2.x, vx2.y, '2'); 

    // visualize the result 

    Visualize(); 

    return 0; 
} 

uscita (ideone):

------------------------------------------------------------------------------ 
------------------------------------------------------------------------------ 
------------------------------------------------------------------------------ 
---------------------------------------0-------------------------------------- 
--------------------------------------++++------------------------------------ 
------------------------------------++++++++---------------------------------- 
----------------------------------+++++++++++++------------------------------- 
--------------------------------+++++++++++++++++----------------------------- 
------------------------------++++++++++++++++++++++-------------------------- 
----------------------------++++++++++++++++++++++++++------------------------ 
--------------------------+++++++++++++++++++++++++++++++--------------------- 
-------------------------++++++++++++++++++++++++++++++++++------------------- 
-----------------------+++++++++++++++++++++++++++++++++++++++---------------- 
---------------------+++++++++++++++++++++++++++++++++++++++++++-------------- 
-------------------+++++++++++++++++++++++++++++++++++++++++++++++1----------- 
-----------------++++++++++++++++++++++++++++++++++++------------------------- 
---------------++++++++++++++++++++++++--------------------------------------- 
-------------++++++++++++----------------------------------------------------- 
-----------2------------------------------------------------------------------ 
------------------------------------------------------------------------------ 
------------------------------------------------------------------------------ 
------------------------------------------------------------------------------ 

Answer 4

È inoltre possibile utilizzare un quadtree per accelerare il calcolo.

Calcola un quadruplo per il triangolo (fermandosi a risoluzione arbitraria) e per ciascun nodo (quadrato), memorizza una bandiera che indica se il nodo è completamente all'interno, completamente all'esterno o parzialmente all'interno del triangolo. Un nodo parzialmente all'interno del triangolo può potenzialmente avere figli (a seconda della profondità)

Per ogni punto, attraversare il quadrilatero. Se visitiamo un nodo completamente esterno o interno al triangolo, siamo pronti. Se non siamo sicuri se siamo nel triangolo (il nodo è parzialmente all'interno del triangolo) e il nodo corrente ha figli, testiamo i suoi bambini in modo ricorsivo. Se colpiamo un nodo foglia che è parzialmente all'interno del triangolo, fai un punto analitico - controllo di contenimento del triangolo.

Answer 5

Prima di tutto, ordina i punti indicati nell'elenco con le coordinate y e in coordinate y coordinate x. Ora inizia dal basso della tua coordinata y più bassa (pensa a una linea parallela all'asse x) e spostalo verso l'alto di 1 unità hai anche l'equazione dei segmenti di linea formati dai punti finali del tuo triangolo. Eliminate ora alcuni punti ovvi come suggerito da Marc B. E per il resto dei punti che hanno la stessa coordinata della vostra linea parallela immaginaria verso l'asse x che si muove verso l'alto di un gradino unitario ogni volta, controllate se sono all'interno o all'esterno del triangolo mettendo nelle equazioni della linea che unisce i punti finali del triangolo. Puoi facilmente fare in modo che questi punti abbiano le stesse coordinate y eseguendo la ricerca binaria nell'elenco delle coordinate che hai ordinato in precedenza in base alle coordinate y. In questo modo il tuo algo prende O (Yrangeoftriangle * nlogn) per ogni query. INOLTRE La domanda è abbastanza ben fatta su Codechef a lungo.