¿Cómo se puede determinar que un punto está entre otros dos puntos en un segmento de línea?

Digamos que tiene un plano bidimensional con 2 puntos (llamados ayb) representados por un entero x y un entero ay para cada punto.

¿Cómo se puede determinar si otro punto c está en el segmento de línea definido por ay b?

Yo uso Python más, pero los ejemplos en cualquier idioma serían útiles.

Compruebe si el producto cruzado de (ba) y (ca) es 0, como le dice Darius Bacon, le dice si los puntos a, byc están alineados.

Pero, como desea saber si c está entre ayb, también debe verificar que el producto escalar de (ba) y (ca) sea positivo y sea menor que el cuadrado de la distancia entre ay b.

En pseudocódigo no optimizado:

def isBetween(a, b, c):
    crossproduct = (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y)

    # compare versus epsilon for floating point values, or != 0 if using integers
    if abs(crossproduct) > epsilon:
        return False

    dotproduct = (c.x - a.x) * (b.x - a.x) + (c.y - a.y)*(b.y - a.y)
    if dotproduct < 0:
        return False

    squaredlengthba = (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)
    if dotproduct > squaredlengthba:
        return False

    return True

Así es como lo haría:

def distance(a,b):
    return sqrt((a.x - b.x)**2 + (a.y - b.y)**2)

def is_between(a,c,b):
    return distance(a,c) + distance(c,b) == distance(a,b)

Compruebe si el producto cruzado de b-ay c-aes 0: eso significa que todos los puntos son colineales. Si es así, compruebe si clas coordenadas de 'están entre a' y b's. Utilice las coordenadas x o y, siempre que ay bestén separados en ese eje (o sean iguales en ambos).

def is_on(a, b, c):
    "Return true iff point c intersects the line segment from a to b."
    # (or the degenerate case that all 3 points are coincident)
    return (collinear(a, b, c)
            and (within(a.x, c.x, b.x) if a.x != b.x else 
                 within(a.y, c.y, b.y)))

def collinear(a, b, c):
    "Return true iff a, b, and c all lie on the same line."
    return (b.x - a.x) * (c.y - a.y) == (c.x - a.x) * (b.y - a.y)

def within(p, q, r):
    "Return true iff q is between p and r (inclusive)."
    return p <= q <= r or r <= q <= p

Esta respuesta solía ser un desastre de tres actualizaciones. La información valiosa de ellos: el capítulo de Brian Hayes en Beautiful Code cubre el espacio de diseño para una función de prueba de colinealidad: antecedentes útiles. La respuesta de Vincent ayudó a mejorar este. Y fue Hayes quien sugirió probar solo una de las coordenadas x o y; originalmente el código tenía anden lugar de if a.x != b.x else.

Aquí hay otro enfoque:

• Supongamos que los dos puntos son A (x1, y1) y B (x2, y2)
• La ecuación de la línea que pasa por esos puntos es (x-x1) / (y-y1) = (x2-x1) / (y2-y1) .. (simplemente igualando las pendientes)

El punto C (x3, y3) estará entre A y B si:

• x3, y3 satisface la ecuación anterior.
• x3 se encuentra entre x1 y x2 e y3 se encuentra entre y1 e y2 (verificación trivial)

La longitud del segmento no es importante, por lo que no es necesario utilizar una raíz cuadrada y debe evitarse ya que podríamos perder algo de precisión.

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Segment:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def is_between(self, c):
        # Check if slope of a to c is the same as a to b ;
        # that is, when moving from a.x to c.x, c.y must be proportionally
        # increased than it takes to get from a.x to b.x .

        # Then, c.x must be between a.x and b.x, and c.y must be between a.y and b.y.
        # => c is after a and before b, or the opposite
        # that is, the absolute value of cmp(a, b) + cmp(b, c) is either 0 ( 1 + -1 )
        #    or 1 ( c == a or c == b)

        a, b = self.a, self.b             

        return ((b.x - a.x) * (c.y - a.y) == (c.x - a.x) * (b.y - a.y) and 
                abs(cmp(a.x, c.x) + cmp(b.x, c.x)) <= 1 and
                abs(cmp(a.y, c.y) + cmp(b.y, c.y)) <= 1)

