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

Prüfen Sie, ob die Kreuzprodukt von (b-a) und (c-a) gleich 0 ist, wie Darius Bacon sagt, sagt dir, ob die Punkte a, b und c aufeinander ausgerichtet sind.

Da man aber wissen will, ob c zwischen a und b liegt, muss man auch prüfen, ob die Punktprodukt von (b-a) und (c-a) ist positiv und ist weniger als das Quadrat des Abstands zwischen a und b.

In nicht optimiertem Pseudocode:

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

Answer 2

Ich würde es folgendermaßen machen:

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

Prüfen Sie, ob das Kreuzprodukt von b-a y c-a es 0 : Das bedeutet, dass alle Punkte kollinear sind. Wenn das der Fall ist, prüfen Sie, ob c Die Koordinaten liegen zwischen a und b 's. Verwenden Sie entweder die x- oder die y-Koordinaten, solange a y b auf dieser Achse getrennt sind (oder sie sind auf beiden gleich).

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

Diese Antwort war ein Durcheinander von drei Aktualisierungen. Die wertvollen Informationen von ihnen: Brian Hayes's Kapitel in Schöner Code deckt den Entwurfsraum für eine Kollinearitätstestfunktion ab - nützlicher Hintergrund. Vincents Antwort dazu beigetragen, diese zu verbessern. Und es war Hayes, der vorschlug, nur eine der x- oder y-Koordinaten zu testen; ursprünglich hatte der Code and anstelle von if a.x != b.x else .

(Dies ist für exakte Arithmetik mit ganzen oder rationalen Zahlen kodiert; wenn Sie stattdessen Fließkommazahlen übergeben, wird es Probleme mit Rundungsfehlern geben. Ich bin mir nicht einmal sicher, wie man den Abstand von 2-D-Punkten in Fließkomma-Koordinaten definieren kann).

Answer 4

Hier ist ein anderer Ansatz:

• Nehmen wir an, die beiden Punkte sind A (x1,y1) und B (x2,y2)
• Die Gleichung der Geraden, die durch diese Punkte verläuft, lautet (x-x1)/(y-y1)=(x2-x1)/(y2-y1) (nur Gleichsetzung der Steigungen)

Der Punkt C (x3,y3) liegt zwischen A und B, wenn:

• x3,y3 erfüllt die obige Gleichung.
• x3 liegt zwischen x1 und x2 und y3 liegt zwischen y1 und y2 (Trivialkontrolle)

Answer 5

Die Länge des Segments ist nicht wichtig, daher ist die Verwendung einer Quadratwurzel nicht erforderlich und sollte auch vermieden werden, da es zu einem Präzisionsverlust kommen könnte.

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)

Ein zufälliges Beispiel für die Verwendung :

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)