Generate valid triangles (convex) given list of points.

valid_triangles.py

import itertools, math

def dist(a, b):
    # 2d distance
    dx = a[0] - b[0]
    dy = a[1] - b[1]
    return math.sqrt(dx*dx + dy*dy)

def valid_triangle(t):
    # Check if triangle is valid (area > 0)
    a, b, c = dist(t[0], t[1]), dist(t[1], t[2]), dist(t[0], t[2]) # Sides
    s = (a + b + c) / 2 # Semiperimeter
    area = math.sqrt(s*(s-a)*(s-b)*(s-c)) # Heron formula
    return area > 0

def gen_valid_triangles(points):
    # Generate possible combinations of 3 points and filter for the valid ones
    return [t for t in itertools.combinations(sample_points, 3) if valid_triangle(t)]

sample_points = [
    (0, 4), (0, 3), (0, 2), (0, 1), (-4, 0), (-3, 0), (-2, 0), (-1, 0), 
    (0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (0, -1), (0, -2), (0, -3), (0, -4)
]
valid_triangles = gen_valid_triangles(sample_points)

print(len(valid_triangles)) # Print number of valid triangles