Python计算图形中三角形数量

rgewr2

                      看一个论坛里的.说如何用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']