Wie können Sie feststellen, dass ein Punkt zwischen zwei anderen Punkten auf einem Liniensegment liegt?

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

Wie können Sie feststellen, ob sich ein anderer Punkt c auf dem durch a und b definierten Liniensegment befindet?

Ich benutze am häufigsten Python, aber Beispiele in jeder Sprache wären hilfreich.

Überprüfen Sie, ob das Kreuzprodukt von (ba) und (ca) 0 ist, wie Darius Bacon mitteilt, ob die Punkte a, b und c ausgerichtet sind.

Wenn Sie jedoch wissen möchten, ob c zwischen a und b liegt, müssen Sie auch überprüfen, ob das Punktprodukt von (ba) und (ca) positiv ist und kleiner als das Quadrat des Abstands zwischen a und b ist.

Im nicht optimierten 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

So würde ich es 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)

Überprüfen Sie, ob das Kreuzprodukt von b-aund c-aist 0: Das bedeutet, dass alle Punkte kollinear sind. Wenn dies der Fall ist, überprüfen Sie, ob cdie Koordinaten zwischen aund liegen b. Verwendung entweder die X oder die Y - Koordinaten, so lange aund bsind getrennt auf dieser Achse (oder sie sind die gleichen auf beiden).

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 bestand aus drei Updates. Die lohnende Information von ihnen: Brian Hayes ' Kapitel in Beautiful Code behandelt den Entwurfsraum für eine Kollinearitätstestfunktion - nützlicher Hintergrund. Vincents Antwort half, diese zu verbessern. Und es war Hayes, der vorschlug, nur eine der x- oder y-Koordinaten zu testen; ursprünglich hatte der Code andanstelle von if a.x != b.x else.

Hier ist ein anderer Ansatz:

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

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

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

Die Länge des Segments ist nicht wichtig, daher ist die Verwendung einer Quadratwurzel nicht erforderlich und sollte vermieden werden, da wir an Genauigkeit verlieren könnten.

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 Anwendungsbeispiel:

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)

Berechnen Sie mit einem geometrischeren Ansatz die folgenden Abstände:

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 testen Sie, ob ac + bc gleich ab ist :

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 des ab- Segments => ac + bc> ab
• Sie sind kollinear und c befindet sich innerhalb des ab- Segments => ac + bc = ab

Hier ist ein anderer Weg, mit Code in C ++. Bei zwei Punkten, l1 und l2, ist es trivial, das Liniensegment zwischen ihnen als auszudrücken

l1 + A(l2 - l1)

Dabei ist 0 <= A <= 1. Dies wird als Vektordarstellung einer Linie bezeichnet, wenn Sie mehr daran interessiert sind, sie nur für dieses Problem zu verwenden. Wir können die x- und y-Komponenten davon aufteilen und geben:

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

Nehmen Sie einen Punkt (x, y) und setzen Sie seine x- und y-Komponenten in diese beiden Ausdrücke ein, um nach 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. Weil Das Lösen nach A erfordert eine Division. Es gibt spezielle Fälle, die behandelt werden müssen, um die Division durch Null zu stoppen, 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;
}

Ok, viele Erwähnungen der linearen Algebra (Kreuzprodukt von Vektoren) und dies funktioniert in einem realen (dh kontinuierlichen oder Gleitkomma-) Raum, aber die Frage stellte speziell fest, dass die beiden Punkte als ganze Zahlen ausgedrückt wurden und daher ein Kreuzprodukt nicht das richtige ist Lösung, obwohl es eine ungefähre Lösung geben kann.

Die richtige Lösung besteht darin, den Bresenham-Linienalgorithmus zwischen den beiden Punkten zu verwenden und festzustellen, ob der dritte Punkt einer der Punkte auf der Linie ist. Wenn die Punkte so weit entfernt sind, dass die Berechnung des Algorithmus nicht performant ist (und es müsste wirklich groß sein, damit dies der Fall ist), könnten Sie sicher herumgraben und Optimierungen finden.

Das Skalarprodukt zwischen (ca) und (ba) muss gleich dem Produkt ihrer Länge sein (dies bedeutet, dass die Vektoren (ca) und (ba) ausgerichtet sind und dieselbe Richtung haben). Darüber hinaus muss die Länge von (ca) kleiner oder gleich der von (ba) 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

Ich brauchte dies für Javascript zur Verwendung in einer HTML5-Zeichenfläche, um festzustellen, ob sich der Cursor des Benutzers über oder in der Nähe einer bestimmten Zeile befand. Also habe ich die Antwort von Darius Bacon in Coffeescript geändert:

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

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

So habe ich es in der Schule gemacht. Ich habe vergessen, warum es keine gute Idee ist.

BEARBEITEN:

@Darius Bacon: zitiert ein "Beautiful Code" -Buch, das eine Erklärung enthält, warum der unten stehende Code keine gute Idee ist.

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

Jeder Punkt auf dem Liniensegment ( a , b ) (wobei a und b Vektoren sind) kann als lineare Kombination der beiden Vektoren a und b ausgedrückt werden :

Mit anderen Worten, wenn c auf dem Liniensegment ( a , b ) liegt:

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

Wenn wir nach m auflösen , erhalten wir:

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

Unser Test wird also (in 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 # Von http://www.faqs.org/faqs/graphics/algorithms-faq/ -> Betreff 1.02: Wie finde ich den Abstand von einem Punkt zu einer Linie?

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

Hier ist ein Java-Code, der für mich funktioniert hat:

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

Wie wäre es nur sicherzustellen, dass die Steigung gleich ist und der Punkt zwischen den anderen liegt?

gegebene Punkte (x1, y1) und (x2, y2) (mit x2> x1) und Kandidatenpunkt (a, b)

wenn (b-y1) / (a-x1) = (y2-y2) / (x2-x1) und x1 <a <x2

Dann muss (a, b) zwischen (x1, y1) und (x2, y2) liegen.

Eine Antwort in C # mit einer Vector2D-Klasse

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

Beachten Sie, dass

s * s

ist das Punktprodukt des Segmentvektors durch Operatorüberladung in C #

Der Schlüssel besteht darin, die Projektion des Punktes auf die unendliche Linie auszunutzen und zu beobachten, dass die skalare Größe der Projektion uns trivial sagt, ob sich die Projektion auf dem Segment befindet oder nicht. Wir können die Grenzen der Skalargröße anpassen, um eine Fuzzy-Toleranz zu verwenden.

Wenn die Projektion innerhalb von Grenzen liegt, testen wir nur, ob der Abstand vom Punkt zur Projektion innerhalb von Grenzen liegt.

Der Vorteil gegenüber dem produktübergreifenden Ansatz besteht darin, dass die Toleranz einen sinnvollen Wert hat.

Hier ist meine Lösung mit C # in 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;
}

C # -Version von Jules 'Antwort:

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

Sie können dies tun, indem Sie die Liniengleichung für dieses Liniensegment mit den Punktkoordinaten lösen. Sie wissen, ob sich dieser Punkt auf der Linie befindet, und überprüfen dann die Grenzen des Segments, um festzustellen, ob er sich innerhalb oder außerhalb des Segments befindet. Sie können einen bestimmten Schwellenwert anwenden, da er sich wahrscheinlich irgendwo im Raum befindet, der höchstwahrscheinlich durch einen Gleitkommawert definiert ist, und Sie dürfen den genauen nicht treffen. Beispiel in 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;
    
}