Given a list of coordinates check if 4 points make a line

Question

I was doing some preparation for coding interviews and I came across the following question:

Given a list of coordinates "x y" return True if there exists a line containing at least 4 of the points (ints), otherwise return False.

The only solution I can think about is in \$O(n^2)\$. It consist of calculating the slope between every coordinate: Given that if \$\frac{y_2-y_1}{x_2 –x_1} = \frac{y_3-y_2}{x_3-x_2}\$ then these three points are on the same line. I have been trying to think about a DP solution but haven't been able to think about one.

Here is the current code:

def points_in_lins(l):
    length = len(l)
    for i in range(0,length -1):
        gradients = {}
        for j in range(i+1, length):
            x1, y1 = l[i]
            x2, y2 = l[j]
            if x1 == x2:
               m = float("inf")
            else:
               m = float((y2 -y1) / (x2 - x1))
            if m in gradients:
                gradients[m] += 1
                if gradients[m] == 3:
                   return(True)
            else:
                gradients[m] = 1

    return(False)

Actually, @W.Chang's suggestion of computing the area can indeed work for four points: if the first three points are collinear, try the first two with the fourth. The equation I use is (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) == 0 — Edward
– Edward, Commented Jul 24, 2018 at 19:37
@Edward: Wouldn't that require 3 (or 4) nested loops, instead of the current 2? — Martin R
– Martin R, Commented Jul 24, 2018 at 19:50
@MartinR: Yes, I believe it would. Whether that's faster or slower would depend on whether traversals are more or less expensive than the mathematical operations. — Edward
– Edward, Commented Jul 24, 2018 at 20:12

Cris Luengo · Accepted Answer · 2018-07-24 22:21:11Z

A different approach could be using the Hough transform. This does require that the points are in a bounded space, but would lead to an algorithm \$O(n)\$. This does not necessarily make it faster, but I think it will be significantly faster for large sets of points. It works this way:

Parameterize the potential lines in the input space using a distance from origin and an angle (typically, the angle is that of the normal line that goes through the origin).
Set up a "parameter space", a discretized space using distance and angle as its two axes. You need to choose a sampling here. Each bin in this space represents a potential line in the input space (or rather, a collection of lines, within a small range of angles and distances determined by the discretization of the parameter space).
For each point in the set, add 1 to each bin in the parameter space that represents a line going through this point. There is an infinite number of potential lines going through one point. These lines form a sinusoid in the parameter space, and it is quick to compute the set of bins covered by this sinusoid.
Each bin in the parameter space that has a value of 4 (or larger) represents the parameters of a line that covers 4 (or more) of the points. However, due to rounding of the parameters, it is possible these points are actually not collinear. To disambiguate, visit each point and determine which ones contributed to the bin in question, then verify they actually form a straight line.

Under a worst case scenario, all points contribute to the same bin, but are not actually on the same line. However, if this happens, the discretization of the parameter space was chosen incorrectly.

Note that this algorithm was invented to detect straight lines in an image, meaning that all input points have discrete coordinates. However, this is not a necessary requirement to apply the algorithm.

Should that step say "Parameterize points" instead of lines? — Edward
– Edward, Commented Jul 24, 2018 at 21:53
@Edward: no, lines in space are parameterized. Points belong to lines, for each point you have an infinite set of possible lines that go through it, you accumulate these possible lines. If one line is possible according to multiple points, than those points sit on the same line. — Cris Luengo
– Cris Luengo, Commented Jul 24, 2018 at 21:56
What I mean is that the algorithm begins with points. When you say lines, I am guessing you mean the line through each arbitrarily chosen pair of points. Correct? — Edward
– Edward, Commented Jul 24, 2018 at 22:02
Yes, lines are imaginary -- each point has an infinite number of possible lines going through it. All of those lines are accumulated in the transform space. — Cris Luengo
– Cris Luengo, Commented Jul 24, 2018 at 22:15
@Edward: I rewrote the explanation a little bit. Is it clearer now? — Cris Luengo
– Cris Luengo, Commented Jul 24, 2018 at 22:21

Martin R · Accepted Answer · 2018-07-26 10:00:37Z

