Pulpcode

捕获，搅碎，拼接，吞咽

0%

两个与长方体有关的算法

发表于 更新于 分类于 Valine：

之前的用用2d画个3d图形)，我说到过跟长方体有关的两个算法，(一个通过中心坐标长宽高求八个顶点，一个通过八个顶点求十二条边) ，但是那两个算法实在是太丑陋了，对于向我这种有强迫症的人简直不能忍受，所以我现在先把它们的算法用python描述出来，接着试着把它们变得更精巧，俗话说，代码就像女生的超短裙，越短越好…(虽然不知道是谁说的，但肯定是个男人)

算法1

通过一个中心坐标cen,和长方体的长宽高lwh，求出长房体的八个顶点 其实如果(x,y,z) = cen, (l,w,h) = lwh 我们的算法就是要求出x加减l,y加减w,z加减h然后在做一个组合,不过要注意位置不能变，所以一共有八个结果，这就是我们要求的八个顶点, 我的算法就是模仿八皇后，不过不需要回溯,递归到合适的值，把值保存起来。

1
2
3
4
5
6
7
8
9
10
11
12
def cubovers(cen,lwh):
    vertex = [None]*3
    res = []
    def ver(i):
	    if i == 3:
	        res.append(vertex[:])
	    else:
	        for x in [-1, 1]:
	 	        vertex[i] = cen[i] + x*lwh[i]/2.0
		    ver(i+1)
    ver(0)
    return res

其中for x in [-1, 1]: 就是分别求出了加和减,(做个乘法就行了)

算法2

第二个算法根据前面求出的顶点，计算出应该有的十二条边，这个算法说起来很简单，找出顶点集合中三个坐标中有两个相等的，那么它们之间就有一条连线。

所以我们先要写一个函数来判断两个点是否是共线（在长方体）

1
2
3
4
5
6
7
8
def same2(ver1, ver2):
    for i in range(3):
    	for j in range(3):
	        if i == j:
		        continue
	        if ver1[i] == ver2[i] and ver1[j] == ver2[j]:
		        return True
    return False

我们要小心三个都相等，那就成同一个点了。
之后，求线算法就调用此函数来判断是否符合并把它们保存起来.

1
2
3
4
5
6
7
8
9
def cubolines(vers):
    res = []
    for i in vers:
	    for j in vers:
	        if i == j:
		        continue
	        if same2(i, j):
		        res.append([i,j])
    return res

再短一点，再细一点———孙悟空

我们的代码之所以看上去那么长，是因为没有很好的处理遍历集合，如果你能很好的写出你想要的遍历方式，那么你的代码会变得非常漂亮，而且有的时候，你以为自己写的代码已经很漂亮了，但是很可能另一个人的代码就会让你自叹不如，python就是这样，如果你只是把这些可跌代对象当c语言中的数组使，肯定会让代码变得跟c语言一样长，

下面我用yield，闭包，和新的遍历方式重写这两个算法，使它们更短，如果哪位大神能写出更短的比如用什么itertools，求指点呀！

求顶点的算法:

1
2
3
4
5
6
7
8
9
10
def cubovers(cen, lwh):
    def vers(i):
        for x in [-1, 1]:
            p = cen[i] + x*lwh[i]/2.0
            if i == 2:
                yield (p,)
            else :
                for rs in vers(i+1):
                    yield (p,)+rs
    return list(vers(0))

说明

因为使用了yield所以不需要一个列表保存结果了，中间变量也不需要用参数传递，而且我还是用了闭包，因为cen和lwh我并不想在参数中传递，这样看上去会很舒服。返回的时候返回list(vers(0))，因为yield返回的算是一种佚代器

求边线的算法

1
2
3
4
5
def same2(ver1,ver2):
    for i in range(3):
    	if ver1[:i]+ver1[i+1:] == ver2[:i] + ver2[i+1:]:
	        return True
    return False

same2看上去比以前短了，因为新的方式佚代出我想要的元素，比如用了切片

cubolines

1
2
def cubolines(vers):
    return [[vers[i],t] for i in range(len(vers)) for t in vers[i+1:] if same2(vers[i],t)]

cubolines只用了一行，看上去会有点难，我返回了一个列表推导式，其实内部就是对一个列表中的元素作了个组合运算，