(Python) Script to determine if (x, y) coordinates

问题:

like the title says, I'm trying to write a program that takes a list of (x, y) coordinates, and determines if any 3 points are collinear (lie on a line with the same slope)

I'm getting some error messages. As it stands, I get an "TypeError: 'int' object is not subscriptable" message. If I take out the part where collinearityTest calls on the areCollinear function, I get an "index out of range" error. I'm new to python, and just trying to learn.

def areCollinear(p1, p2, p3):
    slope1 = (p2[1] - p1[1]) / (p2[0] - p1[0])
    slope2 = (p3[1] - p2[1]) / (p3[0] - p2[0])
    if slope1 == slope2:
        print "Points are colinear"
    else:
        print "Points are NOT colinear, what's the matter with you?"

def collinearityTest(pointList):
    position = 0
    while position >=0 and position < len(pointList):

        for p1 in pointList[position]:
            position = position + 1
            for p2 in pointList[position]:
                position = position + 1
                for p3 in pointList[position]:
                    position = position + 1
                    areCollinear(p1, p2, p3)

pointList = [(10, 20), (55, 18), (10, -45.5), (90, 34), (-34, -67), (10, 99)]

collinearityTest(pointList)

ERROR MESSAGE:

Traceback (most recent call last):
  File "C:\Program Files (x86)\Wing IDE 101 4.1\src\debug\tserver\_sandbox.py", line 23, in <module>
  File "C:\Program Files (x86)\Wing IDE 101 4.1\src\debug\tserver\_sandbox.py", line 19, in collinearityTest
  File "C:\Program Files (x86)\Wing IDE 101 4.1\src\debug\tserver\_sandbox.py", line 2, in areCollinear
    if __name__ == '__main__':
TypeError: 'int' object is not subscriptable

回答1:

Here's an easier and numerically more robust and stable function to test the collinearity of three points:

def collinear(p0, p1, p2):
    x1, y1 = p1[0] - p0[0], p1[1] - p0[1]
    x2, y2 = p2[0] - p0[0], p2[1] - p0[1]
    return abs(x1 * y2 - x2 * y1) < 1e-12

(Note that it would be best not to hard-code the epsilon, and to make it relative to the length of the vectors.)

回答2:

The Error

The main error is that you are trying to access part of the int object, but it is not possible. You can reproduce similar error like this:

>>> p1 = 1
>>> p1[1]
Traceback (most recent call last):
  File "<pyshell#12>", line 1, in <module>
    p1[1]
TypeError: 'int' object is not subscriptable

Other problems

You have several problems with your code, especially two come in mind:

1. Divisions (you are not using Python 3.x, so / works in a way different than you want, eg. the following is true: 3/2==1 - you should use divisions involving floats or at least use from __future__ import division),
2. Three levels of loops - this is bad idea because of complexity, just use itertools.combinations instead.

Framework for improvements

You should just do something like:

import itertools

for x, y, z in itertools.combinations(pointList, 3):
    # Check if x, y and z lie on the same line,
    # where x, y and z are tuples with two elements each.
    # And remember to use floats in divisions
    # (eg. `slope1 = float(p2[1] - p1[1]) / (p2[0] - p1[0])`)
    pass

回答3:

Your code could be much cleaner:

import itertools

def arecolinear(points):
    xdiff1 = float(points[1][0] - points[0][0])
    ydiff1 = float(points[1][1] - points[0][1])
    xdiff2 = float(points[2][0] - points[1][0])
    ydiff2 = float(points[2][1] - points[1][1])

    # infinite slope?
    if xdiff1 == 0 or xdiff2 == 0:
        return xdiff1 == xdiff2
    elif ydiff1/xdiff1 == ydiff2/xdiff2:
        return True
    else:
        return False

pointlist = [(10, 20), (55, 18), (10, -45.5), (90, 34), (-34, -67), (10, 99)]

for points in itertools.combinations(pointlist, 3):
    if arecolinear(points):
        print("Points are colinear")
    else:
        print("Points are NOT colinear")

回答4:

So you want to have 3 for loops and each of them are iterating through the same list of points. Then why do you have the while loop? Just remove it. It's needless in this case.

Furthermore; pointList[position] is a 2d tuple, e.g (10,20). And by writing for p1 in pointList[position], you are trying to iterate over that tuple. What you want is to iterate over the list. So try for p1 in pointList instead. I.e., remove the angle brackets to iterate over the list, not the tuple. Therefore; you don't need to keep track of position as well.

So it becomes

for p1 in pointList:
  for p2 in pointList:
    for p3 in pointList:
        #do something with p1 p2 p3

Tip: You might also consider having areCollinear function return a boolean value instead of printing something. Doesn't really change the functionality but it's a better practice, as it makes your function reusable somewhere else later on.

回答5:

I would use itertools.combinations(), but since you're trying to learn Python, here's your basic problem: you're going a level deeper into pointList than you need to.

Modified function:

def collinearityTest(pointList):
    for p1 in pointList:
        for p2 in pointList:
            if p2 is p1:
                continue
            for p3 in pointList:
                if p3 is p2 or p3 is p1:
                    continue
                areCollinear(p1, p2, p3)

for p1 in pointList will give you each item in pointList. That's exactly what you want. You could also do this with indexes (pointList[index]) if you like.

Again, go for itertools.combinations().

回答6:

There are some problems with the other answers, such as checking for divide by zero. Here's my solution that uses the "All" Python feature and can check a point list of any length:

def collinear(Points):
    '''Accepts [(x1, y1), (x2, y2), ...] and returns true if the 
    points are on the same line.'''
    ERR=1.0e-12
    if len(Points)<3:
        return True
    x1, y1 = Points[0]
    x2, y2 = Points[1]
    if x2==x1:
        raise Exception("points are not a function")
    m=(y2-y1)/(x2-x1)
    return all([abs(m*(xi-x1)-yi+y1)<ERR for xi,yi in Points[2:]])