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

Jeder beliebige Punkt auf dem Liniensegment ( a , b ) (wobei a y b Vektoren sind) kann ausgedrückt werden als a Linearkombination der beiden Vektoren a y b :

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

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

Lösen für m 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)

Answer 2

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

Answer 3

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 über Operatorüberladung in C#

Der Schlüssel liegt darin, die Projektion des Punktes auf die unendliche Linie zu nutzen und zu beobachten, dass die Skalarmenge der Projektion uns trivialerweise sagt, ob die Projektion auf dem Segment liegt oder nicht. Wir können die Grenzen der skalaren Größe anpassen, um eine unscharfe Toleranz zu verwenden.

Wenn die Projektion innerhalb der Grenzen liegt, testen wir einfach, ob der Abstand zwischen dem Punkt und der Projektion innerhalb der Grenzen liegt.

Der Vorteil gegenüber dem Kreuzproduktansatz ist, dass die Toleranz einen sinnvollen Wert hat.

Answer 4

Hier ist ein Java-Code, der bei mir 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);
    return (dotProduct < 0);
}

Answer 5

C# Von http://www.faqs.org/faqs/graphics/algorithms-faq/ -> Thema 1.02: Wie findet man den Abstand eines Punktes zu einer Geraden?

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