Найти, если точка лежит на сегменте линии

У меня есть отрезок линии, определяемый двумя точками A (x1, y1, z1) и B (x2, y2, z2) и точкой p (x, y, z). Как проверить, находится ли точка в сегменте линии?

    Если точка находится на линии, тогда:

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

    Вычислите все три значения, и если они одинаковы (до некоторой степени допуска), ваша точка находится на линии.

    Чтобы проверить, находится ли точка в сегменте, а не только на линии, вы можете проверить,

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

    Найдите расстояние точки P от обеих конечных точек A, B. Если AB = AP + PB, тогда P лежит на отрезке 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; 

    Сначала возьмите крест-произведение AB и AP . Если они коллинеарны, то это будет 0.

    На данный момент он все еще может находиться на большей линии, проходящей мимо B или до A, поэтому я думаю, вы должны просто проверить, находится ли pz между az и bz.

    На самом деле это дубликат , и, как говорится в одном из ответов, он находится в « Красивом коде» .

    Ваш сегмент лучше всего определяется параметрическим уравнением

    для всех точек вашего сегмента выполняется следующее равенство: x = x1 + (x2 – x1) * p y = y1 + (y2 – y1) * p z = z1 + (z2 – z1) * p

    Где p – число в [0; 1]

    Итак, если существует такое ap, что ваши точечные координаты удовлетворяют этим 3 уравнениям, ваша точка находится на этой линии. И он p находится между 0 и 1 – он также находится на сегменте линии

    Вот код C # для 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; } 

    в случае, если кто-то ищет встроенную версию:

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

    Перекрестное произведение (B – A) × (p – A) должно быть намного короче, чем B – A. В идеале кросс – произведение равно нулю, но это маловероятно для аппаратных средств с плавающей запятой с конечной точностью.

    Основываясь на ответе Константина выше, вот какой-то код на C, чтобы определить, действительно ли точка находится на сегменте линии FINITE. Это учитывает сегменты горизонтальной / вертикальной линии. Это также учитывает, что числа с плавающей запятой никогда не являются «точными» при сравнении их друг с другом. В большинстве случаев будет достаточным эпсилон по умолчанию 0,001f. Это для 2D-линий … добавление «Z» было бы тривиальным. Класс PointF – это GDI +, который в основном справедлив: struct PointF{float X,Y};

    Надеюсь это поможет!

     #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 

    Я использую это для вычисления расстояния AB между точками a и 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)); } } 

    основанный на вычислении точки вдоль линии АВ на заданном расстоянии от А

    Пусть V1 – вектор (BA), а V2 = (pA), нормируют как V1, так и V2.

    Если V1 == (- V2), то точка p находится на линии, но предшествует A, поэтому не в сегменте. Если V1 == V2, точка p находится на линии. Получите длину (pA) и проверьте, меньше ли она или равна длине (BA), если точка находится на сегменте, иначе она проходит мимо B.

    Вы можете проверить, находится ли точка между двумя плоскостями, определяемыми точками 1 и 2, и направлением линии:

     /// 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 ()); } 
    Interesting Posts
    Давайте будем гением компьютера.