General remarks

def points_in_lins(l):

The function and argument name can be improved. l is too short and does not indicate at all that this is a list of points, and points_in_lins (perhaps you meant points_in_line?) does not indicate that the function looks for four points in a line.

gradients is in fact a dictionary counting slopes.

Iterating over all pairs of points can be simplified with enumerate() and slices:

for idx, (x1, y1) in enumerate(l):
    gradients = {}
    for (x2, y2) in l[idx + 1:]:

The “set or increment” for gradients can be simplified with defaultdict or a Counter:

gradients = Counter()

# ...

gradients[m] += 1
if gradients[m] == 3:
    return True

The parentheses in return(True) and return(False) are not necessary:

return False

The math

Computing the slope as the quotient

m = (y2 - y1) / (x2 - x1)

requires a separate check for a zero denominator, but is problematic for another reason: Rounding errors can occur. As an example,

points_in_lins([(0, 300000000000000000), (1, 0), (1, 1), (1, 2)])

evaluates to True: The slopes from the first point to the other three points all evaluate to the same floating point number.

A possible fix is to compare the “directions” , i.e. the (2-dimensional) vectors between the two points, normalized in a way such that two vectors pointing in the same (or opposite direction) are considered equal.

If all coordinates are integers, then it is best to stick with pure integer calculations. Normalizing the connecting vector can be achieved by division by the greatest common divisor of the x- and y-component, and possibly mirroring it.

Putting it together

from math import gcd
from collections import Counter


def four_points_in_line(points):
    for idx, (x1, y1) in enumerate(points):
        direction_counts = Counter()
        for (x2, y2) in points[idx + 1:]:
            # Compute normalized direction from (x1, y1) to (x2, y2):
            delta_x, delta_y = x2 - x1, y2 - y1
            g = gcd(delta_x, delta_y)
            delta_x, delta_y = delta_x // g, delta_y // g
            if delta_x < 0 or (delta_x == 0 and delta_y < 0):
                 delta_x, delta_y = -delta_x, -delta_y
            # Three identical directions from (x1, y1) means 4 collinear points:
            direction_counts[(delta_x, delta_y)] += 1
            if direction_counts[(delta_x, delta_y)] == 3:
                return True
    return False

It is still a \$ O(n^2) \$ algorithm, but more robust against rounding and division by zero errors.

If the points are not guaranteed to be distinct then identical points need have to be treated separately.

An even better way of iterating through all pairs would be itertools.combinations(…, 2). — 200_success
– 200_success, Commented Jul 24, 2018 at 20:14
@200_success: I thought about that, but could not figure out how to reset/initialize gradients for each value of the first point. — Martin R
– Martin R, Commented Jul 24, 2018 at 20:17
Some remarks: gcd is found in fractions. While this ok with slicing I dislike idx running till the end when using idx+1 lateron. The special handling for identical points may be done by avoiding the divison by zero and counting gcd==0 an 'special direction' and then checking for direction_counts[direction] + (direction_counts[0] if direction else 0) == 3 (and avoiding — stefan
– stefan, Commented Jul 25, 2018 at 19:26
@stefan: As of Python 3.5, fractions.gcd() is deprecated in favor of math.gcd(). – I would prefer not to generate pairs of identical points in the first place instead of adding special code later to handle that situation. — Martin R
– Martin R, Commented Jul 25, 2018 at 19:34
I missed the introduction of math.gcd(), thanks. However math.gcd() differs from fractions.gcd(), it gives positive integers only. So your direction will not be normalized in terms of denominator sign. btw, my suggestion for handling of identical points is incomplete. better to count them in a dedicated variable and compare to 3 - identical_points. What I missed was to check direction_counts.most_common()[0][1] with new identical points. — stefan
– stefan, Commented Jul 26, 2018 at 9:38

Stack Exchange Network

Given a list of coordinates check if 4 points make a line

2 Answers 2

General remarks

The math

Putting it together

You must log in to answer this question.

Hot Network Questions

Given a list of coordinates check if 4 points make a line

2 Answers 2

General remarks

The math

Putting it together

You must log in to answer this question.

Related

Hot Network Questions