Come determinare se un punto si trova in un triangolo 2D?

C’è un modo semplice per determinare se un punto si trova all’interno di un triangolo? È 2D, non 3D.

In generale, l’algoritmo più semplice (e abbastanza ottimale) sta controllando su quale lato del semipiano creato dai bordi del punto.

Ecco alcune informazioni di alta qualità in questo argomento su GameDev , inclusi i problemi di prestazioni.

Ed ecco un codice per iniziare:

float sign (fPoint p1, fPoint p2, fPoint p3) { return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y); } bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3) { bool b1, b2, b3; b1 = sign(pt, v1, v2) < 0.0f; b2 = sign(pt, v2, v3) < 0.0f; b3 = sign(pt, v3, v1) < 0.0f; return ((b1 == b2) && (b2 == b3)); } 

Risolvi il seguente sistema di equazioni:

 p = p0 + (p1 - p0) * s + (p2 - p0) * t 

Il punto p trova all’interno del triangolo se 0 <= s <= 1 e 0 <= t <= 1 e s + t <= 1 .

s , t e 1 - s - t sono le coordinate baricentriche del punto p .

Sono d’accordo con Andreas Brinck , le coordinate baricentriche sono molto convenienti per questo compito. Nota che non è necessario risolvere ogni volta un sistema di equazioni: basta valutare la soluzione analitica. Utilizzando la notazione di Andreas , la soluzione è:

 s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py); t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py); 

dove Area è l’area (segnata) del triangolo:

 Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y); 

Basta valutare s , te 1-st . Il punto p è all’interno del triangolo se e solo se sono tutti positivi.

EDIT: si noti che l’espressione sopra per l’area presuppone che la numerazione del nodo triangular sia antioraria. Se la numerazione è in senso orario, questa espressione restituirà un’area negativa (ma con la magnitudine corretta). Il test stesso ( s>0 && t>0 && 1-st>0 ) non dipende dalla direzione della numerazione, tuttavia, poiché le espressioni sopra che sono moltiplicate per 1/(2*Area) cambiano anche il segno se l’orientamento del nodo triangular cambia.

EDIT 2: per un’efficienza computazionale ancora migliore, vedere il commento di coproc sotto (che indica che se l’orientamento dei nodes del triangolo (in senso orario o antiorario) è noto in anticipo, la divisione per 2*Area nelle espressioni per s e t possono essere evitati). Vedi anche il codice jsfiddle di Perro Azul nei commenti sotto la risposta di Andreas Brinck .

Ho scritto questo codice prima di un ultimo tentativo con Google e di aver trovato questa pagina, quindi ho pensato di condividerlo. È fondamentalmente una versione ottimizzata della risposta di Kisielewicz. Ho esaminato anche il metodo baricentrico ma, a giudicare dall’articolo di Wikipedia, ho difficoltà a vedere come è più efficiente (suppongo che esista un’equivalenza più profonda). Ad ogni modo, questo algoritmo ha il vantaggio di non usare la divisione; un potenziale problema è il comportamento del rilevamento dei bordi a seconda dell’orientamento.

 bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c) { int as_x = sx-ax; int as_y = sy-ay; bool s_ab = (bx-ax)*as_y-(by-ay)*as_x > 0; if((cx-ax)*as_y-(cy-ay)*as_x > 0 == s_ab) return false; if((cx-bx)*(sy-by)-(cy-by)*(sx-bx) > 0 != s_ab) return false; return true; } 

A parole, l’idea è questa: il punto è a sinistra oa destra di entrambe le linee AB e AC? Se è vero, non può essere dentro. Se falso, è almeno all’interno dei “coni” che soddisfano la condizione. Ora, poiché sappiamo che un punto all’interno di un trigono (triangolo) deve essere sullo stesso lato di AB di BC (e anche CA), controlliamo se sono diversi. Se lo fanno, s non può essere all’interno, altrimenti s deve essere dentro.

Alcune parole chiave nei calcoli sono i semipiani di linea e il determinante (2×2 cross product). Forse un modo più pedagogico è probabilmente quello di pensarlo come un punto all’interno se è dallo stesso lato (a sinistra oa destra) a ciascuna delle linee AB, BC e CA. Tuttavia, il modo sopra descritto sembrava essere più adatto ad alcune ottimizzazioni.

