检查三角形的几何图形是否包含在直线列表中

Question

我有一个线列表 Lines=([('B', 'C'), ('D', 'A'), ('D', 'C'), ('A', 'B'), ('D', 'B')])，geometry = ('B', 'C', 'D') 是一个点列表，这些点构成了三角形 (B,C,D)。

我想检查是否可以从 Lines 中的行列表中设置 geometry。我如何创建一个函数来检查该状态？ 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

Answer 1

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

好的，我将使用字符串作为答案，您应该能够根据需要调整代码。

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') 与 ('B', 'A').

是同一行

Answer 2

对于三角形：

您可以使用 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)

现在您可以调用 all，它将检查 dataE 中的每个值是否存在于 sLines 中：

all(l1 in sLines for l1 in dataE)

哪个会 return 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：check_geometry的geometry参数可以是任何可迭代的（元组、列表、字符串）：

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

在这种情况下创建并传递 tuple 似乎有些奇怪（唉，您可能有充分的理由这样做）。除非原因需要，否则我建议使用字符串作为参数 geometry.

的值

检查三角形的几何图形是否包含在直线列表中

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

python

python-2.7

computational-geometry

对于三角形：

更一般一点：