Checking that the geometry for a triangle is contained in a list of lines

Question

I have a list of lines Lines=([('B', 'C'), ('D', 'A'), ('D', 'C'), ('A', 'B'), ('D', 'B')]) and geometry = ('B', 'C', 'D') is a list of points that set up the triangle (B,C,D).

I want to check whether geometry can be set up from list of lines in Lines. How can I create a function to check that status? True or False.

Sample Functionality with input Lines:

>> Lines=([('B', 'C'), ('D', 'A'), ('D', 'C'), ('A', 'B'), ('D', 'B'),])
>> geometry1 = ('B', 'C', 'D')
>> check_geometry(Lines, geometry1)
   True
>> geometry2 = ('A', 'B', 'E')
>> check_geometry(Lines, geometry2)
   False

This is my code, but the result is wrong:

import itertools

def check_geometry(line, geometry):
    dataE = [set(x) for x in itertools.combinations(geometry, 2)]
    for data in dataE:
       if data not in line:
           return False
    return True 

Lines = [('B', 'C'), ('D', 'A'), ('D', 'C'), ('A', 'B'), ('D', 'B'),]
geometry1 = ('B', 'C', 'D')
print check_geometry(Lines, geometry1)

Output:

False

Answer 1

For triangles:

You could use the built-in all to do this, making sure to first sort the list contents since their order might differ than that generated from itertools.combinations:

sLines = [tuple(sorted(l)) for l in Lines]
dataE = itertools.combinations('BCD', 2)

Now you can call all which will check that every value in dataE is present in sLines:

all(l1 in sLines for l1 in dataE)

Which will return True.

So, your check_geometry function could look something like:

def check_geometry(line, geometry):
    sLines = [tuple(sorted(l)) for l in line]
    dataE = itertools.combinations(geometry, 2)
    return all(l1 in sLines for l1 in dataE) 

Calls made will now check if the Lines contain the geometry:

check_geometry(Lines, 'BCD')
# returns True

check_geometry(Lines, 'ABE')
# returns False

---

A bit more general:

To generalize this a bit, we can drop itertools.combinations and instead utilize zip. The following makes some appropriate changes to the function in order to acommodate zip but performs similar stuff:

def check_geometry(line, geometry):
    sLines = [sorted(l) for l in line]
    dataE = [sorted(x) for x in zip(geometry, geometry[1:] + geometry[:1])] 
    return all(l1 in sLines for l1 in dataE)

The key difference here is:

dataE is now a list of lists containing the result of zip(geometry, geometry[1:] + geometry[:1]). What zip does in this case is it takes a string like "BCDA" and the same string with the first element added to the end geometry[1:] + geometry[:1] (i.e "CDAB") and creates entries signifying the sides of a shape:

>>> s = "BCDA"

>>> s[1:] + s[:1]
>>> 'CDAB'

>>> list(zip(s, s[1:] + s[:1]))
[('B', 'C'), ('C', 'D'), ('D', 'A'), ('A', 'B')]

Now we can check that a geometry with points "BCDA" can be constructed by the lines in Lines:

check_geometry(Lines, "BCD")
# True

check_geometry(Lines, "BCDA")
# True

check_geometry(Lines, "BCDF")
# False

---

Note 1: Lines can be written as:

Lines=[('B', 'C'), ('D', 'A'), ('D', 'C'), ('A', 'B'), ('D', 'B')]

The parenthesis () and comma , have no additional effect here, you can drop them :-) .

Note 2: The geometry parameter for check_geometry can be any iterable (tuples, lists, strings):

check_geometry(lines, "BCD") == check_geometry(lines, ('B', 'C', 'D'))

Creating and passing a tuple to it seems somewhat odd in this case (alas, you might have a good reason to do so). Unless reasons require it, I would suggest going with strings as the value for parameter geometry.

Answer 2

I think A,B,C can be string or whatever which define a point that set up a line

Okay, I'll be using strings for my answer then, you should be able to adjust the code to your needs.

def check_for_triangle(tri, lines):
    lines_needed = zip(tri, (tri[1], tri[2], tri[0]))
    return all(line in lines or line[::-1] in lines for line in lines_needed)

lines=[('B', 'C'), ('D', 'A'), ('D', 'C'), ('A', 'B'), ('D', 'B')]
tri1 = ('B', 'C', 'D')
tri2 = ('A', 'B', 'E')

print(check_for_triangle(tri1, lines)) # True
print(check_for_triangle(tri2, lines)) # False

The idea is to generate all lines (represented by a pair of points) we need to find in lines for a given triangle with zip. After that, we check whether all these lines can be found in lines. Checking for line[::-1] as well is needed because the line ('A', 'B') is the same line as ('B', 'A').