DefectCut

使利用率最大化的破损石块裁剪算法

题目描述：

算法课上的一个作业，要求切割大石板（或者布料）使得利用率最大化；
大石板（或者布料）带有破洞；每切割一下就会把当前块一分为二；
大石板、需要裁出的小块、破洞，都在测试数据文件中；

算法思想：

1.对破洞全排列，对破洞的边全排，列依次切割，切割方式大概有(N!*4!)种；得出所有可用布料，
2.对每种切割等到的结果执行：
	1）为得到的每块可用布料匹配一块需要裁剪的布料，宽度最接近或者高度最接近为最匹配；
	2）在所有匹配，找出最匹配的，切割；
	3）切割时，高度差距小时，竖着切，宽度差距小时横着切，尽可能剩余大块布料；剩余布料放入可以布料中；
	4）返回1），直到没有可匹配的；
3.对比每种结果切割出的需要的布料，计算利用率，选利用率最大的为最终的切割方式；

访问地址

https://danicameng.github.io/DefectCut/

目录说明

example_old,example_new 先后提供的测试数据，由于两种文件格式不同，所以在页面不同位置引入

index.polymer.html 显示页面，由于使用了 Polymer，需要以网络访问方式来访问

js  js 源码文件
	class.js     实现类继承
	cloth.js     布料的定义和去破洞切割等
	cutExample.js  对布料进行切割使用等
	defined.js     点、线、公共函数等

polymer  Web UI 框架Polymer和组件
	example-card.html 一个测试实例的演示结果显示组件
	example-list.html 显示多个example-card的组件
    
运行截图.png :运行结果截图

疑问：

算法效率问题？
近乎穷举的做法效率不高，占用空间也大，但利用率是真的很高（zdfOG8,无破洞,96.57%;zdfOG11,有破洞，93.54%)。如果真的是切割时使用的话，计算一块石板的切割方法的时间和切割石板的时间比，是不足为虑的。

为什么选用javascript？
采用js实现算法，网页展示，仅仅是为了方便。当时有个nodejs项目，想用polymer，正在调研阶段，就顺便用了。

一次性执行多个文件时，显示串行问题？
以前显示没有任何问题。这次出现乱行，而且试着修改了几次，都没有达到预期目的，猜测是polymer问题，毕竟用的是三四年前的polymer了。不改了。添加一张以前的截图。