¿Cómo puedo verificar si un punto está debajo de una línea o no?¿Cómo puedo verificar si un punto está debajo de una línea o no?
tengo los siguientes datos:
Line [ {x1,y1}, {x2,y2} ]
Points {xA,yA}, {xB,yB} ...
Tengo que escribir un pequeño algoritmo en Python para detectar puntos de un lado y del otro lado de la línea.
gracias
Usted podría tratar de usar un producto cruz - 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!'
Necesitará calibrar cada lado. Si desea que esté "debajo" o "arriba", debe asegurarse de que los puntos en la línea estén ordenados horizontalmente.
No he probado esto.
Editar Inicialmente puse la fórmula del producto punto. : o
Afortunadamente encontré Calculating a 2D Vector's Cross Product.
¿Qué sucede si xp es 0.00000000000000000000000000001 (posiblemente debido a la representación en coma flotante)? ¿No es posible que este punto esté realmente en la línea entonces? (Probablemente quiera comparar con algunos epsilon, en lugar de 0.0) – PaulMcG
¡Buen punto! Aunque no sé cómo encontrarías el valor épsilon más apropiado. – Edmund
cos (π/2) debería evaluar a 0, pero 'math.cos (math.pi/2)' en mi sistema da '6.1230317691118863e-017', así que adivinaría un épsilon en' 1e-15' o ' 1e-16' rango sería aproximadamente correcto. (Colóquelo en su propio 'EPS' constante para que pueda sintonizarlo fácilmente ajustando solo en un lugar, en lugar de realizar comparaciones en coma flotante). – PaulMcG
Digamos que has dado 2 puntos A, B y quieres saber en qué halfplane se encuentra un tercer punto C. Los términos "debajo" y "arriba" como criterios son muy vagos, por lo que necesita un punto de referencia, por ejemplo, el origen. Solo asegúrese de que este punto de referencia no sea colineal con A y B.
Lo que tiene ahora es un triángulo (A, B, C). Utilizando el determinante puede calcular el área firmada (see here o here). Lo único interesante aquí es recordar el letrero.
Siguiente paso: para un punto dado D calcule el área firmada del triángulo (A, B, D). Si el resultado tiene el mismo signo que el área de su triángulo de referencia -> C y D están en el mismo lado de (A, B). Si el signo difiere -> C y D se encuentran en lados opuestos de la línea. Si el área de (A, B, D) es 0, entonces A, B y D son colineales. Nota: utilice el built-in de Python cmp para comparar las áreas del triángulo.
Puedes intentar usar un producto cruzado, pero el truco es cómo elegir el punto para formar un vector, aquí elijo el punto más cercano de los puntos, supongo que tengo el punto A (puedes repetir puntos para calcular la distancia desde punto de bucle a línea):
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'
Por favor, marque su tarea con la etiqueta [tarea]. –