Versione C # del metodo baricentrico pubblicato da andreasdr e Perro Azul. Si noti che il calcolo dell’area può essere evitato se s e t hanno segni opposti. Ho verificato il comportamento corretto con un test unitario piuttosto accurato.

 public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2) { var s = p0.Y * p2.X - p0.X * p2.Y + (p2.Y - p0.Y) * pX + (p0.X - p2.X) * pY; var t = p0.X * p1.Y - p0.Y * p1.X + (p0.Y - p1.Y) * pX + (p1.X - p0.X) * pY; if ((s < 0) != (t < 0)) return false; var A = -p1.Y * p2.X + p0.Y * (p2.X - p1.X) + p0.X * (p1.Y - p2.Y) + p1.X * p2.Y; if (A < 0.0) { s = -s; t = -t; A = -A; } return s > 0 && t > 0 && (s + t) <= A; } 

[ modifica ]
accettato la modifica suggerita da @Pierre; vedere i commenti

Un modo semplice è:

trova i vettori che collegano il punto a ciascuno dei tre vertici del triangolo e sum gli angoli tra quei vettori. Se la sum degli angoli è 2 * pi, allora il punto è all’interno del triangolo.

Due buoni siti che spiegano le alternative sono:

blackpawn e wolfram

Versione Java del metodo baricentrico:

 class Triangle { Triangle(double x1, double y1, double x2, double y2, double x3, double y3) { this.x3 = x3; this.y3 = y3; y23 = y2 - y3; x32 = x3 - x2; y31 = y3 - y1; x13 = x1 - x3; det = y23 * x13 - x32 * y31; minD = Math.min(det, 0); maxD = Math.max(det, 0); } boolean contains(double x, double y) { double dx = x - x3; double dy = y - y3; double a = y23 * dx + x32 * dy; if (a < minD || a > maxD) return false; double b = y31 * dx + x13 * dy; if (b < minD || b > maxD) return false; double c = det - a - b; if (c < minD || c > maxD) return false; return true; } private final double x3, y3; private final double y23, x32, y31, x13; private final double det, minD, maxD; } 

Il codice sopra funzionerà in modo accurato con numeri interi, supponendo che non ci siano overflow. Funzionerà anche con triangoli in senso orario e antiorario. Non funzionerà con triangoli collineari (ma puoi verificarlo provando det == 0).

La versione baricentrica è la più veloce se testerai punti diversi con lo stesso triangolo.

La versione baricentrica non è simmetrica nei 3 punti triangolari, quindi è probabile che sia meno coerente della versione half-plane del bordo di Kornel Kisielewicz, a causa di errori di arrotondamento in virgola mobile.

Credito: ho realizzato il codice di cui sopra dall’articolo di Wikipedia sulle coordinate baricentriche.

Utilizzando la soluzione analitica alle coordinate baricentriche (indicate da Andreas Brinck ) e:

  • non distribuire la moltiplicazione sopra i termini tra parentesi
  • evitando di calcolare più volte gli stessi termini memorizzandoli
  • riduzione dei confronti (come sottolineato da coproc e Thomas Eding )

si può ridurre al minimo il numero di operazioni “costose”:

 function ptInTriangle(p, p0, p1, p2) { var dX = px-p2.x; var dY = py-p2.y; var dX21 = p2.x-p1.x; var dY12 = p1.y-p2.y; var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y); var s = dY12*dX + dX21*dY; var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY; if (D<0) return s<=0 && t<=0 && s+t>=D; return s>=0 && t>=0 && s+t<=D; } 

(il codice può essere incollato in Perro Azul jsfiddle )

Che porta a:

  • variabile "richiama": 30
  • archiviazione variabile: 7
  • aggiunte: 4
  • sottostrutture: 8
  • moltiplicazioni: 6
  • divisioni: nessuna
  • confronti: 4

