Найти, если точка лежит на отрезке
У меня есть отрезок, определяемый двумя точками A(x1,y1,z1) и B(x2,y2,z2) и точкой p(x,y,z). Как я могу проверить, лежит ли точка на отрезке?
13 ответов
Если точка находится на прямой, то:
(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.
На самом деле это кажется дубликатом, и, как упоминается в одном из ответов, он есть в Beautiful Code.
В случае, если кто-то ищет встроенную версию:
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;
}
Вот код 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;
}
Ваш сегмент лучше всего определяется параметрическим уравнением
для всех точек в вашем сегменте выполняется следующее уравнение: x = x1 + (x2 - x1) * p y = y1 + (y2 - y1) * p z = z1 + (z2 - z1) * p
Где p - число в [0;1]
Итак, если есть ар, такой что ваши точечные координаты удовлетворяют этим трем уравнениям, ваша точка находится на этой линии. И это р между 0 и 1 - это также на отрезке
Или позвольте dotnet сделать тяжелую работу за вас, если вы используете Visual Studio, используйте GraphicsPath
это также позволит вам добавить допуски, если просто щелкнуть за пределами линии.
using (Drawing2D.GraphicsPath gp = new Drawing2D.GraphicsPath())
{
gp.AddLine(new Point(x1, y1), new Point(x2, y2));
// Make the line as wide as needed (make this larger to allow clicking slightly outside the line)
using (Pen objPen = new Pen(Color.Black, 6))
{
gp.Widen(objPen);
}
if (gp.IsVisible(Mouse.x, Mouse.y))
{
// The line was clicked
}
}
Я использую это, чтобы вычислить расстояние 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));
}
}
на основе Рассчитать точку вдоль линии AB на заданном расстоянии от A
Пусть V1 - вектор (BA), а V2 = (pA), нормализуют как V1, так и V2.
Если V1 == (- V2), то точка p находится на прямой, но предшествует A, и, следовательно, не в сегменте. Если V1 == V2, точка p находится на прямой. Получите длину (pA) и убедитесь, что она меньше или равна длине (BA), если это так, то точка находится на отрезке, иначе она прошла B.
Суммарное произведение (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<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://stackru.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);
}
Это мой код, который можно запускать в WPF
private static bool CheckIsPointOnLine(Point point, Line line, double epsilon = 0.1)
{
// Thank you Rob Agar
// (x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)
// x1 < x < x2, assuming x1 < x2
// y1 < y < y2, assuming y1 < y2
if (EqualPoint(point, line.APoint, epsilon) || EqualPoint(point, line.BPoint, epsilon))
{
return true;
}
if (Math.Abs((point.X - line.APoint.X) / (line.BPoint.X - line.APoint.X) - (point.Y - line.APoint.Y) / (line.BPoint.Y - line.APoint.Y)) < epsilon)
{
var minX = Math.Min(line.APoint.X, line.BPoint.X);
var maxX = Math.Max(line.APoint.X, line.BPoint.X);
var minY = Math.Min(line.APoint.Y, line.BPoint.Y);
var maxY = Math.Max(line.APoint.Y, line.BPoint.Y);
if (minX < point.X && point.X < maxX && minY < point.Y && point.Y < maxY)
{
return true;
}
else
{
return false;
}
}
else
{
return false;
}
}
private static bool EqualPoint(Point a, Point b, double epsilon = 0.001)
{
return Math.Abs(a.X - b.X) < epsilon && Math.Abs(a.Y - b.Y) < epsilon;
}
public record Line
{
public Point APoint { get; init; }
public Point BPoint { get; init; }
}
Мой код находится в github
Спасибо Rob Agar
Вы можете проверить, находится ли точка между двумя плоскостями, определенными point1 и point2, и направлением линии:
/// 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 ());
}