Loops, Geometry
You could write this so that you could compare every combination of three points and see if they are on the same line. This would result in O(n ** 3) performance.
def sameline(pts):
"""Find segments comprising >2 points."""
# START SOLUTION
# The runtime of this is fixed by the combinations of points;
# for (n choose 3); it grows as O(n ** 3)
out = []
for p1, p2, p3 in itertools.combinations(pts, 3):
x1, y1 = p1
x2, y2 = p2
x3, y3 = p3
# Check if these three points are on a line
if (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2):
out.append([p1, p2, p3])
return out
This gets all 3-points combinations and uses a simple geometric test if they are on the same line.
A terser, functional-style version of this logic could be:
def sameline_functional(pts):
"""Find segments comprising >2 points."""
# The runtime of this is fixed by the combinations of points;
# for (n choose 3); it grows as O(n ** 3)
return [([p1, p2, p3])
for p1, p2, p3 in itertools.combinations(pts, 3)
if ((p1[1] - p2[1]) * (p1[0] - p3[0]) ==
(p1[1] - p3[1]) * (p1[0] - p2[0]))]
You can do this in a much better runtime, O(n ** 2), by comparing every combination of two points, and keeping track of the discovered slope in a set. Then, if you find another combination with the same slope, you know it would be on the same point:
def sameline_quadratic(pts):
"""Find segments comprising >2 points."""
# The runtime of this is fixed by the combinations of points;
# for (n choose 2), it grows as O(n ** 2)
# Dictionary of slope-info mapped to sets of points.
#
# In geometry, any line can be represented by the eqn y = mx + b;
# we can calculate m (slope) and b (intercept) for two points and
# keep track of those points in a dict using (m,b) for the key.
# make slopes a dictionary where values default to being an empty set
slopes = defaultdict(set)
# Compare all p1,p2 combinations of points
for p1, p2 in itertools.combinations(pts, 2):
x1, y1 = p1
x2, y2 = p2
# Find slope & y-intercept, avoiding div-by-zero for vertical lines
if x2 - x1:
slope = float(y2 - y1) / float(x2 - x1)
y_intercept = y1 - (slope * x1)
else:
slope = "vertical"
y_intercept = x1
# Add both points to the slopes dictionary
slopes[slope, y_intercept].add(p1)
slopes[slope, y_intercept].add(p2)
return [pts for pts in slopes.values() if len(pts) > 2]
This is much preferred — if we have 500 points, an O(n ** 2) solution would check 124,750 points (that’s “500 choose 2”), whereas our O(n ** 3) solution would need to check 20,708,500 points (“500 choose 3”).