Ciò è paragonabile alla soluzione di Kornel Kisielewicz (25 richiami, 1 stoccaggio, 15 sottrazioni, 6 moltiplicazioni, 5 confronti), e potrebbe essere ancora meglio se è necessario il rilevamento in senso orario / antiorario (che richiede 6 richiami, 1 aggiunta, 2 sottrazioni , 2 moltiplicazioni e 1 confronto in sé, usando il determinante della soluzione analitica, come sottolineato da rhgb ).

Quello che faccio è precalcolare le tre facce normali,

  • in 3D dal prodotto incrociato del vettore laterale e del vettore normale del viso.

  • in 2D semplicemente scambiando componenti e negando uno,

quindi dentro / fuori per ogni lato è quando un prodotto punto del lato normale e il vertice per puntare vettore, cambia segno. Ripeti per altri due (o più) lati.

Benefici:

  • molto è precalcolato così bene per test su più punti sullo stesso triangolo.

  • rifiuto precoce del caso comune di più all’esterno rispetto ai punti interni. (anche se la distribuzione del punto ponderata su un lato, può testare prima quella parte).

Ecco un’efficiente implementazione Python :

 def PointInsideTriangle2(pt,tri): '''checks if point pt(2) is inside triangle tri(3x2). @Developer''' a = 1/(-tri[1,1]*tri[2,0]+tri[0,1]*(-tri[1,0]+tri[2,0])+ \ tri[0,0]*(tri[1,1]-tri[2,1])+tri[1,0]*tri[2,1]) s = a*(tri[2,0]*tri[0,1]-tri[0,0]*tri[2,1]+(tri[2,1]-tri[0,1])*pt[0]+ \ (tri[0,0]-tri[2,0])*pt[1]) if s<0: return False else: t = a*(tri[0,0]*tri[1,1]-tri[1,0]*tri[0,1]+(tri[0,1]-tri[1,1])*pt[0]+ \ (tri[1,0]-tri[0,0])*pt[1]) return ((t>0) and (1-st>0)) 

e un esempio di output:

inserisci la descrizione dell'immagine qui

Se stai cercando velocità, ecco una procedura che potrebbe aiutarti.

Ordina i vertici del triangolo sulle loro coordinate. Nel peggiore dei casi, ci sono tre confronti. Sia Y0, Y1, Y2 i tre valori ordinati. Disegnando tre orizzontali attraverso di essi dividi il piano in due metà piani e due lastre. Sia Y l’ordinata del punto interrogativo.

 if Y < Y1 if Y <= Y0 -> the point lies in the upper half plane, outside the triangle; you are done else Y > Y0 -> the point lies in the upper slab else if Y >= Y2 -> the point lies in the lower half plane, outside the triangle; you are done else Y < Y2 -> the point lies in the lower slab 

Costa altri due confronti. Come puoi vedere, il rifiuto rapido si ottiene per punti al di fuori della “lastra delimitata”.

Facoltativamente, puoi fornire un test sulle ascisse per il rifiuto rapido a sinistra ea destra ( X <= X0' or X >= X2' ). Questo attiverà un test di bounding box veloce allo stesso tempo, ma dovrai anche ordinare le ascisse.

Alla fine dovrai calcolare il segno del punto dato rispetto ai due lati del triangolo che delimitano la lastra pertinente (superiore o inferiore). Il test ha la forma:

 ((X - Xi) * (Y - Yj) > (X - Xi) * (Y - Yj)) == ((X - Xi) * (Y - Yk) > (X - Xi) * (Y - Yk)) 

La discussione completa delle combinazioni i, j, k (ce ne sono sei, basate sul risultato del genere) è fuori dallo scopo di questa risposta e “lasciata come esercizio al lettore”; per efficienza, dovrebbero essere hard-coded.

Se pensate che questa soluzione sia complessa, osservate che essa implica principalmente confronti semplici (alcuni dei quali possono essere precalcolati), più 6 sottrazioni e 4 moltiplicazioni nel caso in cui il test del riquadro di delimitazione non funzioni. Quest’ultimo costo è difficile da battere poiché nel caso peggiore non è ansible evitare di confrontare il punto di prova con due lati (nessun metodo in altre risposte ha un costo inferiore, alcuni lo rendono peggiore, come 15 sottrazioni e 6 moltiplicazioni, a volte divisioni).

AGGIORNAMENTO: più veloce con una trasformazione di taglio

