看一个论坛里的.说如何用python计算图形中三角形的数量. 图如下:
论坛那位兄弟是先把所有的边上的点放到一个list里面. 然后去生成相关组合.
再去判断点的位置正确与否.
所有的点组合list:
|
1
|
[
'abh'
,
'acgi'
,
'adfj'
,
'aek'
,
'bcde'
,
'efgh'
,
'hijk'
]
|
下图中三个框分别为三条线上的点集合.由图可知,要构成三角形必须三个集合两两之间取
交集得到相应的点.
任意两个集合的交集.为一个点. 用itertools的组合方法生成三个集合的组合
再两个之间取交集得到相应的点.即为相应结果.
代码如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#!/usr/bin/env python
import
itertools
a
=
[
'abh'
,
'acgi'
,
'adfj'
,
'aek'
,
'bcde'
,
'efgh'
,
'hijk'
]
a
=
[
set
(i)
for
i
in
a ]
def
CounterTri():
k
=
[]
for
x
in
itertools.combinations(a,
3
):
o, p, q
=
x[
0
] & x[
1
], x[
1
] & x[
2
], x[
2
] & x[
0
]
if
bool
(o)
and
bool
(p)
and
bool
(q)
and
o !
=
p !
=
q:
k.append(
list
(o | p | q))
print
"Triangle Counter is %s"
%
len
(k)
for
i
in
k:
print
i
CounterTri()
|
结果如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
$ python ttt.py
Triangle Counter
is
24
[
'a'
,
'c'
,
'b'
]
[
'a'
,
'h'
,
'g'
]
[
'a'
,
'i'
,
'h'
]
[
'a'
,
'b'
,
'd'
]
[
'a'
,
'h'
,
'f'
]
[
'a'
,
'h'
,
'j'
]
[
'a'
,
'b'
,
'e'
]
[
'a'
,
'h'
,
'e'
]
[
'a'
,
'h'
,
'k'
]
[
'h'
,
'b'
,
'e'
]
[
'a'
,
'c'
,
'd'
]
[
'a'
,
'g'
,
'f'
]
[
'a'
,
'i'
,
'j'
]
[
'a'
,
'c'
,
'e'
]
[
'a'
,
'e'
,
'g'
]
[
'a'
,
'i'
,
'k'
]
[
'c'
,
'e'
,
'g'
]
[
'i'
,
'h'
,
'g'
]
[
'a'
,
'e'
,
'd'
]
[
'a'
,
'e'
,
'f'
]
[
'a'
,
'k'
,
'j'
]
[
'e'
,
'd'
,
'f'
]
[
'h'
,
'j'
,
'f'
]
[
'h'
,
'k'
,
'e'
]
|
本文转自 nonono11 51CTO博客，原文链接：http://blog.51cto.com/abian/1677905，如需转载请自行联系原作者
