c# - Encontrar si el punto se encuentra en el segmento de línea

algorithm 3d

Question

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

Answer 1

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

Answer 2

Basado en la respuesta de Konstantin anterior, 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 toma en cuenta que los números de punto flotante nunca son realmente "exactos" cuando se comparan entre sí. El epsilon 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: 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<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://.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);
}

Answer 3

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 el hardware de punto flotante de precisión finita.

Answer 4

En caso de que si alguien busca la 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 = (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;
}

Answer 5

Encuentre la distancia del punto P a partir de los 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;

Answer 6

Lo uso para calcular la distancia AB entre los puntos ay 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));
    }
}

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

Answer 7

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 verificar 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 .

Answer 8

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

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

Answer 9

Sea V1 el vector (BA) y V2 = (pA), normalice tanto V1 como V2.

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

Answer 10

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 iguales (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

Answer 11

Tu segmento está mejor definido por la ecuación paramétrica

para todos los puntos en su segmento, la siguiente ecuación es válida: 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 que sus coordenadas de punto satisfagan esas 3 ecuaciones, su punto está en esta línea. Y p es entre 0 y 1, también está en el segmento de línea