Come spiegato sopra, è ansible individuare rapidamente il punto all’interno di una delle quattro bande orizzontali delimitate dalle tre ordinate del vertice, utilizzando due confronti.

È ansible eseguire facoltativamente uno o due test X aggiuntivi per verificare l’insidialità nel riquadro di delimitazione (linee tratteggiate).

Quindi considera la trasformazione “a taglio” data da X'= X - m Y, Y' = Y , dove m è la pendenza DX/DY per il bordo più alto. Questa trasformazione renderà verticale questo lato del triangolo. E dal momento che sai da che parte del medio orizzontale sei, basta testare il segno rispetto a un singolo lato del triangolo.

inserisci la descrizione dell'immagine qui

Supponendo che tu abbia precalcolato la pendenza m , così come la X' per i vertici triangolari tranciati e i coefficienti delle equazioni dei lati come X = m Y + p , avrai bisogno nel caso peggiore

  • due confronti ordinati per la classificazione verticale;
  • opzionalmente uno o due confronti in ascissa per il rifiuto del riquadro di delimitazione;
  • calcolo di X' = X - m Y ;
  • uno o due confronti con le ascisse del triangolo tranciato;
  • test di un segno X >< m' Y + p' contro il lato pertinente del triangolo tranciato.

Se conosci le coordinate dei tre vertici e le coordinate del punto specifico, puoi ottenere l’area del triangolo completo. Successivamente, calcola l’area dei tre segmenti triangolari (un punto è il punto dato e gli altri due sono qualsiasi due vertici del triangolo). Quindi, otterrai l’area dei tre segmenti triangolari. Se la sum di queste aree è uguale all’area totale (che hai ottenuto in precedenza), il punto dovrebbe trovarsi all’interno del triangolo. Altrimenti, il punto non è all’interno del triangolo. Questo dovrebbe funzionare. Se ci sono problemi, fammi sapere. Grazie.

Altra funzione in python , più veloce del metodo dello sviluppatore (almeno per me) e ispirata alla soluzione di Cédric Dufour :

 def ptInTriang(p_test, p0, p1, p2): dX = p_test[0] - p0[0] dY = p_test[1] - p0[1] dX20 = p2[0] - p0[0] dY20 = p2[1] - p0[1] dX10 = p1[0] - p0[0] dY10 = p1[1] - p0[1] s_p = (dY20*dX) - (dX20*dY) t_p = (dX10*dY) - (dY10*dX) D = (dX10*dY20) - (dY10*dX20) if D > 0: return ( (s_p >= 0) and (t_p >= 0) and (s_p + t_p) <= D ) else: return ( (s_p <= 0) and (t_p <= 0) and (s_p + t_p) >= D ) 

Puoi testarlo con:

 X_size = 64 Y_size = 64 ax_x = np.arange(X_size).astype(np.float32) ax_y = np.arange(Y_size).astype(np.float32) coords=np.meshgrid(ax_x,ax_y) points_unif = (coords[0].reshape(X_size*Y_size,),coords[1].reshape(X_size*Y_size,)) p_test = np.array([0 , 0]) p0 = np.array([22 , 8]) p1 = np.array([12 , 55]) p2 = np.array([7 , 19]) fig = plt.figure(dpi=300) for i in range(0,X_size*Y_size): p_test[0] = points_unif[0][i] p_test[1] = points_unif[1][i] if ptInTriang(p_test, p0, p1, p2): plt.plot(p_test[0], p_test[1], '.g') else: plt.plot(p_test[0], p_test[1], '.r') 

Ci vuole molto per la trama, ma quella griglia viene testata in 0,0195319652557 secondi contro 0,0844349861145 secondi del codice dello sviluppatore .

