Wie kann man feststellen, dass ein Punkt zwischen zwei anderen Punkten auf einer Strecke liegt?

Question

Nehmen wir an, Sie haben eine zweidimensionale Ebene mit 2 Punkten (genannt a und b) darauf, die durch eine x-Ganzzahl und eine y-Ganzzahl für jeden Punkt dargestellt werden.

Wie kann man feststellen, ob ein weiterer Punkt c auf der durch a und b definierten Strecke liegt?

Ich verwende hauptsächlich Python, aber Beispiele in jeder Sprache wären hilfreich.

Answer 1

Sie können das Keil- und Punktprodukt verwenden:

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

Answer 2

Berechnen Sie die folgenden Entfernungen mit einem geometrischen Ansatz:

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)

und prüfen, ob ac+bc ist gleich ab :

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

Das liegt daran, dass es drei Möglichkeiten gibt:

• Die 3 Punkte bilden ein Dreieck => ac+bc > ab
• Sie sind kollinear und c liegt außerhalb der ab Segment => ac+bc > ab
• Sie sind kollinear und c befindet sich innerhalb der ab Segment => ac+bc = ab

Answer 3

Hier ist ein anderer Weg, um dies zu erreichen, mit Code in C++. Bei zwei Punkten, l1 und l2, ist es trivial, das Liniensegment zwischen ihnen wie folgt auszudrücken

l1 + A(l2 - l1)

wobei 0 <= A <= 1. Dies ist die so genannte Vektordarstellung einer Geraden, falls Sie mehr daran interessiert sind, als sie nur für dieses Problem zu verwenden. Wir können die x- und y-Komponenten davon aufspalten, was ergibt:

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

Man nehme einen Punkt (x, y) und setze seine x- und y-Komponenten in diese beiden Ausdrücke ein, um A zu lösen. Der Punkt liegt auf der Linie, wenn die Lösungen für A in beiden Ausdrücken gleich sind und 0 <= A <= 1. Da das Lösen von A eine Division erfordert, gibt es spezielle Fälle, die behandelt werden müssen, um die Division durch Null zu verhindern, wenn das Liniensegment horizontal oder vertikal ist. Die endgültige Lösung lautet wie folgt:

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

Answer 4

Das Skalarprodukt zwischen (c-a) und (b-a) muss gleich dem Produkt ihrer Längen sein (das bedeutet, dass die Vektoren (c-a) und (b-a) ausgerichtet sind und die gleiche Richtung haben). Außerdem muss die Länge von (c-a) kleiner oder gleich der Länge von (b-a) sein. 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

Answer 5

Ich brauchte diese für Javascript für den Einsatz in einem html5 Leinwand für die Erkennung, wenn der Benutzer Cursor über oder in der Nähe einer bestimmten Zeile war. Also änderte ich die Antwort von Darius Bacon in coffeescript gegeben:

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