第43卷第6期
2003年11月
大连理工大学学报
Jo urnal of Dalian Unive rsity o f Te chno lo g y
Vol
.43,
No
.6
Nov
. 2003
文章编号: 1000-8608(2003)06-0779-04
收稿日期: 2002-10-22; 修回日期: 2003-10-15.
基金项目: 国 家 自 然 科 学 基 金 资 助 项 目 (50073036, 60175009, 60275019); 教 育 部 博 士 学 科 点 专 项 科 研 基 金 资 助 项 目
(20010141005).
作者简介: 陈 羽(1981-), 男, 硕士生; 滕弘飞
*
(1936-), 男, 教授, 博士生导师.
椭圆-椭圆静动态不适合边界算法
陈 羽
1
, 滕弘飞
* 1,2
( 1.大连理工大学 机械工程学院, 辽宁 大连 116024;
2.大连理工大学 计算机技术研究所, 辽宁 大连 116024 )
摘要: 目前,计算二维几何图形是否干涉的不适合多边形(N FP)算法,针对的是多边形,尚
未涉及椭圆-椭圆不干涉计算问题. 因此,基于
NFP
法概念,提出椭圆-椭圆之间的不干涉算
法,称之为不适合边界算法;进而给出了既相对平动又相对转动的椭圆-椭圆间任一时刻的动
态不干涉边界算法. 该法可应用于求解 Packing 问题、机器人路径规划、虚拟装配、医疗内外
科手术等领域.
关键词: 计算机图形学; 椭圆; 干涉; 动态; 算法; 不适合边界
中图分类号:
TP
391.41 文献标识码:
A
0
引 言
不 干涉算法是计算、判断物体轮廓或几何图
形边界是否干涉的算法,常用的二维算法是 1966
年 Art提出的不适合多边形(N o Fit Polygon,
NFP)法
[1]
;1976 年 A dam ow icz 等 在 处 理 排 样
(nesting) 问题时,运用了他的理论并提出了计算
N FP 的方法
[2]
;此后,N F P 法得到了长足的进展.
目前用 N FP 算法,可以计算凸多边形 -凸多边形
(convex and convex)
[3～ 5]
、凸多边形 -凹多边形
(convex and non-convex) 和 两 个 凹 多 边 形
(non-convex and non-convex)
[6]
3 种情况的不适
合边界. 而对于两椭圆之间不干涉边界
(N on-interference B oundary, N IB ) 问题的研究,
尚不多见. 该不干涉边界对应于多边形的不适合
多边形, 称为不适合边界(No Fit Boundary,
N FB ). 这类问题在实际中广泛存在. 例如,医疗
内外科手术中血管、神经、骨骼,以及手术工具截
面与椭圆形相近似;三维圆形管路在非正交的二
维剖面中,呈椭圆形. N F B 算法的应用背景主要
有:求解 packing 问题
[7 ]
、机器人路径规划、虚拟装
配、医疗内外科手术等.
本文以 N FP 概念为基础
[1]
,研究椭圆 -椭圆
的 N FB 计算方法.
1
两椭圆的不适合边界算法
1
.
1
定义
定义
1
在直角坐标系中,设椭圆中心
O
e
坐
标为(
x
e
,
y
e
);
a
、
b
分别是椭圆的长轴和短轴;倾斜
角γ(γ∈[0,π)) 是椭圆的长轴与
x
轴正向所成的
角,则记椭圆
A
为
A
(
x
e
,
y
e
,
a
,
b
,γ),其方程为
[(
x
-
x
e
)cos γ+ (
y
-
y
e
)sin γ]
2
/
a
2
+[(
x
-
x
e
)sin γ+ (
y
-
y
e
)cos γ]
2
/
b
2
=1
其中:(
x
,
y
) 为椭圆
A
上任一点的坐标.
设点
M
(
x
M
,
y
M
)∈
A
,记过
M
点的椭圆
A
的
切线的斜率为
k
M
(
A
),如图 1 所示.
图1 椭圆
Fig.1 Ellipse
定义
2
椭圆
A
1
保持静止,称之为基准椭
圆;椭圆
A
2
始终与
A
1
接触但不干涉,且
A
1
、
A
2
均
保持原来的倾斜角,不旋转;
A
2
绕
A
1
作平动 1 周
资源评论
weixin_38670297
- 粉丝: 7
- 资源: 927
最新资源
- 基于matlab的FFT分析和滤波程序，可对数据信号进行频谱分析，分析波形中所含谐波分量，并可以对特定频率波形进行提取 不需要通过示波器观察，直接导入数据即可，快捷便利 程序带有详细注释， 图a为
- 基于Springboot+Vue的精简博客系统的设计与实现-毕业源码案例设计（源码+论文）.zip
- 基于Springboot+Vue交通管理在线服务系统的开发-毕业源码案例设计（95分以上）.zip
- uDDS源程序publisher
- 机械手自动排列控制PLC与触摸屏程序设计
- 基于Springboot+Vue的客户关系管理系统(crm)的设计与实现-毕业源码案例设计（高分毕业设计）.zip
- 基于Springboot+Vue的课程作业管理系统毕业源码案例设计（高分毕业设计）.zip
- 基于Springboot+Vue的酒店客房管理系统-毕业源码案例设计（源码+数据库）.zip
- (链家)上海市房屋租赁价格数据.zip
- ESP8266-调试.pdf
- 基于STM32设计的工地扬尘与噪音实时监测系统(网页).pdf
- 基于Springboot+Vue的库存管理系统-毕业源码案例设计（高分毕业设计）.zip
- 基于Springboot+Vue的老年人体检管理系统-毕业源码案例设计（高分毕业设计）.zip
- 基于Springboot+Vue的乐享田园系统-毕业源码案例设计（95分以上）.zip
- 基于Springboot+Vue的流浪宠物管理系统的设计与实现-毕业源码案例设计（95分以上）.zip
- 基于Springboot+Vue的论坛系统-毕业源码案例设计（高分项目）.zip
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