Infine il commento del codice:

 # Using barycentric coordintes, any point inside can be described as: # X = p0.x * r + p1.x * s + p2.x * t # Y = p0.y * r + p1.y * s + p2.y * t # with: # r + s + t = 1 and 0 < r,s,t < 1 # then: r = 1 - s - t # and then: # X = p0.x * (1 - s - t) + p1.x * s + p2.x * t # Y = p0.y * (1 - s - t) + p1.y * s + p2.y * t # # X = p0.x + (p1.x-p0.x) * s + (p2.x-p0.x) * t # Y = p0.y + (p1.y-p0.y) * s + (p2.y-p0.y) * t # # X - p0.x = (p1.x-p0.x) * s + (p2.x-p0.x) * t # Y - p0.y = (p1.y-p0.y) * s + (p2.y-p0.y) * t # # we have to solve: # # [ X - p0.x ] = [(p1.x-p0.x) (p2.x-p0.x)] * [ s ] # [ Y - p0.Y ] [(p1.y-p0.y) (p2.y-p0.y)] [ t ] # # ---> b = A*x ; ---> x = A^-1 * b # # [ s ] = A^-1 * [ X - p0.x ] # [ t ] [ Y - p0.Y ] # # A^-1 = 1/D * adj(A) # # The adjugate of A: # # adj(A) = [(p2.y-p0.y) -(p2.x-p0.x)] # [-(p1.y-p0.y) (p1.x-p0.x)] # # The determinant of A: # # D = (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x) # # Then: # # s_p = { (p2.y-p0.y)*(X - p0.x) - (p2.x-p0.x)*(Y - p0.Y) } # t_p = { (p1.x-p0.x)*(Y - p0.Y) - (p1.y-p0.y)*(X - p0.x) } # # s = s_p / D # t = t_p / D # # Recovering r: # # r = 1 - (s_p + t_p)/D # # Since we only want to know if it is insidem not the barycentric coordinate: # # 0 < 1 - (s_p + t_p)/D < 1 # 0 < (s_p + t_p)/D < 1 # 0 < (s_p + t_p) < D # # The condition is: # if D > 0: # s_p > 0 and t_p > 0 and (s_p + t_p) < D # else: # s_p < 0 and t_p < 0 and (s_p + t_p) > D # # s_p = { dY20*dX - dX20*dY } # t_p = { dX10*dY - dY10*dX } # D = dX10*dY20 - dY10*dX20 

Ci sono condizioni fastidiose in cui un punto si trova esattamente sul bordo comune di due triangoli adiacenti. Il punto non può essere né in nessuno né in nessuno dei triangoli. È necessario un modo arbitrario ma coerente di assegnare il punto. Ad esempio, tracciare una linea orizzontale attraverso il punto. Se la linea si interseca con l’altro lato del triangolo a destra, il punto viene trattato come se fosse all’interno del triangolo. Se l’intersezione è a sinistra, il punto è all’esterno.

Se la linea su cui giace il punto è orizzontale, usa sopra / sotto.

Se il punto è sul vertice comune di più triangoli, usa il triangolo con il cui centro il punto forma l’angolo più piccolo.

Più divertimento: tre punti possono essere in linea retta (zero gradi), ad esempio (0,0) – (0,10) – (0,5). In un algoritmo di triangolazione, l'”orecchio” (0,10) deve essere tagliato, il “triangolo” generato è il caso degenerato di una linea retta.

Voglio solo usare una semplice matematica vettoriale per spiegare la soluzione di coordinate baricentriche che Andreas ha dato, sarà molto più facile da capire.

  1. L’area A è definita come qualsiasi vettore dato da s * v02 + t * v01, con condizione s> = 0 e t> = 0. Se qualsiasi punto all’interno del triangolo v0, v1, v2, deve essere all’interno dell’Area A.

inserisci la descrizione dell'immagine qui

  1. Se ulteriormente restringere s, e t appartiene a [0, 1]. Otteniamo Area B che contiene tutti i vettori di s * v02 + t * v01, con condizione s, t appartiene a [0, 1]. Vale la pena notare che la parte bassa dell’area B è lo specchio di Triangle v0, v1, v2. Il problema si presenta se possiamo dare certe condizioni di s, e t, per escludere ulteriormente la parte bassa dell’area B.

inserisci la descrizione dell'immagine qui

  1. Supponiamo di dare un valore s, e t sta cambiando in [0, 1]. Nella foto che segue, il punto p è sul bordo della v1v2. Tutti i vettori di s * v02 + t * v01 che si trovano lungo la linea del trattino per sum vettoriale semplice. A v1v2 e punto croce punto di incrocio p, abbiamo:

