回 帖 发 新 帖 刷新版面

主题:包络线的算法研究

一、问题的提出和初步讨论

由此看到有人提出等值线的算法,就想尝试一下。

等值线,首先是分布在一个平面上的。在平面上有若干个点,这些点的坐标是已知的,这些点上的测量值应当是符合客观规律的。

将这些点三个一组,构成一个个三角形,在三角形的三个边上做出整数点(或者其他需要值的点),然后用曲线将一串等值点连起来。

在构成三角形之前,首先要确定这些点的范围,也就是将其外围的点连起来形成一个包络线。

这个包络线,可以是凸多边形的。这种情况下,包络线是唯一的,证明从略。

包络线也可以是凹多边形的。这种情况下包络线不是唯一的,从凸多边形为基准,每个边向内收缩,可以遇到内部点,形成紧缩的凹多边形包络线。显然,收缩的程度不同,得到的结果就不同。

回复列表 (共5个回复)

沙发

包络线除了用于类似的问题的数据预处理,也可广泛用于各类平面问题的预处理。

本算法分两部分,第一部分就是做出前面说的凸多边形的包络线,第二部分向内收缩得到一个符合观感的包络线。

板凳

二、基本思路

分两部分,一部分为凸多边形包络线,二部分为精细包络线。

1、凸多边形包络线

取 大三角形(确保顺时针),将这三点标记为边界;
将其余点分为四部分:内部点、第一边外点、第二边外点和第三边外点
do 直到没有边外点
对每个边,在对应的边外点中寻找最远点
标记这个点为边界点,
修改这段边界为两段
标记这个新三角形内点为内部点,其余点分为两部分,一部分保留对应一段新边界,一部分对应新增边界。

loop

2、精细包络线

在完成凸多边形包络线的基础上
do 直到没有合适的点存在
对每段边界,查看线的附近*是否有点,构成三角形(其内如果有点,取距离远边界线段最近的点)
如果用内部点构成两段线段代替原线段,会使其前后两个端点的角度过于尖锐*,则放弃
否则,标记这个点为边界点,修改这段边界为两段
loop

*这里的附近和过于尖锐,决定了最终的包络线形状,后面给出建议值。

3 楼

4 楼


具体代码,因为没有优化,就不献丑了。
思路里面反复使用一些功能,对他们可以编成共用函数,相信在其他平面问题的处理中也会经常用到

5 楼

最后展示一下效果

我来回复

您尚未登录,请登录后再回复。点此登录或注册