CODEWITHSUNDEEP
pythongeometry
Some student
Some student

Reputation: 131

Check if all points in a set lie on the same line

I'm given a list with coordinates of n points, let's say:

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

And I need to check if all of them lie on the same line. I also decided to consider 3 cases to avoid dividing by zero when x1 == x2. So here's my code in 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")

It seems that I have a mistake somewhere in the code but I don't really understand what it is.

Upvotes: 1

Views: 5227

Answers (2)

Alain T.
Alain T.

Reputation: 42129

From any point in the list (e.g. first one) if all other points have the same slope with that one, then they are on the same line.

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)

Upvotes: 0

Reblochon Masque
Reblochon Masque

Reputation: 36732

Using cross product of vectors eliminates the complexity of having to deal with special cases where division by zero might happen. Three points are collinear if the cross product of the vectors formed by the two vectors defined by the 3 points is equal to zero:

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

Upvotes: 1

Related Questions