(1 s) | v0v2 | / | v0v2 | = tp | v0v1 | / | v0v1 |

otteniamo 1 – s = tp, quindi 1 = s + tp. Se c’è t> tp, che 1 = s + t dove si trova sulla linea del trattino singolo, il vettore è all’interno del triangolo.

Quindi se abbiamo dato una s in [0, 1], la t corrispondente deve soddisfare 1> = s + t, per il vettore all’interno del triangolo.

inserisci la descrizione dell'immagine qui

Quindi finalmente otteniamo v = s * v02 + t * v01, v è all’interno del triangolo con condizione s, t, s + t appartiene a [0, 1]. Poi traduci in punto, abbiamo

p – p0 = s * (p1 – p0) + t * (p2 – p0), con s, t, s + t in [0, 1]

che è la stessa soluzione di Andreas per risolvere il sistema di equazioni p = p0 + s * (p1 – p0) + t * (p2 – p0), con s, t, s + t appartengono a [0, 1].

Ecco una soluzione in python che è efficiente, documentata e contiene tre unittests. È di qualità professionale e pronto per essere inserito nel tuo progetto sotto forma di un modulo così com’è.

 import unittest ############################################################################### def point_in_triangle(point, triangle): """Returns True if the point is inside the triangle and returns False if it falls outside. - The argument *point* is a tuple with two elements containing the X,Y coordinates respectively. - The argument *triangle* is a tuple with three elements each element consisting of a tuple of X,Y coordinates. It works like this: Walk clockwise or counterclockwise around the triangle and project the point onto the segment we are crossing by using the dot product. Finally, check that the vector created is on the same side for each of the triangle's segments. """ # Unpack arguments x, y = point ax, ay = triangle[0] bx, by = triangle[1] cx, cy = triangle[2] # Segment A to B side_1 = (x - bx) * (ay - by) - (ax - bx) * (y - by) # Segment B to C side_2 = (x - cx) * (by - cy) - (bx - cx) * (y - cy) # Segment C to A side_3 = (x - ax) * (cy - ay) - (cx - ax) * (y - ay) # All the signs must be positive or all negative return (side_1 < 0.0) == (side_2 < 0.0) == (side_3 < 0.0) ############################################################################### class TestPointInTriangle(unittest.TestCase): triangle = ((22 , 8), (12 , 55), (7 , 19)) def test_inside(self): point = (15, 20) self.assertTrue(point_in_triangle(point, self.triangle)) def test_outside(self): point = (1, 7) self.assertFalse(point_in_triangle(point, self.triangle)) def test_border_case(self): """If the point is exactly on one of the triangle's edges, we consider it is inside.""" point = (7, 19) self.assertTrue(point_in_triangle(point, self.triangle)) ############################################################################### if __name__ == "__main__": suite = unittest.defaultTestLoader.loadTestsFromTestCase(TestPointInTriangle) unittest.TextTestRunner().run(suite) 

Esiste un test grafico facoltativo aggiuntivo per l'algoritmo sopra riportato per confermare la sua validità:

 import random from matplotlib import pyplot from triangle_test import point_in_triangle ############################################################################### # The area # size_x = 64 size_y = 64 # The triangle # triangle = ((22 , 8), (12 , 55), (7 , 19)) # Number of random points # count_points = 10000 # Prepare the figure # figure = pyplot.figure() axes = figure.add_subplot(111, aspect='equal') axes.set_title("Test the 'point_in_triangle' function") axes.set_xlim(0, size_x) axes.set_ylim(0, size_y) # Plot the triangle # from matplotlib.patches import Polygon axes.add_patch(Polygon(triangle, linewidth=1, edgecolor='k', facecolor='none')) # Plot the points # for i in range(count_points): x = random.uniform(0, size_x) y = random.uniform(0, size_y) if point_in_triangle((x,y), triangle): pyplot.plot(x, y, '.g') else: pyplot.plot(x, y, '.b') # Save it # figure.savefig("point_in_triangle.pdf") 

Produrre il seguente grafico:

Prova la funzione point_in_triangle

