Finding all the triangles possible out of coordinates (python)

Question

Hello everyone i am new here. So far i have had a lot of information from StackOverflow so thanks everyone.

I got 6 coördinates:

A: (4,2) B: (6,1) C: (9,4) D: (8,9) E: (5,2) F: (2,2)

And i have a measured position, lets say P=(3,7)

I want to find out all the combinations of points that can make a triangle that will cover the position P. I already have a code to calculate if a position is within a triangle:

# A utility function to calculate area
# of triangle formed by (x1, y1),
# (x2, y2) and (x3, y3)

def area(x1, y1, x2, y2, x3, y3):

    return abs((x1 * (y2 - y3) + x2 * (y3 - y1)
                + x3 * (y1 - y2)) / 2.0)


# A function to check whether point P(x, y)
# lies inside the triangle formed by
# A(x1, y1), B(x2, y2) and C(x3, y3)
def isInside(x1, y1, x2, y2, x3, y3, x, y):

    # Calculate area of triangle ABC
    A = area (x1, y1, x2, y2, x3, y3)

    # Calculate area of triangle PBC
    A1 = area (x, y, x2, y2, x3, y3)
    
    # Calculate area of triangle PAC
    A2 = area (x1, y1, x, y, x3, y3)
    
    # Calculate area of triangle PAB
    A3 = area (x1, y1, x2, y2, x, y)
    
    # Check if sum of A1, A2 and A3
    # is same as A
    if(A == A1 + A2 + A3):
        return True
    else:
        return False

# Driver program to test above function
# Let us check whether the point P(10, 15)
# lies inside the triangle formed by
# A(0, 0), B(20, 0) and C(10, 30)
if (isInside(0, 0, 20, 0, 10, 30, 10, 15)):
    print('Inside')
else:
    print('Not Inside')

But in this way I have to make all the triangles one by one. I am looking for a way to calculate all the triangles that cover point P.

As extra information, the goal of the script is to do a triangle interpolation to determine the wind speed at point P.

Could anyone help me with this? I really cant find out how to use all the possible combinations.

Kind regards,

Simon

some notes: *using Anaconda *using Spyder *I am capable of using modules

Answer 1

Nice to see that you have put some effort in your code already.

You can use combinations from itertools [1] to create triangles:

import itertools
data = ['p1', 'p2', 'p3', 'p4', 'p5']

triangles = itertools.combinations(data, 3) 
print(*triangles, sep='\n')

Output:

('p1', 'p2', 'p3')
('p1', 'p2', 'p4')
('p1', 'p2', 'p5')
('p1', 'p3', 'p4')
('p1', 'p3', 'p5')
('p1', 'p4', 'p5')
('p2', 'p3', 'p4')
('p2', 'p3', 'p5')
('p2', 'p4', 'p5')
('p3', 'p4', 'p5')

Triangles is a generator. You can use your code to go over each triangle and check your existing code to check if point P is inside a triangle.

in this case I used strings as elements, but you can also use tuples:

import itertools
data = [(0,0), (1,1), (2,2), (2,3)]

triangles = itertools.combinations(data, 3) 
print(*triangles, sep='\n')

((0, 0), (1, 1), (2, 2))
((0, 0), (1, 1), (2, 3))
((0, 0), (2, 2), (2, 3))
((1, 1), (2, 2), (2, 3))

You can for exmample use this part of code as a starting point:

import itertools

points = [(4,2), (6,1), (9,4), (8,9), (5,2), (2,2)]

P = (3,7)

for triangle in itertools.combinations(points, 3):
    p1, p2, p3 = triangle
    if isInside(*p1, *p2, *p3, *P):
        print(f"P {P} is in triangle: {triangle}")
    else:
        print(f"P {P} is NOT in triangle: {triangle}")

[1] https://docs.python.org/3/library/itertools.html#itertools.combinations