Проверьте, все ли точки в наборе лежат на одной линии

Question

Мне дан список с координатами n точек, скажем:

points = [(1, 2), (2, 3), (3, 4)]

И мне нужно проверить, все ли они лежат на одной линии. Я также решил рассмотреть 3 случая, чтобы избежать деления на ноль при x1 == x2. Итак, вот мой код на Python:

# 2 points always lie on a line
if n <= 2:
    print("yes")
else:
    # leave only unique points
    points = list(set(points))
    x1, y1 = points[0]
    x2, y2 = points[1]

    # if two points have the same x coordinate
    # then they lie on a vertical line and
    # all other points have to have the same x coordinate too
    if x2 == x1:
        for i in range(2, len(points)):
            if points[i][0] != x1:
                print("no")
                break
        else: print("yes")

    # same with a horizontal line
    elif y2 == y1:
        for i in range(2, len(points)):
            if points[i][1] != y1:
                print("no")
                break
        else: print("yes")

    else:
        a = (y2-y1)/(x2-x1)
        b = y2 - a * x2

        for i in range(2, len(points)):
            x, y = points[i]
            if (y != a * x + b):
                print("no")
                break
        else: print("yes")

Кажется, что-то в коде есть ошибка, но я не совсем понимаю, что это такое.

Answer 1

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

import math

class Point:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __sub__(self, other):
        return Vector(self.x - other.x, self.y - other.y)

class Vector:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def cross(self, other):
        return self.x * other.y - self.y * other.x

def are_collinear(three_points):
    a, b, c = three_points  
    # better use math.isclose than == to check for floats
    return math.isclose((b-a).cross(c-a), 0.0)

points = [Point(1, 2), Point(2, 3), Point(3, 4)]
print(are_collinear(points))
# True


points = [Point(1, 2), Point(3, 3), Point(3, 4)]
print(are_collinear(points))
# False

Answer 2

Из любой точки списка (например, первой), если все остальные точки имеют одинаковый наклон с этой точкой, то они находятся на одной линии.

def sameLine(points):
    x0,y0  = points[0]
    points = [ (x,y) for x,y in points if x != x0 or y != y0 ]      # Other points
    slopes = [ (y-y0)/(x-x0) if x!=x0 else None for x,y in points ] # None for vertical Line
    return all( s == slopes[0] for s in slopes)