Find the coordinates of the triangle containing the largest number of points

So basically we have a list of x and y coordinate of points and we need to build a triangle, that will contain the largest number of points from this list.

I can check if this point is in the triangle area or not.

import math
points = [1, 0, 2, 0, 0, 0, 20, 0, 10, 30, 10, 15]

def getArea(x1, y1, x2, y2, x3, y3):
    return abs((x1 * (y2 - y3) + x2 * (y3 - y1)
                + x3 * (y1 - y2)) / 2.0)


def isIn(x1, y1, x2, y2, x3, y3, x, y):

    A = getArea(x1, y1, x2, y2, x3, y3)
    A1 = getArea(x, y, x2, y2, x3, y3)
    A2 = getArea(x1, y1, x, y, x3, y3)
    A3 = getArea(x1, y1, x2, y2, x, y)

    if A == A1 + A2 + A3:
        return True

    else:
        return False

>Solution :

You can use the built-in itertools.combinations() method:

from itertools import combinations

points = [1, 0, 2, 0, 0, 0, 20, 0, 10, 30, 10, 15]

def getArea(x1, y1, x2, y2, x3, y3):
    return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0)

def isIn(x1, y1, x2, y2, x3, y3, x, y):
    A = getArea(x1, y1, x2, y2, x3, y3)
    A1 = getArea(x, y, x2, y2, x3, y3)
    A2 = getArea(x1, y1, x, y, x3, y3)
    A3 = getArea(x1, y1, x2, y2, x, y)
    return A == A1 + A2 + A3

points = [points[i: i + 2] for i in range(0, len(points), 2)]

triangle = None
max_points = 0

for c in combinations(points, 3):
    new_points = [p for p in points if p not in c]
    (x1, y1), (x2, y2), (x3, y3) = c
    in_points = sum(1 for x, y in new_points if isIn(x1, y1, x2, y2, x3, y3, x, y))
    if in_points > max_points:
        max_points = in_points
        triangle = c

print(triangle)

Output:

([0, 0], [20, 0], [10, 30])

The method, itertools.combinations(iterable, r), returns r length subsequences of elements from the input iterable.

Note the small change in your isIn function, where the

    if A == A1 + A2 + A3:
        return True
    else:
        return False

can be replace with just

    return A == A1 + A2 + A3