Как вы можете определить точку между двумя другими точками на отрезке?

Question

Допустим, у вас есть двумерная плоскость с 2 точками (называемыми a и b), представленными целым числом x и целым числом y для каждой точки.

Как вы можете определить, находится ли другая точка c на отрезке, определяемом a и b?

Я чаще использую python, но примеры на любом языке были бы полезны.

Answer 1

Вот код Java, который работал для меня:

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

Answer 2

C # От http://www.faqs.org/faqs/graphics/algorithms-faq/ -> Тема 1.02: Как мне найти расстояние от точки до прямой?

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

Answer 3

Любая точка на отрезке ( a , b ) (где a и b - векторы) может быть выражена как линейная комбинация двух векторов a и b :

Другими словами, если c лежит на отрезке ( a , b ):

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

Решая за м , получим:

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

Итак, наш тест становится (в 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 4

Вот как я это сделал в школе. Я забыл, почему это не очень хорошая идея.

РЕДАКТИРОВАТЬ:

@ Дариус Бэкон: цитирует книгу «Красивый код» , в которой содержится объяснение, почему приведенный ниже код не является хорошей идеей.

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

Answer 5

Ответ в C # с использованием класса Vector2D

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

Обратите внимание, что

s * s

является точечным произведением вектора сегмента через перегрузку оператора в C #

Ключом является использование проекции точки на бесконечную линию и наблюдение, что скалярное количество проекции тривиально сообщает нам, находится ли проекция на отрезке или нет. Мы можем скорректировать границы скалярного количества, чтобы использовать нечеткий допуск.

Если проекция находится в пределах границ, мы просто проверяем, находится ли расстояние от точки до проекции в пределах границ.

Преимущество над подходом к нескольким продуктам заключается в том, что допуск имеет значимое значение.

Answer 6

Вы можете использовать произведение клина и точки:

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 7

Вот мое решение с C # в 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;
}

Answer 8

как насчет того, чтобы убедиться, что наклон одинаков и точка находится между остальными?

заданные точки (x1, y1) и (x2, y2) (при x2> x1) и балл кандидата (а, б)

если (b-y1) / (a-x1) = (y2-y2) / (x2-x1) и x1

Тогда (a, b) должно быть на линии между (x1, y1) и (x2, y2)