У меня есть отрезок линии, определяемый двумя точками A (x1, y1, z1) и B (x2, y2, z2) и точкой p (x, y, z). Как проверить, находится ли точка в сегменте линии?
Найти, если точка лежит на сегменте линии
Ответ 1
Если точка на линии, то:
(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
Ответ 2
Найдите расстояние точки 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;
Ответ 3
Сначала возьмите перекрестный продукт AB и AP. Если они коллинеарны, то это будет 0.
В этот момент он все еще может быть на большей линии, проходящей мимо B или до A, поэтому я думаю, вы должны просто проверить, находится ли pz между az и bz.
Этот кажется дублирующим, на самом деле, и, как говорится в одном из ответов, он находится в Beautiful Code.
Ответ 4
Ваш сегмент лучше всего определяется параметрическим уравнением
для всех точек вашего сегмента, если выполнено равенство: x = x1 + (x2 - x1) * p y = y1 + (y2 - y1) * p z = z1 + (z2 - z1) * p
Где p - число в [0; 1]
Итак, если существует p такое, что ваши координаты точки удовлетворяют тем 3, ваша точка находится в этой строке. И он p находится между 0 и 1 - он также находится в сегменте линии
Ответ 5
Здесь некоторый код С# для 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;
}
Ответ 6
если кто-то ищет встроенную версию:
public static bool PointOnLine2D (this Vector2 p, Vector2 a, Vector2 b, float t = 1E-03f)
{
// ensure points are collinear
var zero = (b.x - a.x) * (p.y - a.y) - (p.x - a.x) * (b.y - a.y);
if (zero > t || zero < -t) return false;
// check if x-coordinates are not equal
if (a.x - b.x > t || b.x - a.x > t)
// ensure x is between a.x & b.x (use tolerance)
return a.x > b.x
? p.x + t > b.x && p.x - t < a.x
: p.x + t > a.x && p.x - t < b.x;
// ensure y is between a.y & b.y (use tolerance)
return a.y > b.y
? p.y + t > b.y && p.y - t < a.y
: p.y + t > a.y && p.y - t < b.y;
}
Ответ 7
Перекрестное произведение (B - A) & times; (p - A) должно быть намного короче, чем B - A. Идеально, кросс-произведение равно нулю, но маловероятно для аппаратных средств с плавающей запятой с конечной точностью.
Ответ 8
На основании ответа Konstantin выше, вот какой-то код 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<flHi)){ return true; }
if(FLOAT_EQE(fl,flLow,flEp) || FLOAT_EQE(fl,flHi,flEp)){ return true; }
return false;
}
static bool PointOnLine(const PointF& ptL1, const PointF& ptL2, const PointF& ptTest, float flEp=DEFFLEQEPSILON){
bool bTestX = true;
const float flX = ptL2.X-ptL1.X;
if(FLOAT_EQE(flX,0.0f,flEp)){
// vertical line -- ptTest.X must equal ptL1.X to continue
if(!FLOAT_EQE(ptTest.X,ptL1.X,flEp)){ return false; }
bTestX = false;
}
bool bTestY = true;
const float flY = ptL2.Y-ptL1.Y;
if(FLOAT_EQE(flY,0.0f,flEp)){
// horizontal line -- ptTest.Y must equal ptL1.Y to continue
if(!FLOAT_EQE(ptTest.Y,ptL1.Y,flEp)){ return false; }
bTestY = false;
}
// found here: http://stackoverflow.com/a/7050309
// x = x1 + (x2 - x1) * p
// y = y1 + (y2 - y1) * p
// solve for p:
const float pX = bTestX?((ptTest.X-ptL1.X)/flX):0.5f;
const float pY = bTestY?((ptTest.Y-ptL1.Y)/flY):0.5f;
return Within(pX,0.0f,1.0f,flEp) && Within(pY,0.0f,1.0f,flEp);
}
Ответ 9
Я использую это для вычисления расстояния 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(c.X + c.Y);
}
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((b.X - a.X) * (b.X - a.X), (b.Y - a.Y) * (b.Y - a.Y));
}
}
на основе Рассчитайте точку вдоль линии A-B на заданном расстоянии от A
Ответ 10
Пусть V1 - вектор (B-A), а V2 = (p-A), нормируют как V1, так и V2.
Если V1 == (- V2), то точка p находится на линии, но предшествует A и, следовательно, не находится в сегменте. Если V1 == V2, точка p находится на линии. Получите длину (p-A) и проверьте, меньше или равно ее длины (B-A), если точка находится на сегменте, иначе она прошла мимо B.
Ответ 11
Вы можете проверить, находится ли точка между двумя плоскостями, определяемыми точками 1 и 2, и направлением линии:
/// Returns the closest point from @a point to this line on this line.
vector3 <Type>
line3d <Type>::closest_point (const vector3 <Type> & point) const
{
return this -> point () + direction () * dot (point - this -> point (), direction ());
}
/// Returns true if @a point lies between point1 and point2.
template <class Type>
bool
line_segment3 <Type>::is_between (const vector3 <Type> & point) const
{
const auto closest = line () .closest_point (point);
return abs ((closest - point0 ()) + (closest - point1 ())) <= abs (point0 () - point1 ());
}