Avevo bisogno di un punto nel controllo del triangolo in “ambiente controllabile” quando sei assolutamente sicuro che i triangoli saranno in senso orario. Quindi, ho preso il jsfiddle di Perro Azul e l’ho modificato come suggerito da coproc per questi casi; ha anche rimosso le moltiplicazioni ridondanti di 0,5 e 2 perché si annullano a vicenda.

http://jsfiddle.net/dog_funtom/H7D7g/

Ecco il codice C # equivalente per Unity:

 public static bool IsPointInClockwiseTriangle(Vector2 p, Vector2 p0, Vector2 p1, Vector2 p2) { var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * px + (p0.x - p2.x) * py); var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * px + (p1.x - p0.x) * py); if (s <= 0 || t <= 0) return false; var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y); return (s + t) < A; } 

Presumibilmente codice ad alte prestazioni che ho adattato in JavaScript (articolo di seguito):

 function pointInTriangle (p, p0, p1, p2) { return (((p1.y - p0.y) * (px - p0.x) - (p1.x - p0.x) * (py - p0.y)) | ((p2.y - p1.y) * (px - p1.x) - (p2.x - p1.x) * (py - p1.y)) | ((p0.y - p2.y) * (px - p2.x) - (p0.x - p2.x) * (py - p2.y))) >= 0; } 

pointInTriangle (p, p0, p1, p2) – per i triangoli in senso antiorario

pointInTriangle (p, p0, p1, p2) – per i triangoli in senso orario

Guarda in jsFiddle (test delle prestazioni incluso), c’è anche il controllo degli avvolgimenti in una funzione separata http://jsfiddle.net/z7x0udf7/3/

Ispirato da questo: http://www.phatcode.net/articles.php?id=459

Il modo più semplice e funziona con tutti i tipi di triangoli è semplicemente determinare gli angoli degli angoli P punti A, B, C. Se uno qualsiasi degli angoli è più grande di 180.0, allora è all’esterno, se 180.0 allora è sulla circonferenza e se gli aco ti tradiscono e meno di 180.0 allora è all’interno. Dai un’occhiata a http: // matematica-fisica -psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

Sinceramente è semplice come la risposta di Simon P Steven, ma con questo approccio non hai un solido controllo sul fatto che tu voglia includere o meno i punti sui bordi del triangolo.

Il mio approccio è un po ‘diverso ma molto semplice. Considera il seguente triangolo;

inserisci la descrizione dell'immagine qui

Per avere il punto nel triangolo dobbiamo soddisfare 3 condizioni

  1. L’angolo ACE (verde) deve essere più piccolo dell’angolo ACB (rosso)
  2. L’angolo della BCE (blu) dovrebbe essere più piccolo dell’angolo ACB (rosso)
  3. Il punto E e il punto C hanno lo stesso segno quando i loro valori x e y sono applicati all’equazione di | AB | linea.

In questo metodo hai il pieno controllo per includere o escludere individualmente il punto sui bordi. Quindi puoi controllare se un punto è nel triangolo includendo solo | AC | bordo per esempio.

Quindi la mia soluzione in JavaScript sarebbe la seguente;

 function isInTriangle(t,p){ function isInBorder(a,b,c,p){ var m = (ay - by) / (ax - bx); // calculate the slope return Math.sign(py - m*px + m*ax - ay) === Math.sign(cy - m*cx + m*ax - ay); } function findAngle(a,b,c){ // calculate the C angle from 3 points. var ca = Math.hypot(cx-ax, cy-ay), // ca edge length cb = Math.hypot(cx-bx, cy-by), // cb edge length ab = Math.hypot(ax-bx, ay-by); // ab edge length return Math.acos((ca*ca + cb*cb - ab*ab) / (2*ca*cb)); // return the C angle } var pas = t.slice(1) .map(tp => findAngle(p,tp,t[0])), // find the angle between (p,t[0]) with (t[1],t[0]) & (t[2],t[0]) ta = findAngle(t[1],t[2],t[0]); return pas[0] < ta && pas[1] < ta && isInBorder(t[1],t[2],t[0],p); } var triangle = [{x:3, y:4},{x:10, y:8},{x:6, y:10}], point1 = {x:3, y:9}, point2 = {x:7, y:9}; console.log(isInTriangle(triangle,point1)); console.log(isInTriangle(triangle,point2)); 
 bool isInside( float x, float y, float x1, float y1, float x2, float y2, float x3, float y3 ) { float l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1), l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2), l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3); return (l1>0 && l2>0 && l3>0) || (l1<0 && l2<0 && l3<0); } 

