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

Question

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

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

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

Answer 1

Проверьте, равняется ли перекрестное произведение из (b-a) и (c-a) 0, как говорит Дариус Бэкон, сообщает ли выровненные точки a, b и c.

Но, как вы хотите знать, если c находится между a и b, вы также должны проверить, что точечное произведение из (ba) и (ca) равно положительное и на меньше , чем квадрат расстояния между a и b.

В неоптимизированном псевдокоде:

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

Вот как бы я это сделал:

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

Проверьте, является ли перекрестное произведение b-a и c-a 0: это означает, что все точки коллинеарны. Если это так, проверьте, находятся ли координаты c между a и b. Используйте координаты x или y, если a и b разделены на этой оси (или одинаковы на обеих).

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

Этот ответ раньше был беспорядком из трех обновлений. Полезная информация от них: глава Брайана Хейса в Beautiful Code охватывает пространство разработки для функции проверки коллинеарности - полезный фон. Ответ Винсента помог улучшить этот. И именно Хейс предложил проверить только одну из координат x или y; Первоначально код имел and вместо if a.x != b.x else.

Answer 4

Вот еще один подход:

• Предположим, что две точки: A (x1, y1) и B (x2, y2)
• Уравнение линии, проходящей через эти точки: (x-x1) / (y-y1) = (x2-x1) / (y2-y1) .. (просто приравнивая наклоны)

Точка C (x3, y3) будет лежать между A и B, если:

• x3, y3 удовлетворяет приведенному выше уравнению.
• x3 лежит между x1 & x2 и y3 лежит между y1 & y2 (тривиальная проверка)

Answer 5

Длина сегмента не важна, поэтому использование квадратного корня не требуется, и его следует избегать, поскольку мы можем потерять некоторую точность.

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)

Случайный пример использования:

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)

Answer 6

Вот другой способ сделать это с помощью кода, приведенного на C ++. Учитывая две точки, l1 и l2, тривиально выразить отрезок между ними как

l1 + A(l2 - l1)

где 0 <= A <= 1. Это называется векторным представлением линии, если вас больше интересует не только использование ее для этой задачи. Мы можем разделить x и y компоненты этого, давая: </p>

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

Возьмите точку (x, y) и подставьте ее компоненты x и y в эти два выражения, чтобы решить для A. Точка находится на прямой, если решения для A в обоих выражениях равны и 0 <= A <= 1. Поскольку решение для A требует деления, есть особые случаи, которые требуют обработки, чтобы остановить деление на ноль, когда отрезок линии горизонтален или вертикальн. Окончательное решение выглядит следующим образом: </p>

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

Хорошо, много упоминаний о линейной алгебре (перекрестное произведение векторов), и это работает в реальном (т. Е. В непрерывной или с плавающей запятой) пространстве, но в вопросе конкретно указано, что две точки были выражены как целые числа и, следовательно, перекрестное произведение не является правильным решением, хотя оно может дать приблизительное решение.

Правильное решение - использовать Алгоритм линии Брезенхема между двумя точками и посмотреть, является ли третья точка одной из точек на линии. Если точки достаточно далеки, чтобы вычисление алгоритма было неэффективным (и это должно быть очень большим, чтобы это имело место), я уверен, что вы могли бы покопаться и найти оптимизацию.

Answer 8

Используя более геометрический подход, вычислите следующие расстояния:

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)

и проверьте, равняется ли ac + bc ab :

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

Это потому, что есть три возможности:

• 3 точки образуют треугольник => ac + bc> ab
• Они коллинеарны и c находится вне сегмента ab => ac + bc> ab
• Они коллинеарны и c находится внутри ab сегмента => ac + bc = ab

Answer 9

Мне нужно было это для javascript для использования на холсте html5 для определения, был ли курсор пользователя над определенной линией или рядом с ней. Поэтому я изменил ответ Дария Бэкона на coffeescript:

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

Answer 10

Скалярное произведение между (c-a) и (b-a) должно быть равно произведению их длин (это означает, что векторы (c-a) и (b-a) выровнены и имеют одинаковое направление). Кроме того, длина (с-а) должна быть меньше или равна длине (б-а). Псевдокод:

# 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