Encuentre si el punto se encuentra en el segmento de línea

Tengo un segmento de línea definido por dos puntos A (x1, y1, z1) y B (x2, y2, z2) y el punto p (x, y, z). ¿Cómo puedo verificar si el punto está en el segmento de línea?

Si el punto está en la línea, entonces:

(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1) = (z - z1) / (z2 - z1) 

Calcule los tres valores, y si son los mismos (hasta cierto grado de tolerancia), su punto está en la línea.

Para comprobar si el punto está en el segmento, no solo en la línea, puede verificar que

 x1 < x < x2, assuming x1 < x2, or y1 < y < y2, assuming y1 < y2, or z1 < z < z2, assuming z1 < z2 

Encuentre la distancia del punto P desde ambos puntos finales de línea A, B. Si AB = AP + PB, entonces P se encuentra en el segmento de línea AB.

 AB = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)+(z2-z1)*(z2-z1)); AP = sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1)); PB = sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y)+(z2-z)*(z2-z)); if(AB == AP + PB) return true; 

Primero tome el producto cruzado de AB y AP . Si son colineales, entonces será 0.

En este punto, todavía podría estar en la línea mayor que se extiende más allá de B o antes de A, entonces creo que debería poder comprobar si pz está entre az y bz.

Esto parece ser un duplicado , en realidad, y como menciona una de las respuestas, está en Beautiful Code .

Su segmento se define mejor por ecuación paramétrica

para todos los puntos de su segmento, la siguiente ecuación se cumple: x = x1 + (x2 – x1) * p y = y1 + (y2 – y1) * p z = z1 + (z2 – z1) * p

Donde p es un número en [0; 1]

Entonces, si hay una p de tal manera que las coordenadas de tus puntos satisfagan esas 3 ecuaciones, tu punto está en esta línea. Y p está entre 0 y 1 – también está en el segmento de línea

Aquí hay un código C # para el caso 2D:

 public static bool PointOnLineSegment(PointD pt1, PointD pt2, PointD pt, double epsilon = 0.001) { if (pt.X - Math.Max(pt1.X, pt2.X) > epsilon || Math.Min(pt1.X, pt2.X) - pt.X > epsilon || pt.Y - Math.Max(pt1.Y, pt2.Y) > epsilon || Math.Min(pt1.Y, pt2.Y) - pt.Y > epsilon) return false; if (Math.Abs(pt2.X - pt1.X) < epsilon) return Math.Abs(pt1.X - pt.X) < epsilon || Math.Abs(pt2.X - pt.X) < epsilon; if (Math.Abs(pt2.Y - pt1.Y) < epsilon) return Math.Abs(pt1.Y - pt.Y) < epsilon || Math.Abs(pt2.Y - pt.Y) < epsilon; double x = pt1.X + (pt.Y - pt1.Y) * (pt2.X - pt1.X) / (pt2.Y - pt1.Y); double y = pt1.Y + (pt.X - pt1.X) * (pt2.Y - pt1.Y) / (pt2.X - pt1.X); return Math.Abs(pt.X - x) < epsilon || Math.Abs(pt.Y - y) < epsilon; } 

en caso de que alguien busque una versión en línea:

 public static bool PointOnLine2D (this Vector2 p, Vector2 a, Vector2 b, float t = 1E-03f) { // ensure points are collinear var zero = (bx - ax) * (py - ay) - (px - ax) * (by - ay); if (zero > t || zero < -t) return false; // check if x-coordinates are not equal if (ax - bx > t || bx - ax > t) // ensure x is between ax & bx (use tolerance) return ax > bx ? px + t > bx && px - t < ax : px + t > ax && px - t < bx; // ensure y is between ay & by (use tolerance) return ay > by ? py + t > by && py - t < ay : py + t > ay && py - t < by; } 

El producto cruzado (B – A) × (p – A) debe ser mucho más corto que B – A. Idealmente, el producto cruzado es cero, pero eso es poco probable en hardware de punto flotante de precisión finita.

Según la respuesta anterior de Konstantin, aquí hay un código C para encontrar si un punto está realmente en un segmento de línea FINITE. Esto tiene en cuenta los segmentos de línea horizontal / vertical. Esto también tiene en cuenta que los números de coma flotante nunca son realmente “exactos” al compararlos entre sí. El épsilon predeterminado de 0.001f será suficiente en la mayoría de los casos. Esto es para líneas 2D … agregar “Z” sería trivial. La clase PointF es de GDI +, que básicamente es simplemente: struct PointF{float X,Y};

¡Espero que esto ayude!

 #define DEFFLEQEPSILON 0.001 #define FLOAT_EQE(x,v,e)((((v)-(e))<(x))&&((x)<((v)+(e)))) static bool Within(float fl, float flLow, float flHi, float flEp=DEFFLEQEPSILON){ if((fl>flLow) && (fl 

Yo uso esto para calcular la distancia AB entre los puntos a y b.

 static void Main(string[] args) { double AB = segment(0, 1, 0, 4); Console.WriteLine("Length of segment AB: {0}",AB); } static double segment (int ax,int ay, int bx, int by) { Vector a = new Vector(ax,ay); Vector b = new Vector(bx,by); Vector c = (a & b); return Math.Sqrt(cX + cY); } struct Vector { public readonly float X; public readonly float Y; public Vector(float x, float y) { this.X = x; this.Y = y; } public static Vector operator &(Vector a, Vector b) { return new Vector((bX - aX) * (bX - aX), (bY - aY) * (bY - aY)); } } 

basado en Calcular un punto a lo largo de la línea AB a una distancia determinada de A

Deje que V1 sea el vector (BA) y V2 = (pA), normalice tanto V1 como V2.

Si V1 == (- V2) entonces el punto p está en la línea, pero precediendo a A, y por lo tanto no en el segmento. Si V1 == V2, el punto p está en la línea. Obtenga la longitud de (pA) y verifique si esta es menor o igual a la longitud de (BA), de ser así, el punto está en el segmento; de lo contrario, pasa de B.

Puede verificar si el punto se encuentra entre los dos planos definidos por el punto 1 y el punto 2 y la dirección de la línea:

 /// Returns the closest point from @a point to this line on this line. vector3  line3d ::closest_point (const vector3  & point) const { return this -> point () + direction () * dot (point - this -> point (), direction ()); } /// Returns true if @a point lies between point1 and point2. template  bool line_segment3 ::is_between (const vector3  & point) const { const auto closest = line () .closest_point (point); return abs ((closest - point0 ()) + (closest - point1 ())) <= abs (point0 () - point1 ()); }