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

данный точки (x1, y1) и (x2, y2) (с x2> x1) и точку кандидата (a, b)

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

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

Скалярное произведение между (c-a) и (b-a) должно быть равно продукту их длин (это означает, что векторы (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

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

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

@Darius Bacon: цитирует "Красивый Код" книга , которая содержит объяснение, почему любимый код не является хорошей идеей.

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

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

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

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

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)

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

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

Вот другой подход:

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

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

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

Проверьте, ли векторное произведение 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

Этот ответ раньше был путаницей трех обновлений. Стоящая информация от них: Brian Hayes глава в [1 113] Красивый Код покрытия пространство дизайна для функции теста коллинеарности - полезный фон. ответ Vincent помог улучшить этого. И это был Hayes, кто предложил тестировать только один из x или координат y; первоначально код имел and вместо [1 110].