Algún ejemplo aleatorio de uso:

a = Point(0,0)
b = Point(50,100)
c = Point(25,50)
d = Point(0,8)

print Segment(a,b).is_between(c)
print Segment(a,b).is_between(d)

Aquí hay una forma diferente de hacerlo, con código proporcionado en C ++. Dados dos puntos, l1 y l2, es trivial expresar el segmento de línea entre ellos como

l1 + A(l2 - l1)

donde 0 <= A <= 1. Esto se conoce como la representación vectorial de una línea si está interesado más allá de usarla para este problema. Podemos dividir los componentes xey de esto, dando:

x = l1.x + A(l2.x - l1.x)
y = l1.y + A(l2.y - l1.y)

Tome un punto (x, y) y sustituya sus componentes xey en estas dos expresiones para resolver A. El punto está en la línea si las soluciones para A en ambas expresiones son iguales y 0 <= A <= 1. Porque Resolver para A requiere división, hay casos especiales que deben manejarse para detener la división por cero cuando el segmento de línea es horizontal o vertical. La solución final es la siguiente:

// Vec2 is a simple x/y struct - it could very well be named Point for this use

bool isBetween(double a, double b, double c) {
    // return if c is between a and b
    double larger = (a >= b) ? a : b;
    double smaller = (a != larger) ? a : b;

    return c <= larger && c >= smaller;
}

bool pointOnLine(Vec2<double> p, Vec2<double> l1, Vec2<double> l2) {
    if(l2.x - l1.x == 0) return isBetween(l1.y, l2.y, p.y); // vertical line
    if(l2.y - l1.y == 0) return isBetween(l1.x, l2.x, p.x); // horizontal line

    double Ax = (p.x - l1.x) / (l2.x - l1.x);
    double Ay = (p.y - l1.y) / (l2.y - l1.y);

    // We want Ax == Ay, so check if the difference is very small (floating
    // point comparison is fun!)

    return fabs(Ax - Ay) < 0.000001 && Ax >= 0.0 && Ax <= 1.0;
}

Utilizando un enfoque más geométrico, calcule las siguientes distancias:

ab = sqrt((a.x-b.x)**2 + (a.y-b.y)**2)
ac = sqrt((a.x-c.x)**2 + (a.y-c.y)**2)
bc = sqrt((b.x-c.x)**2 + (b.y-c.y)**2)

y pruebe si ac + bc es igual a ab :

is_on_segment = abs(ac + bc - ab) < EPSILON

Eso es porque hay tres posibilidades:

• Los 3 puntos forman un triángulo => ac + bc> ab
• Son colineales yc está fuera del segmento ab => ac + bc> ab
• Son colineales yc está dentro del segmento ab => ac + bc = ab

Ok, muchas menciones de álgebra lineal (producto cruzado de vectores) y esto funciona en un espacio real (es decir, continuo o de punto flotante), pero la pregunta establece específicamente que los dos puntos se expresaron como números enteros. y, por lo tanto, un producto cruzado no es el correcto. solución aunque puede dar una solución aproximada.

La solución correcta es usar el algoritmo de línea de Bresenham entre los dos puntos y ver si el tercer punto es uno de los puntos de la línea. Si los puntos están lo suficientemente distantes como para que el cálculo del algoritmo no funcione (y tendría que ser muy grande para que ese sea el caso), estoy seguro de que podría investigar y encontrar optimizaciones.

El producto escalar entre (ca) y (ba) debe ser igual al producto de sus longitudes (esto significa que los vectores (ca) y (ba) están alineados y con la misma dirección). Además, la longitud de (ca) debe ser menor o igual que la de (ba). Pseudocódigo:

