Comment pouvez-vous déterminer qu'un point se trouve entre deux autres points sur un segment de ligne?

Disons que vous avez un plan à deux dimensions avec 2 points (appelés a et b) représentés par un entier x et un entier ay pour chaque point.

Comment pouvez-vous déterminer si un autre point c est sur le segment de droite défini par a et b?

J'utilise le plus python, mais des exemples dans n'importe quel langage seraient utiles.

Vérifiez si le produit croisé de (ba) et (ca) est 0, comme le dit Darius Bacon, vous indique si les points a, b et c sont alignés.

Mais, comme vous voulez savoir si c est compris entre a et b, vous devez également vérifier que le produit scalaire de (ba) et (ca) est positif et est inférieur au carré de la distance entre a et b.

En pseudocode non optimisé:

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

Voici comment je procéderais:

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)

Vérifiez si le produit croisé de b-aet c-aest 0: cela signifie que tous les points sont colinéaires. Si c'est le cas, vérifiez si cles coordonnées de s sont comprises entre ales s et bles. Utilisez les coordonnées x ou y, tant que aet bsont séparés sur cet axe (ou ils sont identiques sur les deux).

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

Cette réponse était un gâchis de trois mises à jour. Les informations intéressantes de leur part: le chapitre de Brian Hayes dans Beautiful Code couvre l'espace de conception d'une fonction de test de colinéarité - contexte utile. La réponse de Vincent a contribué à améliorer celle-ci. Et c'est Hayes qui a suggéré de tester une seule des coordonnées x ou y; à l'origine, le code avait andà la place de if a.x != b.x else.

Voici une autre approche:

• Supposons que les deux points soient A (x1, y1) et B (x2, y2)
• L'équation de la droite passant par ces points est (x-x1) / (y-y1) = (x2-x1) / (y2-y1) .. (en faisant simplement égaliser les pentes)

Le point C (x3, y3) se situera entre A et B si:

• x3, y3 satisfait l'équation ci-dessus.
• x3 se situe entre x1 et x2 et y3 se situe entre y1 et y2 (vérification triviale)

La longueur du segment n'est pas importante, donc l'utilisation d'une racine carrée n'est pas nécessaire et doit être évitée car nous pourrions perdre une certaine précision.

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)

Quelques exemples aléatoires d'utilisation:

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)

Voici une manière différente de procéder, avec du code donné en C ++. Étant donné deux points, l1 et l2, il est trivial d'exprimer le segment de ligne entre eux comme

l1 + A(l2 - l1)

où 0 <= A <= 1. Ceci est connu comme la représentation vectorielle d'une ligne si cela vous intéresse plus que de l'utiliser pour ce problème. Nous pouvons séparer les composantes x et y de ceci, en donnant:

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

Prenez un point (x, y) et remplacez ses composantes x et y dans ces deux expressions pour résoudre A. Le point est sur la ligne si les solutions pour A dans les deux expressions sont égales et 0 <= A <= 1. Parce que la résolution de A nécessite une division, il existe des cas particuliers qui nécessitent une manipulation pour arrêter la division par zéro lorsque le segment de ligne est horizontal ou vertical. La solution finale est la suivante:

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

En utilisant une approche plus géométrique, calculez les distances suivantes:

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)

et testez si ac + bc est égal à ab :

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

C'est parce qu'il y a trois possibilités:

• Les 3 points forment un triangle => ac + bc> ab
• Ils sont colinéaires et c est en dehors du segment ab => ac + bc> ab
• Ils sont colinéaires et c est à l'intérieur du segment ab => ac + bc = ab

Ok, beaucoup de mentions d'algèbre linéaire (produit croisé de vecteurs) et cela fonctionne dans un espace réel (c'est-à-dire à virgule continue ou flottante) mais la question précisait spécifiquement que les deux points étaient exprimés sous forme d' entiers et donc un produit croisé n'est pas le bon solution bien qu’elle puisse donner une solution approximative.

La bonne solution est d'utiliser l' algorithme de ligne de Bresenham entre les deux points et de voir si le troisième point est l'un des points de la ligne. Si les points sont suffisamment éloignés pour que le calcul de l'algorithme ne soit pas performant (et qu'il faudrait que ce soit vraiment grand pour que ce soit le cas), je suis sûr que vous pouvez fouiller et trouver des optimisations.

Le produit scalaire entre (ca) et (ba) doit être égal au produit de leurs longueurs (cela signifie que les vecteurs (ca) et (ba) sont alignés et de même direction). De plus, la longueur de (ca) doit être inférieure ou égale à celle de (ba). Pseudocode:

# 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

J'en avais besoin pour javascript à utiliser dans un canevas html5 pour détecter si le curseur de l'utilisateur était sur ou près d'une certaine ligne. J'ai donc modifié la réponse donnée par 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

Vous pouvez utiliser le produit de coin et de point:

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

Voici comment je l'ai fait à l'école. J'ai oublié pourquoi ce n'est pas une bonne idée.

ÉDITER:

@Darius Bacon: cite un livre "Beautiful Code" qui explique pourquoi le code ci-dessous n'est pas une bonne idée.

#!/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()

Tout point sur le segment de droite ( a , b ) (où a et b sont des vecteurs) peut être exprimé comme une combinaison linéaire des deux vecteurs a et b :

En d'autres termes, si c se trouve sur le segment de droite ( a , b ):

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

En résolvant m , nous obtenons:

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

Donc, notre test devient (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/ -> Sujet 1.02: Comment puis-je trouver la distance d'un point à une ligne?

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

Voici un code Java qui a fonctionné pour moi:

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

que diriez-vous simplement de vous assurer que la pente est la même et que le point est entre les autres?

points donnés (x1, y1) et (x2, y2) (avec x2> x1) et point candidat (a, b)

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

Alors (a, b) doit être sur la ligne entre (x1, y1) et (x2, y2)

Une réponse en C # utilisant une classe 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;
}

Notez que

s * s

est le produit scalaire du vecteur de segment via la surcharge d'opérateurs en C #

La clé est de profiter de la projection du point sur la ligne infinie et d'observer que la quantité scalaire de la projection nous dit trivialement si la projection est sur le segment ou non. Nous pouvons ajuster les bornes de la quantité scalaire pour utiliser une tolérance floue.

Si la projection est dans les limites, nous testons simplement si la distance entre le point et la projection est dans les limites.

L'avantage par rapport à l'approche multi-produits est que la tolérance a une valeur significative.

Voici ma solution avec C # dans 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;
}

Version C # de la réponse 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;
}

Vous pouvez le faire en résolvant l'équation de ligne pour ce segment de ligne avec les coordonnées du point, vous saurez si ce point est sur la ligne, puis en vérifiant les limites du segment pour savoir s'il est à l'intérieur ou à l'extérieur de celui-ci. Vous pouvez appliquer un certain seuil car il se trouve quelque part dans l'espace probablement défini par une valeur à virgule flottante et vous ne devez pas atteindre celui exact. Exemple 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;
    
}