Trova se il punto giace sul segmento di linea

Ho un segmento di linea definito da due punti A (x1, y1, z1) e B (x2, y2, z2) e punto p (x, y, z). Come posso verificare se il punto si trova sul segmento di linea?

Se il punto è sulla linea, allora:

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

Calcola tutti e tre i valori e, se sono uguali (con un certo grado di tolleranza), il tuo punto è sulla linea.

Per verificare se il punto si trova nel segmento, non solo sulla linea, puoi verificarlo

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

Trova la distanza del punto P da entrambi i punti di fine linea A, B. Se AB = AP + PB, allora P si trova sul segmento di linea 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; 

Prendi prima il prodotto incrociato di AB e AP . Se sono colineari, allora sarà 0.

A questo punto, potrebbe ancora essere sulla linea più grande che si estende oltre B o prima di A, quindi penso che dovresti essere in grado di controllare se pz è tra az e bz.

Questo sembra essere un duplicato , in realtà, e come una delle risposte menziona, è in Beautiful Code .

Il tuo segmento è meglio definito dall’equazione parametrica

per tutti i punti del segmento, le seguenti stringhe di equazioni: x = x1 + (x2 – x1) * p y = y1 + (y2 – y1) * p z = z1 + (z2 – z1) * p

Dove p è un numero in [0; 1]

Quindi, se vi è un ap tale che le coordinate del punto soddisfino quelle 3 equazioni, il tuo punto è su questa linea. E p è tra 0 e 1 – è anche un segmento in linea

Ecco un codice C # per il 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; } 

nel caso in cui qualcuno cerchi la versione inline:

 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; } 

Il prodotto incrociato (B – A) × (p – A) dovrebbe essere molto più corto di B – A. Idealmente, il prodotto incrociato è zero, ma è improbabile su hardware a virgola mobile con precisione finita.

In base alla risposta di Konstantin sopra, ecco un codice C per scoprire se un punto si trova effettivamente su un segmento di linea FINITE. Questo tiene conto dei segmenti di linea orizzontali / verticali. Questo prende anche in considerazione che i numeri in virgola mobile non sono mai veramente “esatti” quando li confrontano tra loro. L’epsilon predefinito di 0.001f sarà sufficiente nella maggior parte dei casi. Questo è per linee 2D … l’aggiunta di “Z” sarebbe banale. La class PointF proviene da GDI +, che è fondamentalmente solo: struct PointF{float X,Y};

Spero che questo ti aiuti!

 #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 

Lo uso per calcolare la distanza AB tra i punti a e 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)); } } 

basato su Calcola un punto lungo la linea AB ad una data distanza da A

Sia V1 il vettore (BA) e V2 = (pA), normalizzate sia V1 sia V2.

Se V1 == (- V2) allora il punto p è sulla linea, ma prima di A, e quindi non nel segmento. Se V1 == V2 il punto p è sulla linea. Ottieni la lunghezza di (pA) e controlla se questo è inferiore o uguale alla lunghezza di (BA), in tal caso il punto è sul segmento, altrimenti è passato B.

È ansible verificare se il punto si trova tra i due piani definiti dal punto 1 e dal punto 2 e la direzione della linea:

 /// 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 ()); }