# epsilon = small constant

def isBetween(a, b, c):
    lengthca2  = (c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y)
    lengthba2  = (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)
    if lengthca2 > lengthba2: return False
    dotproduct = (c.x - a.x)*(b.x - a.x) + (c.y - a.y)*(b.y - a.y)
    if dotproduct < 0.0: return False
    if abs(dotproduct*dotproduct - lengthca2*lengthba2) > epsilon: return False 
    return True

Necesitaba esto para javascript para usarlo en un lienzo html5 para detectar si el cursor del usuario estaba sobre o cerca de una determinada línea. Así que modifiqué la respuesta dada por Darius Bacon en coffeescript:

is_on = (a,b,c) ->
    # "Return true if point c intersects the line segment from a to b."
    # (or the degenerate case that all 3 points are coincident)
    return (collinear(a,b,c) and withincheck(a,b,c))

withincheck = (a,b,c) ->
    if a[0] != b[0]
        within(a[0],c[0],b[0]) 
    else 
        within(a[1],c[1],b[1])

collinear = (a,b,c) ->
    # "Return true if a, b, and c all lie on the same line."
    ((b[0]-a[0])*(c[1]-a[1]) < (c[0]-a[0])*(b[1]-a[1]) + 1000) and ((b[0]-a[0])*(c[1]-a[1]) > (c[0]-a[0])*(b[1]-a[1]) - 1000)

within = (p,q,r) ->
    # "Return true if q is between p and r (inclusive)."
    p <= q <= r or r <= q <= p

Puede utilizar el producto de puntos y cuñas:

def dot(v,w): return v.x*w.x + v.y*w.y
def wedge(v,w): return v.x*w.y - v.y*w.x

def is_between(a,b,c):
   v = a - b
   w = b - c
   return wedge(v,w) == 0 and dot(v,w) > 0

Así es como lo hice en la escuela. Olvidé por qué no es una buena idea.

EDITAR:

@Darius Bacon: cita un libro "Beautiful Code" que contiene una explicación de por qué el siguiente código no es una buena idea.

#!/usr/bin/env python
from __future__ import division

epsilon = 1e-6

class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y

class LineSegment:
    """
    >>> ls = LineSegment(Point(0,0), Point(2,4))
    >>> Point(1, 2) in ls
    True
    >>> Point(.5, 1) in ls
    True
    >>> Point(.5, 1.1) in ls
    False
    >>> Point(-1, -2) in ls
    False
    >>> Point(.1, 0.20000001) in ls
    True
    >>> Point(.1, 0.2001) in ls
    False
    >>> ls = LineSegment(Point(1, 1), Point(3, 5))
    >>> Point(2, 3) in ls
    True
    >>> Point(1.5, 2) in ls
    True
    >>> Point(0, -1) in ls
    False
    >>> ls = LineSegment(Point(1, 2), Point(1, 10))
    >>> Point(1, 6) in ls
    True
    >>> Point(1, 1) in ls
    False
    >>> Point(2, 6) in ls 
    False
    >>> ls = LineSegment(Point(-1, 10), Point(5, 10))
    >>> Point(3, 10) in ls
    True
    >>> Point(6, 10) in ls
    False
    >>> Point(5, 10) in ls
    True
    >>> Point(3, 11) in ls
    False
    """
    def __init__(self, a, b):
        if a.x > b.x:
            a, b = b, a
        (self.x0, self.y0, self.x1, self.y1) = (a.x, a.y, b.x, b.y)
        self.slope = (self.y1 - self.y0) / (self.x1 - self.x0) if self.x1 != self.x0 else None

    def __contains__(self, c):
        return (self.x0 <= c.x <= self.x1 and
                min(self.y0, self.y1) <= c.y <= max(self.y0, self.y1) and
                (not self.slope or -epsilon < (c.y - self.y(c.x)) < epsilon))

    def y(self, x):        
        return self.slope * (x - self.x0) + self.y0

