Come posso verificare se un punto è sotto una linea o no?Come posso verificare se un punto è sotto una linea o no?
ho i seguenti dati:
Line [ {x1,y1}, {x2,y2} ]
Points {xA,yA}, {xB,yB} ...
ho bisogno di scrivere un piccolo algoritmo in pitone per individuare i punti su un lato e l'altro lato della linea.
grazie
Si potrebbe provare a utilizzare un prodotto trasversale - http://en.wikipedia.org/wiki/Cross_product.
v1 = {x2-x1, y2-y1} # Vector 1
v2 = {x2-xA, y2-yA} # Vector 1
xp = v1.x*v2.y - v1.y*v2.x # Cross product
if xp > 0:
print 'on one side'
elif xp < 0:
print 'on the other'
else:
print 'on the same line!'
Avresti bisogno di calibrare ciò che ciascun lato è. Se vuoi che sia "sotto" o "sopra" devi assicurarti che i punti sulla linea siano ordinati orizzontalmente.
Non l'ho provato.
Modifica Inizialmente ho inserito la formula del punto. : o
Fortunatamente ho trovato Calculating a 2D Vector's Cross Product.
Cosa succede se xp è 0,00000000000000000000000000001 (probabilmente a causa della rappresentazione in virgola mobile)? Non è possibile che questo punto sia effettivamente in linea allora? (probabilmente vuoi confrontare un po 'di epsilon, piuttosto che 0.0) – PaulMcG
Buon punto! Anche se non so come si potrebbe trovare il valore epsilon più appropriato. – Edmund
cos (π/2) dovrebbe valutare a 0, ma 'math.cos (math.pi/2)' sul mio sistema fornisce '6.1230317691118863e-017', quindi indovinerei un epsilon in' 1e-15' o ' La gamma 1e-16' sarebbe giusta. (Inseriscilo nel proprio costante 'EPS' in modo da poterlo facilmente regolare regolando solo in un punto invece che ovunque si faccia confronti a virgola mobile.) – PaulMcG
Diciamo che hai dato 2 punti A, B e vuoi sapere in quale halfplane un terzo punto C si trova. I termini "sotto" e "sopra" come criteri sono molto vaghi, quindi è necessario un punto di riferimento, ad esempio l'origine. Assicurati che questo punto di riferimento non sia collineare con A e B.
Quello che hai ora è un triangolo (A, B, C). Utilizzando il determinante è possibile calcolare l'area firmata (see here o here). L'unica cosa interessante qui è ricordare il segno.
Passaggio successivo: per un dato punto D calcolare l'area segnata del triangolo (A, B, D). Se il risultato ha lo stesso segno dell'area del triangolo di riferimento -> C e D sono sullo stesso lato di (A, B). Se il segno differisce -> C e D si trovano sui lati opposti della linea. Se l'area di (A, B, D) è 0 allora A, B e D sono collineari. Nota: utilizzare il built-in Python cmp per confrontare le aree del triangolo.
Si potrebbe provare a utilizzare un prodotto incrociato, ma il trucco è come scegliere il punto per formare un vettore, qui scelgo il punto più vicino dai punti, suppongo di aver ottenuto il punto A (puoi fare abbastanza punti di loop per calcolare a distanza da loop point to Line):
v1 = {x2-x1, y2-y1} # Vector 1
v2 = {xA-x1, yA-y1} # Vector 2
cross_product = v1.x*v2.y - v1.y*v2.x
if cross_product > 0:
print 'pointA is on the counter-clockwise side of line'
elif xp < 0:
print 'pointA is on the clockwise side of line'
else:
print 'pointA is exactly on the line'
Per favore segna i tuoi compiti con il tag [homework]. –