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

Question

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

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

J'utilise python pour la plupart, mais des exemples dans n'importe quelle langue serait utile.

Answer 1

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

Mais, comme vous le souhaitez savoir si c est entre a et b, vous devez également vérifier que le produit scalaire de (b-a) et (c-a) est positive et est moins que le carré de la distance entre a et b.

Non optimisé pseudo-code:

def isBetween(a, b, c):
    crossproduct = (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y)
    if abs(crossproduct) > epsilon : return False   # (or != 0 if using integers)

    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

Answer 2

Voici comment je ferais:

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)

Answer 3

Vérifiez si le produit vectoriel de (b-a) et (c-a) est de 0. Ah, attendez, vous dites que vous voulez savoir si c'est sur la ligne de segment, pas la même ligne. C'est un peu plus de travail et je n'ai pas de temps pour la réponse je vais supprimer cette réponse partielle après que quelqu'un remplit un bon.

Mise à jour: Deux remarques: tout d'abord, Brian Hayes chapitre dans Belle du Code couvre la conception de l'espace pour une colinéarité-fonction de test -- utile de fond. Deuxièmement, [points qui ont depuis été répondu].

Mise à jour 2: j'aime vincent approche mieux maintenant (et je suis gênée Je ne l'ai pas vu). Mais la comparaison pourrait encore être fait d'une manière plus propre, je pense que, comme ceci:

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

Mise à jour 3: Brian Hayes a souligné que, vous avez besoin seulement de plage de cocher une case de coordonnées, une fois que vous connaissez les points sont colinéaires. (Auparavant, mon code était "and" au lieu de "if a.x != b.x".)

Answer 4

Voici une autre approche:

• Supposons que les deux points 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) .. (juste faire assimiler les pentes)

Le Point C (x3,y3) sera compris 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 (trivial de vérifier)

Answer 5

La longueur du segment n'est pas important, donc à l'aide d'une racine carrée n'est pas nécessaire et devrait être évitée, car nous risquons de perdre un peu de 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)

Certains aléatoires exemple 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)