if __name__ == '__main__':
    import  doctest
    doctest.testmod()

Cualquier punto en el segmento de línea ( un , b ) (donde un y b son vectores) se puede expresar como una combinación lineal de los dos vectores a y b :

En otras palabras, si c se encuentra en el segmento de línea ( a , b ):

c = ma + (1 - m)b, where 0 <= m <= 1

Resolviendo para m , obtenemos:

m = (c.x - b.x)/(a.x - b.x) = (c.y - b.y)/(a.y - b.y)

Entonces, nuestra prueba se convierte (en Python):

def is_on(a, b, c):
    """Is c on the line segment ab?"""

    def _is_zero( val ):
        return -epsilon < val < epsilon

    x1 = a.x - b.x
    x2 = c.x - b.x
    y1 = a.y - b.y
    y2 = c.y - b.y

    if _is_zero(x1) and _is_zero(y1):
        # a and b are the same point:
        # so check that c is the same as a and b
        return _is_zero(x2) and _is_zero(y2)

    if _is_zero(x1):
        # a and b are on same vertical line
        m2 = y2 * 1.0 / y1
        return _is_zero(x2) and 0 <= m2 <= 1
    elif _is_zero(y1):
        # a and b are on same horizontal line
        m1 = x2 * 1.0 / x1
        return _is_zero(y2) and 0 <= m1 <= 1
    else:
        m1 = x2 * 1.0 / x1
        if m1 < 0 or m1 > 1:
            return False
        m2 = y2 * 1.0 / y1
        return _is_zero(m2 - m1)

c # De http://www.faqs.org/faqs/graphics/algorithms-faq/ -> Asunto 1.02: ¿Cómo encuentro la distancia de un punto a una línea?

Boolean Contains(PointF from, PointF to, PointF pt, double epsilon)
        {

            double segmentLengthSqr = (to.X - from.X) * (to.X - from.X) + (to.Y - from.Y) * (to.Y - from.Y);
            double r = ((pt.X - from.X) * (to.X - from.X) + (pt.Y - from.Y) * (to.Y - from.Y)) / segmentLengthSqr;
            if(r<0 || r>1) return false;
            double sl = ((from.Y - pt.Y) * (to.X - from.X) - (from.X - pt.X) * (to.Y - from.Y)) / System.Math.Sqrt(segmentLengthSqr);
            return -epsilon <= sl && sl <= epsilon;
        }

Aquí hay un código Java que funcionó para mí:

boolean liesOnSegment(Coordinate a, Coordinate b, Coordinate  c) {

    double dotProduct = (c.x - a.x) * (c.x - b.x) + (c.y - a.y) * (c.y - b.y);
    if (dotProduct < 0) return true;
    return false;
}

¿Qué tal si nos aseguramos de que la pendiente sea la misma y el punto entre los demás?

puntos dados (x1, y1) y (x2, y2) (con x2> x1) y punto candidato (a, b)

si (b-y1) / (a-x1) = (y2-y2) / (x2-x1) Y x1 <a <x2

Entonces (a, b) debe estar en línea entre (x1, y1) y (x2, y2)

Una respuesta en C # usando una clase Vector2D

public static bool IsOnSegment(this Segment2D @this, Point2D c, double tolerance)
{
     var distanceSquared = tolerance*tolerance;
     // Start of segment to test point vector
     var v = new Vector2D( @this.P0, c ).To3D();
     // Segment vector
     var s = new Vector2D( @this.P0, @this.P1 ).To3D();
     // Dot product of s
     var ss = s*s;
     // k is the scalar we multiply s by to get the projection of c onto s
     // where we assume s is an infinte line
     var k = v*s/ss;
     // Convert our tolerance to the units of the scalar quanity k
     var kd = tolerance / Math.Sqrt( ss );
     // Check that the projection is within the bounds
     if (k <= -kd || k >= (1+kd))
     {
        return false;
     }
     // Find the projection point
     var p = k*s;
     // Find the vector between test point and it's projection
     var vp = (v - p);
     // Check the distance is within tolerance.
     return vp * vp < distanceSquared;
}

