发明名称 |
一种图层叠加应用中计算相交对象的方法和装置 |
摘要 |
本发明公开了一种图层叠加应用中计算相交对象的方法和装置。该方法包括:将由对象虚拟化成的线段的斜率进行量化规整;计算量化规整后的线段的规整最小外包矩形;用扫描线进行扫描,当扫描线遇到第一条线段的前端点时,将该线段的规整最小外包矩形加入扫描线状态表中;当扫描线遇到线段的后端点时,则将该线段的记录从扫描状态表中删除;当扫描线遇到下一条线段的前端点时,把所述下一条线段的规整最小外包矩形加入扫描线状态表中,并判断所述下一条线段的规整最小外包矩形与扫描线状态表中的线段的没被扫描部分的规整最小外包矩形是否相交,若相交,则把线段对加入到求交点候选集;反复执行上述步骤,直到扫描线遇到最后一条线段的后端点。 |
申请公布号 |
CN100570642C |
申请公布日期 |
2009.12.16 |
申请号 |
CN200810057744.1 |
申请日期 |
2008.02.14 |
申请人 |
中国科学院计算技术研究所 |
发明人 |
肖子枫;韩冀中;贺劲;李鹏;韩承德 |
分类号 |
G06T17/40(2006.01)I;G06T17/00(2006.01)I |
主分类号 |
G06T17/40(2006.01)I |
代理机构 |
北京律诚同业知识产权代理有限公司 |
代理人 |
梁 挥;陈 振 |
主权项 |
1、一种图层叠加应用中计算相交对象的方法,其特征是,包括以下步骤:步骤S1,将由对象虚拟化成的线段的斜率进行量化规整;步骤S2,计算量化规整后的线段的规整最小外包矩形;步骤S3,用扫描线进行扫描,当扫描线遇到第一条线段的前端点时,将该线段的规整最小外包矩形加入扫描线状态表中;步骤S4,当扫描线遇到一条线段的后端点时,则将该线段的记录从扫描状态表中删除;当扫描线遇到下一条线段的前端点时,把所述下一条线段的规整最小外包矩形加入扫描线状态表中,并判断所述下一条线段的规整最小外包矩形与扫描线状态表中的线段的渐缩规整最小外包矩形是否相交,若相交,则把线段对加入到求交点候选集;其中,所述渐缩规整最小外包矩形是对应于线段的没被扫描部分的规整最小外包矩形;步骤S5,反复执行步骤S4,直到扫描线遇到最后一条线段的后端点。 |
地址 |
100080北京市海淀区中关村科学院南路6号 |