最小有向外接矩形算法的CUDA并行实现的中期报告.docx

最小有向外接矩形算法的CUDA并行实现的中期报告
1.项目背景
最小有向外接矩形（Minimumboundingbox）是计算机图形学、计算几何中一个重要的问题，它是指一个点集或一个图形的有向外接矩形面积最小的矩形。在求解最小有向外接矩形问题中，传统的算法时间复杂度较高，难以满足实时性要求，因此利用GPU进行加速是一种可行的解决方案。本项目的目的在于使用CUDA并行实现求解最小有向外接矩形的算法，并对比传统算法进行性能评测，从而验证并行化算法的加速效果。
2.技术路线
本项目将使用CUDA进行并行加速，实现最小有向外接矩形的算法。具体涉及以下内容：
按照研究计划的目标，设计和实现所需的最小有向外接矩形算法，包括串行、并行两种算法实现。
通过可视化、数据使用等方式进行算法测试，对比两种算法在时间和空间、精度等方面的异同。
在算法设计的基础上，对实验结果进行比较分析。
3.已完成工作
-确定最小有向外接矩形的串行算法实现方案；
-确定最小有向外接矩形的CUDA并行算法实现方案；
-完成了串行算法的代码实现；
-完成了CUDA并行算法的框架代码实现；
-构建数据集，完成了对串行算法和CUDA并行算法实现结果的可视化比较；
-完成了对实验结果的初步分析。
4.下一步工作
-完成CUDA并行算法的具体实现；
-使用实验数据进行完整的测试，并进行详细分析；
-经数据分析后，对比两种算法在时间和空间、精度等方面的异同；
-完成最小有向外接矩形算法的文档撰写。
5.总结
本项目是在计算几何中求解最小有向外接矩形问题的算法设计和CUDA并行实现的研究。通过实现串行算法和CUDA并行算法的可视化比较，进行详细分析，说明并行算法可以大幅度提高算法效率。这将对计算机图形学和计算几何等相关领域的研究和实践具有重要意义。