Tenga en cuenta que

s * s

es el producto escalar del vector de segmento a través de la sobrecarga del operador en C #

La clave es aprovechar la proyección del punto sobre la línea infinita y observar que la cantidad escalar de la proyección nos dice trivialmente si la proyección está sobre el segmento o no. Podemos ajustar los límites de la cantidad escalar para usar una tolerancia difusa.

Si la proyección está dentro de los límites, solo probamos si la distancia desde el punto a la proyección está dentro de los límites.

El beneficio sobre el enfoque de productos cruzados es que la tolerancia tiene un valor significativo.

Aquí está mi solución con C # en Unity.

private bool _isPointOnLine( Vector2 ptLineStart, Vector2 ptLineEnd, Vector2 ptPoint )
{
    bool bRes = false;
    if((Mathf.Approximately(ptPoint.x, ptLineStart.x) || Mathf.Approximately(ptPoint.x, ptLineEnd.x)))
    {
        if(ptPoint.y > ptLineStart.y && ptPoint.y < ptLineEnd.y)
        {
            bRes = true;
        }
    }
    else if((Mathf.Approximately(ptPoint.y, ptLineStart.y) || Mathf.Approximately(ptPoint.y, ptLineEnd.y)))
    {
        if(ptPoint.x > ptLineStart.x && ptPoint.x < ptLineEnd.x)
        {
            bRes = true;
        }
    }
    return bRes;
}

Versión C # de la respuesta de Jules:

public static double CalcDistanceBetween2Points(double x1, double y1, double x2, double y2)
{
    return Math.Sqrt(Math.Pow (x1-x2, 2) + Math.Pow (y1-y2, 2));
}

public static bool PointLinesOnLine (double x, double y, double x1, double y1, double x2, double y2, double allowedDistanceDifference)
{
    double dist1 = CalcDistanceBetween2Points(x, y, x1, y1);
    double dist2 = CalcDistanceBetween2Points(x, y, x2, y2);
    double dist3 = CalcDistanceBetween2Points(x1, y1, x2, y2);
    return Math.Abs(dist3 - (dist1 + dist2)) <= allowedDistanceDifference;
}

Puede hacerlo resolviendo la ecuación de línea para ese segmento de línea con las coordenadas del punto, sabrá si ese punto está en la línea y luego verificando los límites del segmento para saber si está dentro o fuera de él. Puede aplicar algún umbral porque, bueno, está en algún lugar del espacio probablemente definido por un valor de punto flotante y no debe alcanzar el exacto. Ejemplo en php

function getLineDefinition($p1=array(0,0), $p2=array(0,0)){
    
    $k = ($p1[1]-$p2[1])/($p1[0]-$p2[0]);
    $q = $p1[1]-$k*$p1[0];
    
    return array($k, $q);
    
}

function isPointOnLineSegment($line=array(array(0,0),array(0,0)), $pt=array(0,0)){
    
    // GET THE LINE DEFINITION y = k.x + q AS array(k, q) 
    $def = getLineDefinition($line[0], $line[1]);
    
    // use the line definition to find y for the x of your point
    $y = $def[0]*$pt[0]+$def[1];

    $yMin = min($line[0][1], $line[1][1]);
    $yMax = max($line[0][1], $line[1][1]);

    // exclude y values that are outside this segments bounds
    if($y>$yMax || $y<$yMin) return false;
    
    // calculate the difference of your points y value from the reference value calculated from lines definition 
    // in ideal cases this would equal 0 but we are dealing with floating point values so we need some threshold value not to lose results
    // this is up to you to fine tune
    $diff = abs($pt[1]-$y);
    
    $thr = 0.000001;
    
    return $diff<=$thr;
    
}