Проверка того, что геометрия треугольника содержится в списке линий

У меня есть список линий Lines=([('B', 'C'), ('D', 'A'), ('D', 'C'), ('A', 'B'), ('D', 'B')]) и geometry = ('B', 'C', 'D') - это список точек, которые образуют треугольник (B,C,D).

Я хочу проверить, можно ли настроить geometry из списка строк в Lines. Как я могу создать функцию для проверки этого статуса? True или False.

Пример функциональности с входными строками: 

>> 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

Это мой код, но результат неверный: 

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)

Вывод: 

False
2 5
python python-2.7 computational-geometry

2 ответа:

Для треугольников:

Вы можете использовать встроенный all для этого необходимо сначала отсортировать содержимое списка, так как их порядок может отличаться от порядка, сгенерированного из itertools.combinations:

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

Теперь вы можете вызвать all, который проверит, что каждое значение в dataE присутствует в sLines: 

all(l1 in sLines for l1 in dataE)

Который вернется True.

Итак, ваша функция check_geometry может выглядеть примерно так: 

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)

Звонки сделаны будут сейчас проверьте, содержат ли Lines geometry: 

check_geometry(Lines, 'BCD')
# returns True

check_geometry(Lines, 'ABE')
# returns False

Чуть более общее:

Чтобы немного обобщить это, мы можем отбросить itertools.combinations и вместо этого использовать zip. Следующее вносит некоторые соответствующие изменения в функцию, чтобы аккомодировать zip , но выполняет аналогичные вещи: 
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)

Ключевое различие здесь:

dataE теперь это список списков, содержащих результат zip(geometry, geometry[1:] + geometry[:1]). То, что zip делает в этом случае, это берет строку типа "BCDA" и ту же строку с первым элементом, добавленным в конец geometry[1:] + geometry[:1] (то есть "CDAB"), и создает записи, обозначающие стороны фигуры: 

>>> s = "BCDA"

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

>>> list(zip(s, s[1:] + s[:1]))
[('B', 'C'), ('C', 'D'), ('D', 'A'), ('A', 'B')]
Теперь мы можем проверить, что геометрия с точками "BCDA" может быть построена линиями в Lines: 
check_geometry(Lines, "BCD")
# True

check_geometry(Lines, "BCDA")
# True

check_geometry(Lines, "BCDF")
# False

Примечание 1: Lines может быть записано как: 

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

Скобки () и запятая , здесь не имеют дополнительного эффекта, их можно отбросить :-) .

Примечание 2 : параметр geometry для check_geometry может быть любым iterable (кортежи, списки, строки): 

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

Создание и передача tuple ему кажется несколько странным в этом случае (увы, у вас может быть хорошая причина для этого). Если этого не требуют причины, я бы предложил использовать строки в качестве значения параметра geometry.

3

Я думаю, что A, B, C могут быть строкой или чем угодно, определяющим точку, которая задает линию

Хорошо, я буду использовать строки для моего ответа, тогда вы сможете настроить код под свои нужды. 
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
Идея состоит в том, чтобы сгенерировать все линии (представленные парой точек), которые мы должны найти в lines для данного треугольника с zip. После этого мы проверяем, можно ли найти все эти строки в lines. Проверка на line[::-1] также необходима, потому что строка ('A', 'B') одинакова строка as ('B', 'A').
3