Non può essere più efficiente di questo! Ogni lato di un triangolo può avere posizione e orientamento indipendenti, quindi tre calcoli: l1, l2 e l3 sono sicuramente necessari coinvolgendo 2 moltiplicazioni ciascuno. Una volta che l1, l2 e l3 sono noti, il risultato sono solo pochi confronti di base e operazioni booleane lontane.

Questo è il concetto più semplice per determinare se un punto si trova all’interno o all’esterno del triangolo o su un arm di un triangolo. La determinazione di un punto è all’interno di un tringle per determinanti

Il codice di lavoro più semplice: `

 #-*- coding: utf-8 -*- import numpy as np tri_points = [(1,1),(2,3),(3,1)] def pisinTri(point,tri_points): Dx , Dy = point A,B,C = tri_points Ax, Ay = A Bx, By = B Cx, Cy = C M1 = np.array([ [Dx - Bx, Dy - By, 0], [Ax - Bx, Ay - By, 0], [1 , 1 , 1] ]) M2 = np.array([ [Dx - Ax, Dy - Ay, 0], [Cx - Ax, Cy - Ay, 0], [1 , 1 , 1] ]) M3 = np.array([ [Dx - Cx, Dy - Cy, 0], [Bx - Cx, By - Cy, 0], [1 , 1 , 1] ]) M1 = np.linalg.det(M1) M2 = np.linalg.det(M2) M3 = np.linalg.det(M3) print(M1,M2,M3) if(M1 == 0 or M2 == 0 or M3 ==0): print("Point: ",point," lies on the arms of Triangle") elif((M1 > 0 and M2 > 0 and M3 > 0)or(M1 < 0 and M2 < 0 and M3 < 0)): #if products is non 0 check if all of their sign is same print("Point: ",point," lies inside the Triangle") else: print("Point: ",point," lies outside the Triangle") print("Vertices of Triangle: ",tri_points) points = [(0,0),(1,1),(2,3),(3,1),(2,2),(4,4),(1,0),(0,4)] for c in points: pisinTri(c,tri_points) 

`

 bool point2Dtriangle(double e,double f, double a,double b,double c, double g,double h,double i, double v, double w){ /* inputs: e=point.x, f=point.y a=triangle.Ax, b=triangle.Bx, c=triangle.Cx g=triangle.Ay, h=triangle.By, i=triangle.Cy */ v = 1 - (f * (b - c) + h * (c - e) + i * (e - b)) / (g * (b - c) + h * (c - a) + i * (a - b)); w = (f * (a - b) + g * (b - e) + h * (e - a)) / (g * (b - c) + h * (c - a) + i * (a - b)); if (*v > -0.0 && *v < 1.0000001 && *w > -0.0 && *w < *v) return true;//is inside else return false;//is outside return 0; } 

almost perfect Cartesian coordinates converted from barycentric are exported within *v (x) and *w (y) doubles. Both export doubles should have a * char before in every case, likely: *v and *w Code can be used for the other triangle of a quadrangle too. Hereby signed wrote only triangle abc from the clockwise abcd quad.

 A---B |..\\.o| |....\\.| D---C 

the o point is inside ABC triangle for testing with with second triangle call this function CDA direction, and results should be correct after *v=1-*v; and *w=1-*w; for the quadrangle

Since there’s no JS answer,
Clockwise & Counter-Clockwise solution:

 function triangleContains(ax, ay, bx, by, cx, cy, x, y) { let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) return det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 && det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 && det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0 } 

EDIT: there was a typo for det computation ( cy - ay instead of cx - ax ), this is fixed.

https://jsfiddle.net/jniac/rctb3gfL/ inserisci la descrizione dell'immagine qui

I’m using here the same method as described above: a point is inside ABC if he is respectively on the “same” side of each line AB, BC, CA. triangle inclusion example